feanor_math/divisibility.rs
1
2use std::fmt::Debug;
3
4use crate::ring::*;
5
6///
7/// Trait for rings that support checking divisibility, i.e.
8/// whether for `x, y` there is `k` such that `x = ky`.
9///
10pub trait DivisibilityRing: RingBase {
11
12 ///
13 /// Additional data associated to a fixed ring element that can be used
14 /// to speed up division by this ring element.
15 ///
16 /// See also [`DivisibilityRing::prepare_divisor()`].
17 ///
18 #[stability::unstable(feature = "enable")]
19 type PreparedDivisorData = ();
20
21 ///
22 /// Checks whether there is an element `x` such that `rhs * x = lhs`, and
23 /// returns it if it exists.
24 ///
25 /// Note that this does not have to be unique, if rhs is a left zero-divisor.
26 /// In particular, this function will return any element in the ring if `lhs = rhs = 0`.
27 /// In rings with many zero-divisors, this can sometimes lead to unintuitive behavior.
28 /// See also [`crate::pid::PrincipalIdealRing::checked_div_min()`] for a function that,
29 /// if available, might sometimes behave more intuitively.
30 ///
31 /// # Example
32 /// ```rust
33 /// # use feanor_math::ring::*;
34 /// # use feanor_math::primitive_int::*;
35 /// # use feanor_math::divisibility::*;
36 /// let ZZ = StaticRing::<i64>::RING;
37 /// assert_eq!(Some(3), ZZ.checked_left_div(&6, &2));
38 /// assert_eq!(None, ZZ.checked_left_div(&6, &4));
39 /// ```
40 /// In rings that have zero-divisors, there are usually multiple possible results.
41 /// ```rust
42 /// # use feanor_math::ring::*;
43 /// # use feanor_math::divisibility::*;
44 /// # use feanor_math::homomorphism::*;
45 /// # use feanor_math::rings::zn::zn_64::*;
46 /// let ring = Zn::new(6);
47 /// let four_over_four = ring.checked_left_div(&ring.int_hom().map(4), &ring.int_hom().map(4)).unwrap();
48 /// assert!(ring.eq_el(&four_over_four, &ring.int_hom().map(1)) || ring.eq_el(&four_over_four, &ring.int_hom().map(4)));
49 /// // note that the output 4 might be unexpected, since it is a zero-divisor itself!
50 /// ```
51 ///
52 fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element>;
53
54 ///
55 /// Returns whether there is an element `x` such that `rhs * x = lhs`.
56 /// If you need such an element, consider using [`DivisibilityRing::checked_left_div()`].
57 ///
58 /// # Example
59 /// ```rust
60 /// # use feanor_math::ring::*;
61 /// # use feanor_math::primitive_int::*;
62 /// # use feanor_math::divisibility::*;
63 /// let ZZ = StaticRing::<i64>::RING;
64 /// assert_eq!(true, ZZ.divides_left(&6, &2));
65 /// assert_eq!(false, ZZ.divides_left(&6, &4));
66 /// ```
67 ///
68 fn divides_left(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
69 self.checked_left_div(lhs, rhs).is_some()
70 }
71
72 ///
73 /// Same as [`DivisibilityRing::divides_left()`], but requires a commutative ring.
74 ///
75 fn divides(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
76 assert!(self.is_commutative());
77 self.divides_left(lhs, rhs)
78 }
79
80 ///
81 /// Same as [`DivisibilityRing::checked_left_div()`], but requires a commutative ring.
82 ///
83 fn checked_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
84 assert!(self.is_commutative());
85 self.checked_left_div(lhs, rhs)
86 }
87
88 ///
89 /// Returns whether the given element is a unit, i.e. has an inverse.
90 ///
91 fn is_unit(&self, x: &Self::Element) -> bool {
92 self.checked_left_div(&self.one(), x).is_some()
93 }
94
95 ///
96 /// Function that computes a "balancing" factor of a sequence of ring elements.
97 /// The only use of the balancing factor is to increase performance, in particular,
98 /// dividing all elements in the sequence by this factor should make them
99 /// "smaller" resp. cheaper to process.
100 ///
101 /// Note that the balancing factor must always be a non-zero divisor.
102 ///
103 /// Standard cases are reducing fractions (where the sequence would be exactly two
104 /// elements), or polynomials over fields (where we often want to scale the polynomial
105 /// to make all denominators 1).
106 ///
107 /// If balancing does not make sense (as in the case of finite fields) or is not
108 /// supported by the implementation, it is valid to return `None`.
109 ///
110 fn balance_factor<'a, I>(&self, _elements: I) -> Option<Self::Element>
111 where I: Iterator<Item = &'a Self::Element>,
112 Self: 'a
113 {
114 None
115 }
116
117 ///
118 /// "Prepares" an element of this ring for division.
119 ///
120 /// The returned [`PreparedDivisor`] can then be used in calls
121 /// to [`DivisibilityRing::checked_left_div_prepared()`] and other "prepared" division
122 /// functions, which can be faster than for an "unprepared" element.
123 ///
124 /// # Caveat
125 ///
126 /// Previously, this was its own trait, but that caused problems, since using this properly
127 /// would require fully-fledged specialization. Hence, we now inlude it in [`DivisibilityRing`]
128 /// but provide defaults for all `*_prepared()` functions.
129 ///
130 /// This is not perfect, and in particular, if you specialize [`DivisibilityRing::PreparedDivisorData`]
131 /// and not [`DivisibilityRing::prepare_divisor()`], this will currently not cause a compile error, but
132 /// panic at runtime when calling [`DivisibilityRing::prepare_divisor()`] (unfortunately). However,
133 /// it seems like the most usable solution, and does not require unsafe code.
134 ///
135 /// TODO: at the next breaking release, remove default implementation of `prepare_divisor()`.
136 ///
137 /// # Example
138 ///
139 /// Assume we want to go through all positive integers `<= 1000` that are divisible by `257`. The naive
140 /// way would be the following
141 /// ```rust
142 /// # use feanor_math::ring::*;
143 /// # use feanor_math::divisibility::*;
144 /// # use feanor_math::primitive_int::*;
145 /// let ring = StaticRing::<i128>::RING;
146 /// for integer in 0..1000 {
147 /// if ring.divides(&integer, &257) {
148 /// assert!(integer == 0 || integer == 257 || integer == 514 || integer == 771);
149 /// }
150 /// }
151 /// ```
152 /// It can be faster to instead prepare the divisor `257` once and use this "prepared" divisor for
153 /// all checks (of course, it will be much faster to iterate over `(0..10000).step_by(257)`, but
154 /// for the sake of this example, let's use individual divisibility checks).
155 /// ```rust
156 /// # use feanor_math::ring::*;
157 /// # use feanor_math::divisibility::*;
158 /// # use feanor_math::primitive_int::*;
159 /// # let ring = StaticRing::<i128>::RING;
160 /// let prepared_257 = PreparedDivisor::new(ring.get_ring(), 257);
161 /// for integer in 0..1000 {
162 /// if prepared_257.checked_left_div_by(&integer, ring.get_ring()).is_some(){
163 /// assert!(integer == 0 || integer == 257 || integer == 514 || integer == 771);
164 /// }
165 /// }
166 /// ```
167 ///
168 #[stability::unstable(feature = "enable")]
169 fn prepare_divisor(&self, _: &Self::Element) -> Self::PreparedDivisorData {
170 struct ProduceUnitType;
171 trait ProduceValue<T> {
172 fn produce() -> T;
173 }
174 impl<T> ProduceValue<T> for ProduceUnitType {
175 default fn produce() -> T {
176 panic!("if you specialize DivisibilityRing::PreparedDivisorData, you must also specialize DivisibilityRing::prepare_divisor()")
177 }
178 }
179 impl ProduceValue<()> for ProduceUnitType {
180 fn produce() -> () {}
181 }
182 <ProduceUnitType as ProduceValue<Self::PreparedDivisorData>>::produce()
183 }
184
185 ///
186 /// Same as [`DivisibilityRing::checked_left_div()`] but for a prepared divisor.
187 ///
188 /// See also [`DivisibilityRing::prepare_divisor()`].
189 ///
190 #[stability::unstable(feature = "enable")]
191 fn checked_left_div_prepared(&self, lhs: &Self::Element, rhs: &Self::Element, _rhs_prep: &Self::PreparedDivisorData) -> Option<Self::Element> {
192 self.checked_left_div(lhs, rhs)
193 }
194
195 ///
196 /// Same as [`DivisibilityRing::divides_left()`] but for a prepared divisor.
197 ///
198 /// See also [`DivisibilityRing::prepare_divisor()`].
199 ///
200 #[stability::unstable(feature = "enable")]
201 fn divides_left_prepared(&self, lhs: &Self::Element, rhs: &Self::Element, _rhs_prep: &Self::PreparedDivisorData) -> bool {
202 self.divides_left(lhs, rhs)
203 }
204
205 ///
206 /// Same as [`DivisibilityRing::is_unit()`] but for a prepared divisor.
207 ///
208 /// See also [`DivisibilityRing::prepare_divisor()`].
209 ///
210 #[stability::unstable(feature = "enable")]
211 fn is_unit_prepared(&self, x: &PreparedDivisor<Self>) -> bool {
212 self.is_unit(&x.element)
213 }
214
215 ///
216 /// If the given element is a unit, returns its inverse, otherwise `None`.
217 ///
218 /// This is equivalent (but possibly faster) than `ring.checked_div(ring.one(), el)`.
219 ///
220 fn invert(&self, el: &Self::Element) -> Option<Self::Element> {
221 self.checked_div(&self.one(), el)
222 }
223}
224
225///
226/// Struct for ring elements that are stored with associated data to
227/// enable faster divisions.
228///
229/// For details, see [`DivisibilityRing::prepare_divisor()`].
230///
231pub struct PreparedDivisor<R>
232 where R: ?Sized + RingBase + DivisibilityRing
233{
234 /// This [`PreparedDivisor`] can perform the division by this element
235 pub element: R::Element,
236 /// Additional data used to compute the division by the stored element more efficiently
237 pub data: R::PreparedDivisorData
238}
239
240impl<R> PreparedDivisor<R>
241 where R: ?Sized + RingBase + DivisibilityRing,
242{
243 ///
244 /// Creates a new [`PreparedDivisor`] from the given ring element, obtaining
245 /// any additional data by calling [`DivisibilityRing::prepare_divisor()`].
246 ///
247 pub fn new(ring: &R, el: R::Element) -> Self {
248 Self {
249 data: ring.prepare_divisor(&el),
250 element: el
251 }
252 }
253
254 ///
255 /// Computes some `q` such that `q * self == lhs`, if it exists.
256 ///
257 /// If the underlying ring supports it, this uses precomputed data
258 /// and thus can be faster than [`DivisibilityRing::checked_left_div()`].
259 ///
260 pub fn checked_left_div_by(&self, lhs: &R::Element, ring: &R) -> Option<R::Element> {
261 ring.checked_left_div_prepared(lhs, &self.element, &self.data)
262 }
263}
264
265impl<R> Debug for PreparedDivisor<R>
266 where R: ?Sized + RingBase + DivisibilityRing,
267 R::Element: Debug,
268 R::PreparedDivisorData: Debug
269{
270 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
271 f.debug_struct("PreparedDivisor").field("element", &self.element).field("data", &self.data).finish()
272 }
273}
274
275impl<R> Clone for PreparedDivisor<R>
276 where R: ?Sized + RingBase + DivisibilityRing,
277 R::Element: Clone,
278 R::PreparedDivisorData: Clone
279{
280 fn clone(&self) -> Self {
281 Self {
282 element: self.element.clone(),
283 data: self.data.clone()
284 }
285 }
286}
287
288impl<R> Copy for PreparedDivisor<R>
289 where R: ?Sized + RingBase + DivisibilityRing,
290 R::Element: Copy,
291 R::PreparedDivisorData: Copy
292{}
293
294///
295/// Trait for rings that are integral, i.e. have no zero divisors.
296///
297/// A zero divisor is a nonzero element `a` such that there is a nonzero
298/// element `b` with `ab = 0`.
299///
300pub trait Domain: DivisibilityRing {}
301
302///
303/// Trait for [`RingStore`]s that store [`DivisibilityRing`]s. Mainly used
304/// to provide a convenient interface to the `DivisibilityRing`-functions.
305///
306pub trait DivisibilityRingStore: RingStore
307 where Self::Type: DivisibilityRing
308{
309 delegate!{ DivisibilityRing, fn checked_left_div(&self, lhs: &El<Self>, rhs: &El<Self>) -> Option<El<Self>> }
310 delegate!{ DivisibilityRing, fn divides_left(&self, lhs: &El<Self>, rhs: &El<Self>) -> bool }
311 delegate!{ DivisibilityRing, fn is_unit(&self, x: &El<Self>) -> bool }
312 delegate!{ DivisibilityRing, fn checked_div(&self, lhs: &El<Self>, rhs: &El<Self>) -> Option<El<Self>> }
313 delegate!{ DivisibilityRing, fn divides(&self, lhs: &El<Self>, rhs: &El<Self>) -> bool }
314 delegate!{ DivisibilityRing, fn invert(&self, lhs: &El<Self>) -> Option<El<Self>> }
315
316}
317
318impl<R> DivisibilityRingStore for R
319 where R: RingStore, R::Type: DivisibilityRing
320{}
321
322#[cfg(any(test, feature = "generic_tests"))]
323pub mod generic_tests {
324
325 use crate::ring::El;
326 use super::*;
327
328 pub fn test_divisibility_axioms<R: DivisibilityRingStore, I: Iterator<Item = El<R>>>(ring: R, edge_case_elements: I)
329 where R::Type: DivisibilityRing
330 {
331 let elements = edge_case_elements.collect::<Vec<_>>();
332
333 for a in &elements {
334 for b in &elements {
335 let ab = ring.mul(ring.clone_el(a), ring.clone_el(b));
336 let c = ring.checked_left_div(&ab, &a);
337 assert!(c.is_some(), "Divisibility existence failed: there should exist b = {} such that {} = b * {}, but none was found", ring.format(b), ring.format(&ab), ring.format(&a));
338 assert!(ring.eq_el(&ab, &ring.mul_ref_snd(ring.clone_el(a), c.as_ref().unwrap())), "Division failed: {} * {} != {} but {} = checked_div({}, {})", ring.format(a), ring.format(c.as_ref().unwrap()), ring.format(&ab), ring.format(c.as_ref().unwrap()), ring.format(&ab), ring.format(&a));
339
340 if !ring.is_unit(a) {
341 let ab_plus_one = ring.add(ring.clone_el(&ab), ring.one());
342 let c = ring.checked_left_div(&ab_plus_one, &a);
343 assert!(c.is_none(), "Unit check failed: is_unit({}) is false but checked_div({}, {}) = {}", ring.format(a), ring.format(&ab_plus_one), ring.format(a), ring.format(c.as_ref().unwrap()));
344
345 let ab_minus_one = ring.sub(ring.clone_el(&ab), ring.one());
346 let c = ring.checked_left_div(&ab_minus_one, &a);
347 assert!(c.is_none(), "Unit check failed: is_unit({}) is false but checked_div({}, {}) = {}", ring.format(a), ring.format(&ab_minus_one), ring.format(a), ring.format(c.as_ref().unwrap()));
348 } else {
349 let inv = ring.checked_left_div(&ring.one(), a);
350 assert!(inv.is_some(), "Unit check failed: is_unit({}) is true but checked_div({}, {}) is None", ring.format(a), ring.format(&ring.one()), ring.format(&a));
351 let prod = ring.mul_ref(a, inv.as_ref().unwrap());
352 assert!(ring.eq_el(&ring.one(), &prod), "Division failed: {} != {} * {} but checked_div({}, {}) = {}", ring.format(&ring.one()), ring.format(a), ring.format(inv.as_ref().unwrap()), ring.format(&ring.one()), ring.format(a), ring.format(c.as_ref().unwrap()));
353 }
354 }
355 }
356
357 for a in &elements {
358 let a_prepared_divisor = PreparedDivisor::new(ring.get_ring(), ring.clone_el(a));
359 for b in &elements {
360 let ab = ring.mul(ring.clone_el(a), ring.clone_el(b));
361 let c = a_prepared_divisor.checked_left_div_by(&ab, ring.get_ring());
362 assert!(c.is_some(), "Divisibility existence failed for prepared divisor: there should exist b = {} such that {} = b * {}, but none was found", ring.format(b), ring.format(&ab), ring.format(&a));
363 assert!(ring.eq_el(&ab, &ring.mul_ref_snd(ring.clone_el(a), c.as_ref().unwrap())), "Division failed: {} * {} != {} but {} = checked_div({}, {})", ring.format(a), ring.format(c.as_ref().unwrap()), ring.format(&ab), ring.format(c.as_ref().unwrap()), ring.format(&ab), ring.format(&a));
364
365 if !ring.get_ring().is_unit_prepared(&a_prepared_divisor) {
366 let ab_plus_one = ring.add(ring.clone_el(&ab), ring.one());
367 let c = a_prepared_divisor.checked_left_div_by(&ab_plus_one, ring.get_ring());
368 assert!(c.is_none(), "Unit check failed for prepared divisor: is_unit({}) is false but checked_div({}, {}) = {}", ring.format(a), ring.format(&ab_plus_one), ring.format(a), ring.format(c.as_ref().unwrap()));
369
370 let ab_minus_one = ring.sub(ring.clone_el(&ab), ring.one());
371 let c = a_prepared_divisor.checked_left_div_by(&ab_minus_one, ring.get_ring());
372 assert!(c.is_none(), "Unit check failed for prepared divisor: is_unit({}) is false but checked_div({}, {}) = {}", ring.format(a), ring.format(&ab_minus_one), ring.format(a), ring.format(c.as_ref().unwrap()));
373 } else {
374 let inv = a_prepared_divisor.checked_left_div_by(&ring.one(), ring.get_ring());
375 assert!(inv.is_some(), "Unit check failed for prepared divisor: is_unit({}) is true but checked_div({}, {}) is None", ring.format(a), ring.format(&ring.one()), ring.format(&a));
376 let prod = ring.mul_ref(a, inv.as_ref().unwrap());
377 assert!(ring.eq_el(&ring.one(), &prod), "Division failed for prepared divisor: {} != {} * {} but checked_div({}, {}) = {}", ring.format(&ring.one()), ring.format(a), ring.format(inv.as_ref().unwrap()), ring.format(&ring.one()), ring.format(a), ring.format(c.as_ref().unwrap()));
378 }
379 }
380 }
381 }
382}