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