feanor_math/homomorphism.rs
1use std::fmt::Debug;
2use std::marker::PhantomData;
3
4use crate::ring::*;
5use crate::primitive_int::{StaticRingBase, StaticRing};
6
7///
8/// The user-facing trait for ring homomorphisms, i.e. maps `R -> S`
9/// between rings that respect the ring structure. Since all considered
10/// rings are unital, ring homomorphisms also must be unital.
11///
12/// Objects are expected to know their domain and codomain rings and
13/// can thus make sense without an implicit ambient ring (unlike e.g.
14/// ring elements).
15///
16/// Ring homomorphisms are usually obtained by a corresponding method
17/// on [`RingStore`], and their functionality is provided by underlying
18/// functions of [`RingBase`]. Main examples include
19/// - Every ring `R` has a homomorphism `Z -> R`. The corresponding
20/// [`Homomorphism`]-object is obtained with [`RingStore::int_hom()`],
21/// and the functionality provided by [`RingBase::from_int()`].
22/// - [`RingExtension`]s have give a (injective) homomorphism `R -> S`
23/// which can be obtained by [`RingExtensionStore::inclusion()`].
24/// The functionality is provided by functions on [`RingExtension`],
25/// like [`RingExtension::from()`].
26/// - Other "natural" homomorphisms can be obtained via [`RingStore::can_hom()`].
27/// This requires the underlying [`RingBase`]s to implement [`CanHomFrom`],
28/// and the functions of that trait define the homomorphism.
29///
30pub trait Homomorphism<Domain: ?Sized, Codomain: ?Sized>
31 where Domain: RingBase, Codomain: RingBase
32{
33 ///
34 /// The type of the [`RingStore`] used by this object to store the domain ring.
35 ///
36 type DomainStore: RingStore<Type = Domain>;
37 ///
38 /// The type of the [`RingStore`] used by this object to store the codomain ring.
39 ///
40 type CodomainStore: RingStore<Type = Codomain>;
41
42 ///
43 /// Returns a reference to the domain ring.
44 ///
45 fn domain<'a>(&'a self) -> &'a Self::DomainStore;
46
47 ///
48 /// Returns a reference to the codomain ring.
49 ///
50 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore;
51
52 ///
53 /// Applies this homomorphism to the given element from the domain ring,
54 /// resulting in an element in the codomain ring.
55 ///
56 fn map(&self, x: Domain::Element) -> Codomain::Element;
57
58 ///
59 /// Applies this homomorphism to the given element from the domain ring,
60 /// resulting in an element in the codomain ring.
61 ///
62 fn map_ref(&self, x: &Domain::Element) -> Codomain::Element {
63 self.map(self.domain().clone_el(x))
64 }
65
66 ///
67 /// Multiplies the given element in the codomain ring with an element obtained
68 /// by applying this homomorphism to a given element from the domain ring.
69 ///
70 /// This is equivalent to, but may be faster than, first mapping the domain
71 /// ring element via this homomorphism, and then performing ring multiplication.
72 ///
73 fn mul_assign_map(&self, lhs: &mut Codomain::Element, rhs: Domain::Element) {
74 self.codomain().mul_assign(lhs, self.map(rhs))
75 }
76
77 ///
78 /// Multiplies the given element in the codomain ring with an element obtained
79 /// by applying this homomorphism to a given element from the domain ring.
80 ///
81 /// This is equivalent to, but may be faster than, first mapping the domain
82 /// ring element via this homomorphism, and then performing ring multiplication.
83 ///
84 fn mul_assign_ref_map(&self, lhs: &mut Codomain::Element, rhs: &Domain::Element) {
85 self.codomain().mul_assign(lhs, self.map_ref(rhs))
86 }
87
88 ///
89 /// Multiplies the given element in the codomain ring with an element obtained
90 /// by applying this homomorphism to a given element from the domain ring.
91 ///
92 /// This is equivalent to, but may be faster than, first mapping the domain
93 /// ring element via this homomorphism, and then performing ring multiplication.
94 ///
95 fn mul_map(&self, mut lhs: Codomain::Element, rhs: Domain::Element) -> Codomain::Element {
96 self.mul_assign_map(&mut lhs, rhs);
97 lhs
98 }
99
100 ///
101 /// Fused-multiply-add. This computes `lhs * rhs + summand`, where `rhs` is mapped
102 /// into the ring via this homomorphism.
103 ///
104 /// This is equivalent to, but may be faster than, first mapping the domain
105 /// ring element via this homomorphism, and then using [`RingBase::fma()`].
106 ///
107 fn fma_map(&self, lhs: &Codomain::Element, rhs: &Domain::Element, summand: Codomain::Element) -> Codomain::Element {
108 self.codomain().add(summand, self.mul_ref_map(lhs, rhs))
109 }
110
111 ///
112 /// Multiplies the given element in the codomain ring with an element obtained
113 /// by applying this homomorphism to a given element from the domain ring.
114 ///
115 /// This is equivalent to, but may be faster than, first mapping the domain
116 /// ring element via this homomorphism, and then performing ring multiplication.
117 ///
118 fn mul_ref_fst_map(&self, lhs: &Codomain::Element, rhs: Domain::Element) -> Codomain::Element {
119 self.mul_map(self.codomain().clone_el(lhs), rhs)
120 }
121
122 ///
123 /// Multiplies the given element in the codomain ring with an element obtained
124 /// by applying this homomorphism to a given element from the domain ring.
125 ///
126 /// This is equivalent to, but may be faster than, first mapping the domain
127 /// ring element via this homomorphism, and then performing ring multiplication.
128 ///
129 fn mul_ref_snd_map(&self, mut lhs: Codomain::Element, rhs: &Domain::Element) -> Codomain::Element {
130 self.mul_assign_ref_map(&mut lhs, rhs);
131 lhs
132 }
133
134 ///
135 /// Multiplies the given element in the codomain ring with an element obtained
136 /// by applying this homomorphism to a given element from the domain ring.
137 ///
138 /// This is equivalent to, but may be faster than, first mapping the domain
139 /// ring element via this homomorphism, and then performing ring multiplication.
140 ///
141 fn mul_ref_map(&self, lhs: &Codomain::Element, rhs: &Domain::Element) -> Codomain::Element {
142 self.mul_ref_snd_map(self.codomain().clone_el(lhs), rhs)
143 }
144
145 ///
146 /// Constructs the homomorphism `x -> self.map(prev.map(x))`.
147 ///
148 fn compose<F, PrevDomain: ?Sized + RingBase>(self, prev: F) -> ComposedHom<PrevDomain, Domain, Codomain, F, Self>
149 where Self: Sized, F: Homomorphism<PrevDomain, Domain>
150 {
151 assert!(prev.codomain().get_ring() == self.domain().get_ring());
152 ComposedHom { f: prev, g: self, domain: PhantomData, intermediate: PhantomData, codomain: PhantomData }
153 }
154
155 ///
156 /// Multiplies the given element in the codomain ring with an element obtained
157 /// by applying this and another homomorphism to a given element from another ring.
158 ///
159 /// The equivalent of [`Homomorphism::mul_assign_map()`] for a chain of two
160 /// homomorphisms. While providing specialized implementations for longer and longer
161 /// chains soon becomes ridiculous, there is one important use case why we would want
162 /// at least length-2 chains:
163 ///
164 /// In particular, many [`RingExtension`]s have elements that consist of multiple
165 /// elements of the base ring, with base-ring-multiplication being scalar-vector
166 /// multiplication. Hence, if the base ring allows a fast-multiplication through
167 /// a single homomorphism, it makes sense to extend that along an [`Inclusion`].
168 /// Hence, we also have [`RingExtension::mul_assign_base_through_hom()`].
169 ///
170 #[stability::unstable(feature = "enable")]
171 fn mul_assign_ref_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, Domain>>(&self, lhs: &mut Codomain::Element, rhs: &First::Element, hom: H) {
172 self.mul_assign_map(lhs, hom.map_ref(rhs));
173 }
174
175 ///
176 /// Multiplies the given element in the codomain ring with an element obtained
177 /// by applying this and another homomorphism to a given element from another ring.
178 ///
179 /// For details, see [`Homomorphism::mul_assign_ref_map_through_hom()`].
180 ///
181 #[stability::unstable(feature = "enable")]
182 fn mul_assign_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, Domain>>(&self, lhs: &mut Codomain::Element, rhs: First::Element, hom: H) {
183 self.mul_assign_map(lhs, hom.map(rhs));
184 }
185}
186
187///
188/// Trait for rings R that have a canonical homomorphism `S -> R`.
189/// A ring homomorphism is expected to be unital.
190///
191/// This trait is considered implementor-facing, so it is designed to easily
192/// implement natural maps between rings. When using homomorphisms, consider
193/// using instead [`CanHom`], as it does not require weird syntax like
194/// `R.get_ring().map_in(S.get_ring(), x, &hom)`.
195///
196/// **Warning** Because of type-system limitations (see below), this trait
197/// is not implemented in all cases where it makes sense, in particular when
198/// type parameters are involved. Thus, you should always consider this trait
199/// to be for convenience only. A truly generic algorithm should, if possible,
200/// not constrain input ring types using `CanHomFrom`, but instead take an
201/// additional object of generic type bounded by [`Homomorphism`] that provides
202/// the required homomorphism.
203///
204/// # Exact requirements
205///
206/// Which homomorphisms are considered canonical is up to implementors,
207/// as long as any diagram of canonical homomorphisms commutes. In
208/// other words, if there are rings `R, S` and "intermediate rings"
209/// `R1, ..., Rn` resp. `R1', ..., Rm'` such that there are canonical
210/// homomorphisms
211/// ```text
212/// S -> R1 -> R2 -> ... -> Rn -> R
213/// ```
214/// and
215/// ```text
216/// S -> R1' -> R2' -> ... -> Rm' -> R
217/// ```
218/// then both homomorphism chains should yield same results on same
219/// inputs.
220///
221/// If the canonical homomorphism might be an isomorphism, consider also
222/// implementing [`CanIsoFromTo`].
223///
224/// # Example
225///
226/// Most integer rings support canonical homomorphisms between them.
227/// ```rust
228/// # use feanor_math::ring::*;
229/// # use feanor_math::homomorphism::*;
230/// # use feanor_math::primitive_int::*;
231/// # use feanor_math::integer::*;
232/// let R = StaticRing::<i64>::RING;
233/// let S = BigIntRing::RING;
234/// let eight = S.int_hom().map(8);
235/// // on RingBase level
236/// let hom = R.get_ring().has_canonical_hom(S.get_ring()).unwrap();
237/// assert_eq!(8, R.get_ring().map_in(S.get_ring(), S.clone_el(&eight), &hom));
238/// // on RingStore level
239/// assert_eq!(8, R.coerce(&S, S.clone_el(&eight)));
240/// // or
241/// let hom = R.can_hom(&S).unwrap();
242/// assert_eq!(8, hom.map_ref(&eight));
243/// ```
244///
245/// # Limitations
246///
247/// The rust constraints regarding conflicting impl make it, in some cases,
248/// impossible to implement all the canonical homomorphisms that we would like.
249/// This is true in particular, if the rings are highly generic, and build
250/// on base rings. In this case, it should always be preferred to implement
251/// `CanIsoFromTo` for rings that are "the same", and on the other hand not
252/// to implement classical homomorphisms, like `ZZ -> R` which exists for any
253/// ring R. In applicable cases, consider also implementing [`RingExtension`].
254///
255/// Because of this reason, implementing [`RingExtension`] also does not require
256/// an implementation of `CanHomFrom<Self::BaseRing>`. Hence, if you as a user
257/// miss a certain implementation of `CanHomFrom`, check whether there maybe
258/// is a corresponding implementation of [`RingExtension`], or a member function.
259///
260/// # More examples
261///
262/// ## Integer rings
263///
264/// All given integer rings have canonical isomorphisms between each other.
265/// ```rust
266/// # use feanor_math::ring::*;
267/// # use feanor_math::integer::*;
268/// # use feanor_math::primitive_int::*;
269/// # use feanor_math::integer::*;
270/// let Z_i8 = StaticRing::<i8>::RING;
271/// let Z_i32 = StaticRing::<i32>::RING;
272/// let Z_i128 = StaticRing::<i128>::RING;
273/// let Z_big = BigIntRing::RING;
274///
275/// assert!(Z_i8.can_iso(&Z_i8).is_some());
276/// assert!(Z_i8.can_iso(&Z_i32).is_some());
277/// assert!(Z_i8.can_iso(&Z_i128).is_some());
278/// assert!(Z_i8.can_iso(&Z_big).is_some());
279///
280/// assert!(Z_i32.can_iso(&Z_i8).is_some());
281/// assert!(Z_i32.can_iso(&Z_i32).is_some());
282/// assert!(Z_i32.can_iso(&Z_i128).is_some());
283/// assert!(Z_i32.can_iso(&Z_big).is_some());
284///
285/// assert!(Z_i128.can_iso(&Z_i8).is_some());
286/// assert!(Z_i128.can_iso(&Z_i32).is_some());
287/// assert!(Z_i128.can_iso(&Z_i128).is_some());
288/// assert!(Z_i128.can_iso(&Z_big).is_some());
289///
290/// assert!(Z_big.can_iso(&Z_i8).is_some());
291/// assert!(Z_big.can_iso(&Z_i32).is_some());
292/// assert!(Z_big.can_iso(&Z_i128).is_some());
293/// assert!(Z_big.can_iso(&Z_big).is_some());
294/// ```
295///
296/// ## Integer quotient rings `Z/nZ`
297///
298/// Due to conflicting implementations, only the most useful conversions
299/// are implemented for `Z/nZ`.
300/// ```rust
301/// # use feanor_math::ring::*;
302/// # use feanor_math::primitive_int::*;
303/// # use feanor_math::homomorphism::*;
304/// # use feanor_math::integer::*;
305/// # use feanor_math::rings::zn::*;
306/// # use feanor_math::rings::zn::zn_big;
307/// # use feanor_math::rings::zn::zn_rns;
308/// let ZZ = StaticRing::<i128>::RING;
309/// let ZZ_big = BigIntRing::RING;
310///
311/// let zn_big_i128 = zn_big::Zn::new(ZZ, 17 * 257);
312/// let zn_big_big = zn_big::Zn::new(ZZ_big, ZZ_big.int_hom().map(17 * 257));
313/// let Zn_std = zn_64::Zn::new(17 * 257);
314/// let Zn_rns = zn_rns::Zn::create_from_primes(vec![17, 257], ZZ_big);
315///
316/// assert!(zn_big_i128.can_iso(&zn_big_i128).is_some());
317/// assert!(zn_big_i128.can_iso(&zn_big_big).is_some());
318///
319/// assert!(zn_big_big.can_iso(&zn_big_i128).is_some());
320/// assert!(zn_big_big.can_iso(&zn_big_big).is_some());
321///
322/// assert!(Zn_std.can_iso(&zn_big_i128).is_some());
323/// assert!(Zn_std.can_iso(&Zn_std).is_some());
324///
325/// assert!(Zn_rns.can_iso(&zn_big_i128).is_some());
326/// assert!(Zn_rns.can_iso(&zn_big_big).is_some());
327/// assert!(Zn_rns.can_iso(&Zn_rns).is_some());
328/// ```
329/// Most notably, reduction homomorphisms are currently not available.
330/// You can use [`crate::rings::zn::ZnReductionMap`] instead.
331/// ```rust
332/// # use feanor_math::ring::*;
333/// # use feanor_math::primitive_int::*;
334/// # use feanor_math::homomorphism::*;
335/// # use feanor_math::integer::*;
336/// # use feanor_math::rings::zn::*;
337/// # use feanor_math::assert_el_eq;
338/// let Z9 = zn_64::Zn::new(9);
339/// let Z3 = zn_64::Zn::new(3);
340/// assert!(Z3.can_hom(&Z9).is_none());
341/// let mod_3 = ZnReductionMap::new(&Z9, &Z3).unwrap();
342/// assert_el_eq!(Z3, Z3.one(), mod_3.map(Z9.int_hom().map(4)));
343/// ```
344/// Additionally, there are the projections `Z -> Z/nZ`.
345/// They are all implemented, even though [`crate::rings::zn::ZnRing`] currently
346/// only requires the projection from the "associated" integer ring.
347/// ```rust
348/// # use feanor_math::ring::*;
349/// # use feanor_math::homomorphism::*;
350/// # use feanor_math::primitive_int::*;
351/// # use feanor_math::integer::*;
352/// # use feanor_math::rings::zn::*;
353/// let ZZ = StaticRing::<i128>::RING;
354/// let ZZ_big = BigIntRing::RING;
355///
356/// let zn_big_i128 = zn_big::Zn::new(ZZ, 17 * 257);
357/// let zn_big_big = zn_big::Zn::new(ZZ_big, ZZ_big.int_hom().map(17 * 257));
358/// let Zn_std = zn_64::Zn::new(17 * 257);
359/// let Zn_rns = zn_rns::Zn::create_from_primes(vec![17, 257], ZZ_big);
360///
361/// assert!(zn_big_i128.can_hom(&ZZ).is_some());
362/// assert!(zn_big_i128.can_hom(&ZZ_big).is_some());
363///
364/// assert!(zn_big_big.can_hom(&ZZ).is_some());
365/// assert!(zn_big_big.can_hom(&ZZ_big).is_some());
366///
367/// assert!(Zn_std.can_hom(&ZZ).is_some());
368/// assert!(Zn_std.can_hom(&ZZ_big).is_some());
369///
370/// assert!(Zn_rns.can_hom(&ZZ).is_some());
371/// assert!(Zn_rns.can_hom(&ZZ_big).is_some());
372/// ```
373///
374/// ## Polynomial Rings
375///
376/// For the two provided univariate polynomial ring implementations, we have the isomorphisms
377/// ```rust
378/// # use feanor_math::ring::*;
379/// # use feanor_math::primitive_int::*;
380/// # use feanor_math::integer::*;
381/// # use feanor_math::rings::poly::*;
382///
383/// let ZZ = StaticRing::<i128>::RING;
384/// let P_dense = dense_poly::DensePolyRing::new(ZZ, "X");
385/// let P_sparse = sparse_poly::SparsePolyRing::new(ZZ, "X");
386///
387/// assert!(P_dense.can_iso(&P_dense).is_some());
388/// assert!(P_dense.can_iso(&P_sparse).is_some());
389/// assert!(P_sparse.can_iso(&P_dense).is_some());
390/// assert!(P_sparse.can_iso(&P_sparse).is_some());
391/// ```
392/// Unfortunately, the inclusions `R -> R[X]` are not implemented as canonical homomorphisms,
393/// however provided by the functions of [`RingExtension`].
394///
395pub trait CanHomFrom<S>: RingBase
396 where S: RingBase + ?Sized
397{
398 ///
399 /// Data required to compute the action of the canonical homomorphism on ring elements.
400 ///
401 type Homomorphism;
402
403 ///
404 /// If there is a canonical homomorphism `from -> self`, returns `Some(data)`, where
405 /// `data` is additional data that can be used to compute the action of the homomorphism
406 /// on ring elements. Otherwise, `None` is returned.
407 ///
408 fn has_canonical_hom(&self, from: &S) -> Option<Self::Homomorphism>;
409
410 ///
411 /// Evaluates the homomorphism.
412 ///
413 fn map_in(&self, from: &S, el: S::Element, hom: &Self::Homomorphism) -> Self::Element;
414
415 ///
416 /// Evaluates the homomorphism, taking the element by reference.
417 ///
418 fn map_in_ref(&self, from: &S, el: &S::Element, hom: &Self::Homomorphism) -> Self::Element {
419 self.map_in(from, from.clone_el(el), hom)
420 }
421
422 ///
423 /// Evaluates the homomorphism on `rhs`, and multiplies the result to `lhs`.
424 ///
425 fn mul_assign_map_in(&self, from: &S, lhs: &mut Self::Element, rhs: S::Element, hom: &Self::Homomorphism) {
426 self.mul_assign(lhs, self.map_in(from, rhs, hom));
427 }
428
429 ///
430 /// Evaluates the homomorphism on `rhs`, taking it by reference, and multiplies the result to `lhs`.
431 ///
432 fn mul_assign_map_in_ref(&self, from: &S, lhs: &mut Self::Element, rhs: &S::Element, hom: &Self::Homomorphism) {
433 self.mul_assign(lhs, self.map_in_ref(from, rhs, hom));
434 }
435
436 ///
437 /// Fused-multiply-add. Computes `summand + lhs * rhs`, where `rhs` is mapped into the ring via the homomorphism.
438 ///
439 fn fma_map_in(&self, from: &S, lhs: &Self::Element, rhs: &S::Element, summand: Self::Element, hom: &Self::Homomorphism) -> Self::Element {
440 let mut lhs_copy = self.clone_el(lhs);
441 self.mul_assign_map_in_ref(from, &mut lhs_copy, rhs, hom);
442 return self.add(lhs_copy, summand);
443 }
444}
445
446///
447/// Trait for rings R that have a canonical isomorphism `S -> R`.
448/// A ring homomorphism is expected to be unital.
449///
450/// **Warning** Because of type-system limitations (see [`CanHomFrom`]), this trait
451/// is not implemented in all cases where it makes sense, in particular when
452/// type parameters are involved. Thus, you should always consider this trait
453/// to be for convenience only. A truly generic algorithm should, if possible,
454/// not constrain input ring types using `CanHomFrom`, but instead take an
455/// additional object of generic type bounded by [`Homomorphism`] that provides
456/// the required homomorphism.
457///
458/// # Exact requirements
459///
460/// Same as for [`CanHomFrom`], it is up to implementors to decide which
461/// isomorphisms are canonical, as long as each diagram that contains
462/// only canonical homomorphisms, canonical isomorphisms and their inverses
463/// commutes.
464/// In other words, if there are rings `R, S` and "intermediate rings"
465/// `R1, ..., Rn` resp. `R1', ..., Rm'` such that there are canonical
466/// homomorphisms `->` or isomorphisms `<~>` connecting them - e.g. like
467/// ```text
468/// S -> R1 -> R2 <~> R3 <~> R4 -> ... -> Rn -> R
469/// ```
470/// and
471/// ```text
472/// S <~> R1' -> R2' -> ... -> Rm' -> R
473/// ```
474/// then both chains should yield same results on same inputs.
475///
476/// Hence, it would be natural if the trait were symmetrical, i.e.
477/// for any implementation `R: CanIsoFromTo<S>` there is also an
478/// implementation `S: CanIsoFromTo<R>`. However, because of the trait
479/// impl constraints of Rust, this is unpracticable and so we only
480/// require the implementation `R: CanHomFrom<S>`.
481///
482pub trait CanIsoFromTo<S>: CanHomFrom<S>
483 where S: RingBase + ?Sized
484{
485 ///
486 /// Data required to compute a preimage under the canonical homomorphism.
487 ///
488 type Isomorphism;
489
490 ///
491 /// If there is a canonical homomorphism `from -> self`, and this homomorphism
492 /// is an isomorphism, returns `Some(data)`, where `data` is additional data that
493 /// can be used to compute preimages under the homomorphism. Otherwise, `None` is
494 /// returned.
495 ///
496 fn has_canonical_iso(&self, from: &S) -> Option<Self::Isomorphism>;
497
498 ///
499 /// Computes the preimage of `el` under the canonical homomorphism `from -> self`.
500 ///
501 fn map_out(&self, from: &S, el: Self::Element, iso: &Self::Isomorphism) -> S::Element;
502}
503
504///
505/// Basically an alias for `CanIsoFromTo<Self>`, but implemented as new
506/// trait since trait aliases are not available.
507///
508pub trait SelfIso: CanIsoFromTo<Self> {}
509
510impl<R: ?Sized + CanIsoFromTo<R>> SelfIso for R {}
511
512///
513/// A high-level wrapper of [`CanHomFrom::Homomorphism`] that references the
514/// domain and codomain rings, and is much easier to use.
515///
516/// # Example
517/// ```rust
518/// # use feanor_math::ring::*;
519/// # use feanor_math::homomorphism::*;
520/// # use feanor_math::homomorphism::*;
521/// # use feanor_math::primitive_int::*;
522/// let from = StaticRing::<i32>::RING;
523/// let to = StaticRing::<i64>::RING;
524/// let hom = to.can_hom(&from).unwrap();
525/// assert_eq!(7, hom.map(7));
526/// // instead of
527/// let hom = to.get_ring().has_canonical_hom(from.get_ring()).unwrap();
528/// assert_eq!(7, to.get_ring().map_in(from.get_ring(), 7, &hom));
529/// ```
530///
531/// # See also
532/// The "bi-directional" variant [`CanHom`], the basic interfaces [`CanHomFrom`] and
533/// [`CanIsoFromTo`] and the very simplified function [`RingStore::coerce`].
534///
535pub struct CanHom<R, S>
536 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
537{
538 from: R,
539 to: S,
540 data: <S::Type as CanHomFrom<R::Type>>::Homomorphism
541}
542
543impl<R, S> Debug for CanHom<R, S>
544 where R: RingStore + Debug, S: RingStore + Debug, S::Type: CanHomFrom<R::Type>
545{
546 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
547 f.debug_struct("CanHom").field("from", &self.from).field("to", &self.to).finish()
548 }
549}
550
551impl<R, S> CanHom<R, S>
552 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
553{
554 ///
555 /// Creates a new [`CanHom`] from `from` to `to`, if the
556 /// corresonding rings support it.
557 ///
558 pub fn new(from: R, to: S) -> Result<Self, (R, S)> {
559 match to.get_ring().has_canonical_hom(from.get_ring()) {
560 Some(data) => Ok(Self::from_raw_parts(from, to, data)),
561 _ => Err((from, to))
562 }
563 }
564
565 ///
566 /// Returns a reference to the underlying [`CanHomFrom::Homomorphism`].
567 ///
568 pub fn raw_hom(&self) -> &<S::Type as CanHomFrom<R::Type>>::Homomorphism {
569 &self.data
570 }
571
572 ///
573 /// Returns the underlying [`CanHomFrom::Homomorphism`], consuming this object.
574 ///
575 pub fn into_raw_hom(self) -> <S::Type as CanHomFrom<R::Type>>::Homomorphism {
576 self.data
577 }
578
579 #[stability::unstable(feature = "enable")]
580 pub fn from_raw_parts(from: R, to: S, data: <S::Type as CanHomFrom<R::Type>>::Homomorphism) -> Self {
581 Self { from, to, data }
582 }
583}
584
585impl<R, S> Clone for CanHom<R, S>
586 where R: RingStore + Clone, S: RingStore + Clone, S::Type: CanHomFrom<R::Type>
587{
588 fn clone(&self) -> Self {
589 Self::new(self.from.clone(), self.to.clone()).ok().unwrap()
590 }
591}
592
593impl<R, S> Homomorphism<R::Type, S::Type> for CanHom<R, S>
594 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
595{
596 type CodomainStore = S;
597 type DomainStore = R;
598
599 fn map(&self, el: El<R>) -> El<S> {
600 self.to.get_ring().map_in(self.from.get_ring(), el, &self.data)
601 }
602
603 fn map_ref(&self, el: &El<R>) -> El<S> {
604 self.to.get_ring().map_in_ref(self.from.get_ring(), el, &self.data)
605 }
606
607 fn domain(&self) -> &R {
608 &self.from
609 }
610
611 fn codomain(&self) -> &S {
612 &self.to
613 }
614
615 fn mul_assign_map(&self, lhs: &mut El<S>, rhs: El<R>) {
616 self.to.get_ring().mul_assign_map_in(self.from.get_ring(), lhs, rhs, &self.data);
617 }
618
619 fn mul_assign_ref_map(&self, lhs: &mut El<S>, rhs: &El<R>) {
620 self.to.get_ring().mul_assign_map_in_ref(self.from.get_ring(), lhs, rhs, &self.data);
621 }
622
623 fn fma_map(&self, lhs: &El<S>, rhs: &El<R>, summand: El<S>) -> El<S> {
624 self.to.get_ring().fma_map_in(self.from.get_ring(), lhs, rhs, summand, &self.data)
625 }
626}
627
628///
629/// A wrapper of [`CanHomFrom::Homomorphism`] that does not own the data associated
630/// with the homomorphism. Use cases are rare, prefer to use [`CanHom`] whenever possible.
631///
632/// More concretely, this should only be used when you only have a reference to `<R as CanHomFrom<S>>::Homomorphism`,
633/// but cannot refactor code to wrap that object in a [`CanHom`] instead. The main situation
634/// where this occurs is when implementing [`CanHomFrom`], since a the lifetime of [`CanHom`] is
635/// bound by the lifetime of the domain and codomain rings, but `CanHomFrom::Type` does not allow
636/// this.
637///
638#[stability::unstable(feature = "enable")]
639pub struct CanHomRef<'a, R, S>
640 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
641{
642 from: R,
643 to: S,
644 data: &'a <S::Type as CanHomFrom<R::Type>>::Homomorphism
645}
646
647impl<'a, R, S> CanHomRef<'a, R, S>
648 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
649{
650 #[stability::unstable(feature = "enable")]
651 pub fn raw_hom(&self) -> &<S::Type as CanHomFrom<R::Type>>::Homomorphism {
652 &self.data
653 }
654
655 #[stability::unstable(feature = "enable")]
656 pub fn from_raw_parts(from: R, to: S, data: &'a <S::Type as CanHomFrom<R::Type>>::Homomorphism) -> Self {
657 Self { from, to, data }
658 }
659}
660
661impl<'a, R, S> Clone for CanHomRef<'a, R, S>
662 where R: RingStore + Clone, S: RingStore + Clone, S::Type: CanHomFrom<R::Type>
663{
664 fn clone(&self) -> Self {
665 Self::from_raw_parts(self.from.clone(), self.to.clone(), self.data)
666 }
667}
668
669impl<'a, R, S> Copy for CanHomRef<'a, R, S>
670 where R: RingStore + Copy,
671 S: RingStore + Copy,
672 S::Type: CanHomFrom<R::Type>,
673 El<R>: Copy,
674 El<S>: Copy
675{}
676
677impl<'a, R, S> Homomorphism<R::Type, S::Type> for CanHomRef<'a, R, S>
678 where R: RingStore, S: RingStore, S::Type: CanHomFrom<R::Type>
679{
680 type CodomainStore = S;
681 type DomainStore = R;
682
683 fn map(&self, el: El<R>) -> El<S> {
684 self.to.get_ring().map_in(self.from.get_ring(), el, &self.data)
685 }
686
687 fn map_ref(&self, el: &El<R>) -> El<S> {
688 self.to.get_ring().map_in_ref(self.from.get_ring(), el, &self.data)
689 }
690
691 fn domain(&self) -> &R {
692 &self.from
693 }
694
695 fn codomain(&self) -> &S {
696 &self.to
697 }
698
699 fn mul_assign_map(&self, lhs: &mut El<S>, rhs: El<R>) {
700 self.to.get_ring().mul_assign_map_in(self.from.get_ring(), lhs, rhs, &self.data);
701 }
702
703 fn mul_assign_ref_map(&self, lhs: &mut El<S>, rhs: &El<R>) {
704 self.to.get_ring().mul_assign_map_in_ref(self.from.get_ring(), lhs, rhs, &self.data);
705 }
706
707 fn fma_map(&self, lhs: &El<S>, rhs: &El<R>, summand: El<S>) -> El<S> {
708 self.to.get_ring().fma_map_in(self.from.get_ring(), lhs, rhs, summand, &self.data)
709 }
710}
711
712///
713/// A wrapper around [`CanIsoFromTo::Isomorphism`] that references the domain and
714/// codomain rings, making it much easier to use. This also contains the homomorphism
715/// in the other direction, i.e. allows mapping in both directions.
716///
717/// # Example
718/// ```rust
719/// # use feanor_math::ring::*;
720/// # use feanor_math::homomorphism::*;
721/// # use feanor_math::primitive_int::*;
722///
723/// let from = StaticRing::<i32>::RING;
724/// let to = StaticRing::<i64>::RING;
725/// let hom = to.can_iso(&from).unwrap();
726/// assert_eq!(7, hom.map(7));
727/// // instead of
728/// let hom = to.get_ring().has_canonical_iso(from.get_ring()).unwrap();
729/// assert_eq!(7, from.get_ring().map_out(to.get_ring(), 7, &hom));
730/// ```
731///
732/// # See also
733///
734/// The "one-directional" variant [`CanHom`], the basic interfaces [`CanHomFrom`] and
735/// [`CanIsoFromTo`] and the very simplified function [`RingStore::coerce()`].
736///
737pub struct CanIso<R, S>
738 where R: RingStore, S: RingStore, S::Type: CanIsoFromTo<R::Type>
739{
740 from: R,
741 to: S,
742 data: <S::Type as CanIsoFromTo<R::Type>>::Isomorphism
743}
744
745impl<R, S> Debug for CanIso<R, S>
746 where R: RingStore + Debug, S: RingStore + Debug, S::Type: CanIsoFromTo<R::Type>
747{
748 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
749 f.debug_struct("CanIso").field("from", &self.from).field("to", &self.to).finish()
750 }
751}
752
753impl<R, S> Clone for CanIso<R, S>
754 where R: RingStore + Clone, S: RingStore + Clone, S::Type: CanIsoFromTo<R::Type>
755{
756 fn clone(&self) -> Self {
757 Self::new(self.from.clone(), self.to.clone()).ok().unwrap()
758 }
759}
760
761impl<R, S> CanIso<R, S>
762 where R: RingStore, S: RingStore, S::Type: CanIsoFromTo<R::Type>
763{
764 ///
765 /// Creates a new [`CanIso`] between `from` and `to`, if the
766 /// corresonding rings support it.
767 ///
768 /// Somewhat counter-intuitively, the returned object actually
769 /// implements the homomorphism in the direction `to -> from`.
770 /// However, for an isomorphism, the direction is not that relevant,
771 /// and the map in the direction `from -> to` can be obtained by
772 /// [`CanIso::inv()`] or [`CanIso::into_inv()`].
773 ///
774 pub fn new(from: R, to: S) -> Result<Self, (R, S)> {
775 match to.get_ring().has_canonical_iso(from.get_ring()) {
776 Some(data) => {
777 assert!(to.get_ring().has_canonical_hom(from.get_ring()).is_some());
778 Ok(Self { from, to, data })
779 },
780 _ => Err((from, to))
781 }
782 }
783
784 ///
785 /// Returns the inverse homomorphism, consuming this object.
786 ///
787 pub fn into_inv(self) -> CanHom<R, S> {
788 CanHom::new(self.from, self.to).unwrap_or_else(|_| unreachable!())
789 }
790
791 ///
792 /// Returns the inverse homomorphism.
793 ///
794 pub fn inv<'a>(&'a self) -> CanHom<&'a R, &'a S> {
795 CanHom::new(&self.from, &self.to).unwrap_or_else(|_| unreachable!())
796 }
797
798 ///
799 /// Returns a reference to the underlying [`CanIsoFromTo::Isomorphism`].
800 ///
801 pub fn raw_iso(&self) -> &<S::Type as CanIsoFromTo<R::Type>>::Isomorphism {
802 &self.data
803 }
804
805 ///
806 /// Returns the underlying [`CanIsoFromTo::Isomorphism`], consuming this object.
807 ///
808 pub fn into_raw_iso(self) -> <S::Type as CanIsoFromTo<R::Type>>::Isomorphism {
809 self.data
810 }
811}
812
813impl<R, S> Homomorphism<S::Type, R::Type> for CanIso<R, S>
814 where R: RingStore, S: RingStore, S::Type: CanIsoFromTo<R::Type>
815{
816 type DomainStore = S;
817 type CodomainStore = R;
818
819 fn map(&self, x: El<S>) -> El<R> {
820 self.to.get_ring().map_out(self.from.get_ring(), x, &self.data)
821 }
822
823 fn domain(&self) -> &S {
824 &self.to
825 }
826
827 fn codomain(&self) -> &R {
828 &self.from
829 }
830}
831
832///
833/// The ring homomorphism induced by a [`RingExtension`].
834///
835/// # Example
836/// ```rust
837/// # use feanor_math::assert_el_eq;
838/// # use feanor_math::ring::*;
839/// # use feanor_math::primitive_int::*;
840/// # use feanor_math::homomorphism::*;
841/// # use feanor_math::rings::poly::*;
842/// let base = StaticRing::<i32>::RING;
843/// let extension = dense_poly::DensePolyRing::new(base, "X");
844/// let hom = extension.inclusion();
845/// let f = extension.add(hom.map(8), extension.indeterminate());
846/// assert_el_eq!(extension, extension.from_terms([(8, 0), (1, 1)].into_iter()), &f);
847/// ```
848///
849#[derive(Clone, Debug)]
850pub struct Inclusion<R>
851 where R: RingStore, R::Type: RingExtension
852{
853 ring: R
854}
855
856impl<R: RingStore> Copy for Inclusion<R>
857 where R: Copy, El<R>: Copy, R::Type: RingExtension
858{}
859
860impl<R> Inclusion<R>
861 where R: RingStore, R::Type: RingExtension
862{
863 ///
864 /// Returns the [`Inclusion`] from the base ring of the given ring to itself.
865 ///
866 pub fn new(ring: R) -> Self {
867 Inclusion { ring }
868 }
869}
870
871impl<R> Homomorphism<<<R::Type as RingExtension>::BaseRing as RingStore>::Type, R::Type> for Inclusion<R>
872 where R: RingStore, R::Type: RingExtension
873{
874 type CodomainStore = R;
875 type DomainStore = <R::Type as RingExtension>::BaseRing;
876
877 fn domain<'a>(&'a self) -> &'a Self::DomainStore {
878 self.ring.base_ring()
879 }
880
881 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
882 &self.ring
883 }
884
885 fn map(&self, x: El<<R::Type as RingExtension>::BaseRing>) -> El<R> {
886 self.ring.get_ring().from(x)
887 }
888
889 fn map_ref(&self, x: &El<<R::Type as RingExtension>::BaseRing>) -> El<R> {
890 self.ring.get_ring().from_ref(x)
891 }
892
893 fn mul_assign_ref_map(&self, lhs: &mut El<R>, rhs: &El<<R::Type as RingExtension>::BaseRing>) {
894 self.ring.get_ring().mul_assign_base(lhs, rhs)
895 }
896
897 fn mul_assign_map(&self, lhs: &mut El<R>, rhs: El<<R::Type as RingExtension>::BaseRing>) {
898 self.mul_assign_ref_map(lhs, &rhs)
899 }
900
901 fn mul_assign_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, <<R::Type as RingExtension>::BaseRing as RingStore>::Type>>(&self, lhs: &mut El<R>, rhs: First::Element, hom: H) {
902 self.ring.get_ring().mul_assign_base_through_hom(lhs, &rhs, hom)
903 }
904
905 fn mul_assign_ref_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, <<R::Type as RingExtension>::BaseRing as RingStore>::Type>>(&self, lhs: &mut El<R>, rhs: &First::Element, hom: H) {
906 self.ring.get_ring().mul_assign_base_through_hom(lhs, rhs, hom)
907 }
908
909 fn fma_map(&self, lhs: &El<R>, rhs: &El<<R::Type as RingExtension>::BaseRing>, summand: El<R>) -> El<R> {
910 self.ring.get_ring().fma_base(lhs, rhs, summand)
911 }
912}
913
914///
915/// The ring homomorphism `Z -> R` that exists for any ring `R`.
916///
917/// # Example
918/// ```rust
919/// # use feanor_math::assert_el_eq;
920/// # use feanor_math::ring::*;
921/// # use feanor_math::primitive_int::*;
922/// # use feanor_math::homomorphism::*;
923/// # use feanor_math::rings::zn::*;
924/// let ring = zn_static::F17;
925/// let hom = ring.int_hom();
926/// assert_el_eq!(ring, hom.map(1), hom.map(18));
927/// ```
928///
929#[derive(Clone)]
930pub struct IntHom<R>
931 where R: RingStore
932{
933 ring: R
934}
935
936impl<R: RingStore> Copy for IntHom<R>
937 where R: Copy, El<R>: Copy
938{}
939
940impl<R> Homomorphism<StaticRingBase<i32>, R::Type> for IntHom<R>
941 where R: RingStore
942{
943 type CodomainStore = R;
944 type DomainStore = StaticRing<i32>;
945
946 fn domain<'a>(&'a self) -> &'a Self::DomainStore {
947 &StaticRing::<i32>::RING
948 }
949
950 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
951 &self.ring
952 }
953
954 fn map(&self, x: i32) -> El<R> {
955 self.ring.get_ring().from_int(x)
956 }
957
958 fn mul_assign_map(&self, lhs: &mut El<R>, rhs: i32) {
959 self.ring.get_ring().mul_assign_int(lhs, rhs)
960 }
961
962 fn mul_assign_ref_map(&self, lhs: &mut El<R>, rhs: &<StaticRingBase<i32> as RingBase>::Element) {
963 self.mul_assign_map(lhs, *rhs)
964 }
965
966 fn fma_map(&self, lhs: &El<R>, rhs: &i32, summand: El<R>) -> El<R> {
967 self.ring.get_ring().fma_int(lhs, *rhs, summand)
968 }
969}
970
971impl<R> IntHom<R>
972 where R: RingStore
973{
974 ///
975 /// Creates the [`IntHom`] homomorphism
976 /// ```text
977 /// Z -> R, n -> 1 + ... + 1 [n times]
978 /// ```
979 /// for the given ring `R`.
980 ///
981 pub fn new(ring: R) -> Self {
982 Self { ring }
983 }
984}
985
986///
987/// The identity homomorphism `R -> R, x -> x` on the given ring `R`.
988///
989#[derive(Clone)]
990pub struct Identity<R: RingStore> {
991 ring: R
992}
993
994impl<R: RingStore> Copy for Identity<R>
995 where R: Copy, El<R>: Copy
996{}
997
998impl<R: RingStore> Identity<R> {
999
1000 ///
1001 /// Creates the [`Identity`] homomorphism `R -> R, x -> x` on the given ring `R`.
1002 ///
1003 pub fn new(ring: R) -> Self {
1004 Identity { ring }
1005 }
1006}
1007
1008impl<R: RingStore> Homomorphism<R::Type, R::Type> for Identity<R> {
1009
1010 type CodomainStore = R;
1011 type DomainStore = R;
1012
1013 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
1014 &self.ring
1015 }
1016
1017 fn domain<'a>(&'a self) -> &'a Self::DomainStore {
1018 &self.ring
1019 }
1020
1021 fn map(&self, x: El<R>) -> El<R> {
1022 x
1023 }
1024
1025 fn mul_assign_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, R::Type>>(&self, lhs: &mut El<R>, rhs: First::Element, hom: H) {
1026 hom.mul_assign_map(lhs, rhs);
1027 }
1028
1029 fn mul_assign_ref_map_through_hom<First: ?Sized + RingBase, H: Homomorphism<First, R::Type>>(&self, lhs: &mut El<R>, rhs: &First::Element, hom: H) {
1030 hom.mul_assign_ref_map(lhs, rhs);
1031 }
1032
1033 fn fma_map(&self, lhs: &El<R>, rhs: &El<R>, summand: El<R>) -> El<R> {
1034 self.ring.get_ring().fma(lhs, rhs, summand)
1035 }
1036}
1037
1038impl<'a, S, R, H> Homomorphism<S, R> for &'a H
1039 where S: ?Sized + RingBase, R: ?Sized + RingBase, H: Homomorphism<S, R>
1040{
1041 type CodomainStore = H::CodomainStore;
1042 type DomainStore = H::DomainStore;
1043
1044 fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
1045 (*self).codomain()
1046 }
1047
1048 fn domain<'b>(&'b self) -> &'b Self::DomainStore {
1049 (*self).domain()
1050 }
1051
1052 fn map(&self, x: <S as RingBase>::Element) -> <R as RingBase>::Element {
1053 (*self).map(x)
1054 }
1055
1056 fn map_ref(&self, x: &<S as RingBase>::Element) -> <R as RingBase>::Element {
1057 (*self).map_ref(x)
1058 }
1059
1060 fn mul_assign_map(&self, lhs: &mut <R as RingBase>::Element, rhs: <S as RingBase>::Element) {
1061 (*self).mul_assign_map(lhs, rhs)
1062 }
1063
1064 fn mul_assign_ref_map(&self, lhs: &mut <R as RingBase>::Element, rhs: &<S as RingBase>::Element) {
1065 (*self).mul_assign_ref_map(lhs, rhs)
1066 }
1067
1068 fn fma_map(&self, lhs: &<R as RingBase>::Element, rhs: &<S as RingBase>::Element, summand: <R as RingBase>::Element) -> <R as RingBase>::Element {
1069 (*self).fma_map(lhs, rhs, summand)
1070 }
1071}
1072
1073///
1074/// A homomorphism between rings `R -> S`, with its action on elements
1075/// defined by a user-provided closure.
1076///
1077/// It is up to the user to ensure that the given closure indeed
1078/// satisfies the ring homomorphism axioms:
1079/// - For `x, y in R`, it should satisfy `f(x) + f(y) = f(x + y)`
1080/// - For `x, y in R`, it should satisfy `f(x) * f(y) = f(x * y)`
1081/// - It should map `f(0) = 0` and `f(1) = 1`
1082///
1083/// Hence, a [`LambdaHom`] should only be used if none of the builtin
1084/// homomorphisms can achieve the same result, since a function that does
1085/// not follow the above axioms will make algorithms misbehave, and can
1086/// lead to hard-to-debug errors.
1087///
1088#[derive(Clone)]
1089pub struct LambdaHom<R: RingStore, S: RingStore, F>
1090 where F: Fn(&R, &S, &El<R>) -> El<S>
1091{
1092 from: R,
1093 to: S,
1094 f: F
1095}
1096
1097impl<R: RingStore, S: RingStore, F> Copy for LambdaHom<R, S, F>
1098 where F: Copy + Fn(&R, &S, &El<R>) -> El<S>,
1099 R: Copy, El<R>: Copy,
1100 S: Copy, El<S>: Copy
1101{}
1102
1103impl<R: RingStore, S: RingStore, F> LambdaHom<R, S, F>
1104 where F: Fn(&R, &S, &El<R>) -> El<S>
1105{
1106 ///
1107 /// Creates a new [`LambdaHom`] from `from` to `to`, mapping elements as
1108 /// specified by the given function.
1109 ///
1110 /// It is up to the user to ensure that the given closure indeed
1111 /// satisfies the ring homomorphism axioms:
1112 /// - For `x, y in R`, it should satisfy `f(x) + f(y) = f(x + y)`
1113 /// - For `x, y in R`, it should satisfy `f(x) * f(y) = f(x * y)`
1114 /// - It should map `f(0) = 0` and `f(1) = 1`
1115 ///
1116 /// Hence, a [`LambdaHom`] should only be used if none of the builtin
1117 /// homomorphisms can achieve the same result, since a function that does
1118 /// not follow the above axioms will make algorithms misbehave, and can
1119 /// lead to hard-to-debug errors.
1120 ///
1121 pub fn new(from: R, to: S, f: F) -> Self {
1122 Self { from, to, f }
1123 }
1124
1125 ///
1126 /// Returns the stored domain and codomain rings, consuming this object.
1127 ///
1128 #[stability::unstable(feature = "enable")]
1129 pub fn into_domain_codomain(self) -> (R, S) {
1130 (self.from, self.to)
1131 }
1132}
1133
1134impl<R: RingStore, S: RingStore, F> Homomorphism<R::Type, S::Type> for LambdaHom<R, S, F>
1135 where F: Fn(&R, &S, &El<R>) -> El<S>
1136{
1137 type CodomainStore = S;
1138 type DomainStore = R;
1139
1140 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
1141 &self.to
1142 }
1143
1144 fn domain<'a>(&'a self) -> &'a Self::DomainStore {
1145 &self.from
1146 }
1147
1148 fn map(&self, x: El<R>) -> <S::Type as RingBase>::Element {
1149 (self.f)(self.domain(), self.codomain(), &x)
1150 }
1151
1152 fn map_ref(&self, x: &El<R>) -> <S::Type as RingBase>::Element {
1153 (self.f)(self.domain(), self.codomain(), x)
1154 }
1155}
1156
1157///
1158/// The function composition of two homomorphisms `f: R -> S` and `g: S -> T`.
1159///
1160/// More concretely, this is the homomorphism `R -> T` that maps `x` to `g(f(x))`.
1161/// The best way to create a [`ComposedHom`] is through [`Homomorphism::compose()`].
1162///
1163pub struct ComposedHom<R, S, T, F, G>
1164 where F: Homomorphism<R, S>,
1165 G: Homomorphism<S, T>,
1166 R: ?Sized + RingBase,
1167 S: ?Sized + RingBase,
1168 T: ?Sized + RingBase
1169{
1170 f: F,
1171 g: G,
1172 domain: PhantomData<R>,
1173 intermediate: PhantomData<S>,
1174 codomain: PhantomData<T>
1175}
1176
1177impl<R, S, T, F, G> ComposedHom<R, S, T, F, G>
1178 where F: Clone + Homomorphism<R, S>,
1179 G: Clone + Homomorphism<S, T>,
1180 R: ?Sized + RingBase,
1181 S: ?Sized + RingBase,
1182 T: ?Sized + RingBase
1183{
1184 ///
1185 /// Returns a reference to `f`, the homomorphism that is applied first
1186 /// to input elements `x`.
1187 ///
1188 #[stability::unstable(feature = "enable")]
1189 pub fn first(&self) -> &F {
1190 &self.f
1191 }
1192
1193 ///
1194 /// Returns a reference to `g`, the homomorphism that is applied second,
1195 /// so to `f(x)` when mapping an input element `x`.
1196 ///
1197 #[stability::unstable(feature = "enable")]
1198 pub fn second(&self) -> &G {
1199 &self.g
1200 }
1201}
1202
1203impl<R, S, T, F, G> Clone for ComposedHom<R, S, T, F, G>
1204 where F: Clone + Homomorphism<R, S>,
1205 G: Clone + Homomorphism<S, T>,
1206 R: ?Sized + RingBase,
1207 S: ?Sized + RingBase,
1208 T: ?Sized + RingBase
1209{
1210 fn clone(&self) -> Self {
1211 Self {
1212 f: self.f.clone(),
1213 g: self.g.clone(),
1214 domain: PhantomData,
1215 codomain: PhantomData,
1216 intermediate: PhantomData
1217 }
1218 }
1219}
1220
1221impl<R, S, T, F, G> Copy for ComposedHom<R, S, T, F, G>
1222 where F: Copy + Homomorphism<R, S>,
1223 G: Copy + Homomorphism<S, T>,
1224 R: ?Sized + RingBase,
1225 S: ?Sized + RingBase,
1226 T: ?Sized + RingBase
1227{}
1228
1229impl<R, S, T, F, G> Homomorphism<R, T> for ComposedHom<R, S, T, F, G>
1230 where F: Homomorphism<R, S>,
1231 G: Homomorphism<S, T>,
1232 R: ?Sized + RingBase,
1233 S: ?Sized + RingBase,
1234 T: ?Sized + RingBase
1235{
1236 type DomainStore = <F as Homomorphism<R, S>>::DomainStore;
1237 type CodomainStore = <G as Homomorphism<S, T>>::CodomainStore;
1238
1239 fn domain<'a>(&'a self) -> &'a Self::DomainStore {
1240 self.f.domain()
1241 }
1242
1243 fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
1244 self.g.codomain()
1245 }
1246
1247 fn map(&self, x: <R as RingBase>::Element) -> <T as RingBase>::Element {
1248 self.g.map(self.f.map(x))
1249 }
1250
1251 fn map_ref(&self, x: &<R as RingBase>::Element) -> <T as RingBase>::Element {
1252 self.g.map(self.f.map_ref(x))
1253 }
1254
1255 fn mul_assign_map(&self, lhs: &mut <T as RingBase>::Element, rhs: <R as RingBase>::Element) {
1256 self.g.mul_assign_map_through_hom(lhs, rhs, &self.f)
1257 }
1258
1259 fn mul_assign_ref_map(&self, lhs: &mut <T as RingBase>::Element, rhs: &<R as RingBase>::Element) {
1260 self.g.mul_assign_ref_map_through_hom(lhs, rhs, &self.f)
1261 }
1262
1263 fn fma_map(&self, lhs: &<T as RingBase>::Element, rhs: &<R as RingBase>::Element, summand: <T as RingBase>::Element) -> <T as RingBase>::Element {
1264 self.g.fma_map(lhs, &self.f.map_ref(rhs), summand)
1265 }
1266}
1267
1268///
1269/// Implements the trivial canonical isomorphism `Self: CanIsoFromTo<Self>` for the
1270/// given type.
1271///
1272/// Note that this does not support generic types, as for those, it is
1273/// usually better to implement
1274/// ```rust
1275/// # use feanor_math::ring::*;
1276/// # use feanor_math::homomorphism::*;
1277/// # use feanor_math::delegate::*;
1278/// // define `RingConstructor<R: RingStore>`
1279/// # struct RingConstructor<R: RingStore>(R);
1280/// # impl<R: RingStore> DelegateRing for RingConstructor<R> {
1281/// # type Element = El<R>;
1282/// # type Base = R::Type;
1283/// # fn get_delegate(&self) -> &Self::Base { self.0.get_ring() }
1284/// # fn delegate_ref<'a>(&self, el: &'a Self::Element) -> &'a <Self::Base as RingBase>::Element { el }
1285/// # fn delegate_mut<'a>(&self, el: &'a mut Self::Element) -> &'a mut <Self::Base as RingBase>::Element { el }
1286/// # fn delegate(&self, el: Self::Element) -> <Self::Base as RingBase>::Element { el }
1287/// # fn rev_delegate(&self, el: <Self::Base as RingBase>::Element) -> Self::Element { el }
1288/// # }
1289/// # impl<R: RingStore> PartialEq for RingConstructor<R> {
1290/// # fn eq(&self, other: &Self) -> bool {
1291/// # self.0.get_ring() == other.0.get_ring()
1292/// # }
1293/// # }
1294/// impl<R, S> CanHomFrom<RingConstructor<S>> for RingConstructor<R>
1295/// where R: RingStore, S: RingStore, R::Type: CanHomFrom<S::Type>
1296/// {
1297/// type Homomorphism = <R::Type as CanHomFrom<S::Type>>::Homomorphism;
1298///
1299/// fn has_canonical_hom(&self, from: &RingConstructor<S>) -> Option<<R::Type as CanHomFrom<S::Type>>::Homomorphism> {
1300/// // delegate to base ring of type `R::Type`
1301/// # self.get_delegate().has_canonical_hom(from.get_delegate())
1302/// }
1303///
1304/// fn map_in(&self, from: &RingConstructor<S>, el: <RingConstructor<S> as RingBase>::Element, hom: &Self::Homomorphism) -> <Self as RingBase>::Element {
1305/// // delegate to base ring of type `R::Type`
1306/// # self.get_delegate().map_in(from.get_delegate(), el, hom)
1307/// }
1308/// }
1309///
1310/// // and same for CanIsoFromTo
1311/// ```
1312/// or something similar.
1313///
1314/// # Example
1315/// ```rust
1316/// # use feanor_math::ring::*;
1317/// # use feanor_math::homomorphism::*;
1318/// # use feanor_math::primitive_int::*;
1319/// # use feanor_math::delegate::*;
1320/// # use feanor_math::{assert_el_eq, impl_eq_based_self_iso};
1321///
1322/// #[derive(PartialEq, Clone)]
1323/// struct MyI32Ring;
1324///
1325/// impl DelegateRing for MyI32Ring {
1326///
1327/// type Base = StaticRingBase<i32>;
1328/// type Element = i32;
1329///
1330/// fn get_delegate(&self) -> &Self::Base {
1331/// StaticRing::<i32>::RING.get_ring()
1332/// }
1333///
1334/// fn delegate_ref<'a>(&self, el: &'a i32) -> &'a i32 {
1335/// el
1336/// }
1337///
1338/// fn delegate_mut<'a>(&self, el: &'a mut i32) -> &'a mut i32 {
1339/// el
1340/// }
1341///
1342/// fn delegate(&self, el: i32) -> i32 {
1343/// el
1344/// }
1345///
1346/// fn postprocess_delegate_mut(&self, _: &mut i32) {
1347/// // sometimes it might be necessary to fix some data of `Self::Element`
1348/// // if the underlying `Self::Base::Element` was modified via `delegate_mut()`;
1349/// // this is not the case here, so leave empty
1350/// }
1351///
1352/// fn rev_delegate(&self, el: i32) -> i32 {
1353/// el
1354/// }
1355/// }
1356///
1357/// // since we provide `PartialEq`, the trait `CanIsoFromTo<Self>` is trivial
1358/// // to implement
1359/// impl_eq_based_self_iso!{ MyI32Ring }
1360///
1361/// let ring = RingValue::from(MyI32Ring);
1362/// assert_el_eq!(ring, ring.int_hom().map(1), ring.one());
1363/// ```
1364///
1365#[macro_export]
1366macro_rules! impl_eq_based_self_iso {
1367 ($type:ty) => {
1368 impl $crate::homomorphism::CanHomFrom<Self> for $type {
1369
1370 type Homomorphism = ();
1371
1372 fn has_canonical_hom(&self, from: &Self) -> Option<()> {
1373 if self == from {
1374 Some(())
1375 } else {
1376 None
1377 }
1378 }
1379
1380 fn map_in(&self, _from: &Self, el: <Self as $crate::ring::RingBase>::Element, _: &Self::Homomorphism) -> <Self as $crate::ring::RingBase>::Element {
1381 el
1382 }
1383 }
1384
1385 impl $crate::homomorphism::CanIsoFromTo<Self> for $type {
1386
1387 type Isomorphism = ();
1388
1389 fn has_canonical_iso(&self, from: &Self) -> Option<()> {
1390 if self == from {
1391 Some(())
1392 } else {
1393 None
1394 }
1395 }
1396
1397 fn map_out(&self, _from: &Self, el: <Self as $crate::ring::RingBase>::Element, _: &Self::Homomorphism) -> <Self as $crate::ring::RingBase>::Element {
1398 el
1399 }
1400 }
1401 };
1402}
1403
1404#[cfg(any(test, feature = "generic_tests"))]
1405pub mod generic_tests {
1406
1407 use super::*;
1408
1409 pub fn test_homomorphism_axioms<R: ?Sized + RingBase, S: ?Sized + RingBase, H, I: Iterator<Item = R::Element>>(hom: H, edge_case_elements: I)
1410 where H: Homomorphism<R, S>
1411 {
1412 let from = hom.domain();
1413 let to = hom.codomain();
1414 let elements = edge_case_elements.collect::<Vec<_>>();
1415
1416 assert!(to.is_zero(&hom.map(from.zero())));
1417 assert!(to.is_one(&hom.map(from.one())));
1418
1419 for a in &elements {
1420 for b in &elements {
1421 {
1422 let map_a = hom.map_ref(a);
1423 let map_b = hom.map_ref(b);
1424 let map_sum = to.add_ref(&map_a, &map_b);
1425 let sum_map = hom.map(from.add_ref(a, b));
1426 assert!(to.eq_el(&map_sum, &sum_map), "Additive homomorphic property failed: hom({} + {}) = {} != {} = {} + {}", from.format(a), from.format(b), to.format(&sum_map), to.format(&map_sum), to.format(&map_a), to.format(&map_b));
1427 }
1428 {
1429 let map_a = hom.map_ref(a);
1430 let map_b = hom.map_ref(b);
1431 let map_prod = to.mul_ref(&map_a, &map_b);
1432 let prod_map = hom.map(from.mul_ref(a, b));
1433 assert!(to.eq_el(&map_prod, &prod_map), "Multiplicative homomorphic property failed: hom({} * {}) = {} != {} = {} * {}", from.format(a), from.format(b), to.format(&prod_map), to.format(&map_prod), to.format(&map_a), to.format(&map_b));
1434 }
1435 {
1436 let map_a = hom.map_ref(a);
1437 let prod_map = hom.map(from.mul_ref(a, b));
1438 let mut mul_assign = to.clone_el(&map_a);
1439 hom.mul_assign_ref_map( &mut mul_assign, b);
1440 assert!(to.eq_el(&mul_assign, &prod_map), "mul_assign_ref_map() failed: hom({} * {}) = {} != {} = mul_map_in(hom({}), {})", from.format(a), from.format(b), to.format(&prod_map), to.format(&mul_assign), to.format(&map_a), from.format(b));
1441 }
1442 }
1443 }
1444 }
1445}