feanor_math/
group.rs

1use std::fmt::Debug;
2use std::hash::{Hash, Hasher};
3use std::ops::Deref;
4
5use feanor_serde::newtype_struct::{DeserializeSeedNewtypeStruct, SerializableNewtypeStruct};
6use serde::de::DeserializeSeed;
7use serde::{Deserialize, Deserializer, Serialize, Serializer};
8
9use crate::algorithms::sqr_mul::generic_abs_square_and_multiply;
10use crate::divisibility::{DivisibilityRing, DivisibilityRingStore};
11use crate::integer::BigIntRing;
12use crate::ordered::OrderedRingStore;
13use crate::ring::*;
14use crate::serialization::{DeserializeWithRing, SerializableElementRing, SerializeWithRing};
15
16/// Trait for implementations of generic abelian groups, for which only
17/// the group operation, equality testing and computing hash values is supported.
18///
19/// These groups from the model for which most dlog algorithms have been developed.
20/// Note that if your group is actually the additive group of a ring, it is very
21/// likely that you can solve dlog much more efficiently by using [`crate::algorithms::linsolve`].
22///
23/// The design mirrors [`RingBase`] and [`RingStore`], with [`AbelianGroupStore`] being
24/// the counterpart to [`RingStore`].
25#[stability::unstable(feature = "enable")]
26pub trait AbelianGroupBase: PartialEq {
27    /// Type used to represent elements of this group.
28    type Element;
29
30    /// Clones an element of the group.
31    fn clone_el(&self, x: &Self::Element) -> Self::Element;
32
33    /// Checks whether two group elements are equal.
34    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool;
35
36    /// Applies the group operation to two elements.
37    fn op(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element;
38
39    /// Applies the group operation to two elements.
40    ///
41    /// As opposed to [`AbelianGroupBase::op()`], this takes both arguments by reference.
42    fn op_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
43        self.op(self.clone_el(lhs), self.clone_el(rhs))
44    }
45
46    /// Applies the group operation to two elements.
47    ///
48    /// As opposed to [`AbelianGroupBase::op()`], this takes the second argument by reference.
49    fn op_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { self.op(lhs, self.clone_el(rhs)) }
50
51    /// Computes the inverse of the give element, i.e. the unique group element `x^-1` such that
52    /// `x * x^-1` is the identity element.
53    fn inv(&self, x: &Self::Element) -> Self::Element;
54
55    /// Returns the identity element of the group, i.e. the unique element `1` such that
56    /// `x * 1 = x` for all group elements `x`.
57    fn identity(&self) -> Self::Element;
58
59    /// Hashes the group element.
60    ///
61    /// This should satisfy all the standard properties usually satisfied by hashing,
62    /// in particular it should be compatible with [`AbelianGroupBase::eq_el()`].
63    fn hash<H: Hasher>(&self, x: &Self::Element, hasher: &mut H);
64
65    /// Raises a group element to the given power, i.e. computes `x * x * ... * x`,
66    /// in total `e` times.
67    fn pow(&self, x: &Self::Element, e: &El<BigIntRing>) -> Self::Element {
68        let res = generic_abs_square_and_multiply(
69            self.clone_el(x),
70            e,
71            BigIntRing::RING,
72            |a| self.op_ref(&a, &a),
73            |a, b| self.op_ref_snd(b, a),
74            self.identity(),
75        );
76        if !BigIntRing::RING.is_neg(e) {
77            res
78        } else {
79            self.inv(&res)
80        }
81    }
82
83    /// Checks whether the given element is the identity element of the group.
84    ///
85    /// Equivalent to `group.eq_el(x, &group.identity())`, but may be faster.
86    fn is_identity(&self, x: &Self::Element) -> bool { self.eq_el(x, &self.identity()) }
87}
88
89/// Alias for the type of elements of a group underlying an `AbelianGroupStore`.
90#[stability::unstable(feature = "enable")]
91#[allow(type_alias_bounds)]
92pub type GroupEl<G: AbelianGroupStore> = <G::Type as AbelianGroupBase>::Element;
93
94/// Analogue of [`crate::delegate!`] for groups.
95#[macro_export]
96macro_rules! delegate_group {
97    ($base_trait:ty, fn $name:ident (&self, $($pname:ident: $ptype:ty),*) -> $rtype:ty) => {
98        #[doc = concat!(" See [`", stringify!($base_trait), "::", stringify!($name), "()`]")]
99        fn $name (&self, $($pname: $ptype),*) -> $rtype {
100            <Self::Type as $base_trait>::$name(self.get_group(), $($pname),*)
101        }
102    };
103    ($base_trait:ty, fn $name:ident (&self) -> $rtype:ty) => {
104        #[doc = concat!(" See [`", stringify!($base_trait), "::", stringify!($name), "()`]")]
105        fn $name (&self) -> $rtype {
106            <Self::Type as $base_trait>::$name(self.get_group())
107        }
108    };
109}
110
111/// Object provides access to a generic abelian group, as modelled by [`AbelianGroupBase`].
112///
113/// The design of [`AbelianGroupBase`] and [`AbelianGroupStore`] mirrors
114/// the design of [`RingBase`] and [`RingStore`]. See there for details.
115#[stability::unstable(feature = "enable")]
116pub trait AbelianGroupStore {
117    type Type: AbelianGroupBase;
118
119    fn get_group(&self) -> &Self::Type;
120
121    delegate_group! { AbelianGroupBase, fn clone_el(&self, el: &GroupEl<Self>) -> GroupEl<Self> }
122    delegate_group! { AbelianGroupBase, fn eq_el(&self, lhs: &GroupEl<Self>, rhs: &GroupEl<Self>) -> bool }
123    delegate_group! { AbelianGroupBase, fn op(&self, lhs: GroupEl<Self>, rhs: GroupEl<Self>) -> GroupEl<Self> }
124    delegate_group! { AbelianGroupBase, fn op_ref(&self, lhs: &GroupEl<Self>, rhs: &GroupEl<Self>) -> GroupEl<Self> }
125    delegate_group! { AbelianGroupBase, fn op_ref_snd(&self, lhs: GroupEl<Self>, rhs: &GroupEl<Self>) -> GroupEl<Self> }
126    delegate_group! { AbelianGroupBase, fn inv(&self, x: &GroupEl<Self>) -> GroupEl<Self> }
127    delegate_group! { AbelianGroupBase, fn identity(&self) -> GroupEl<Self> }
128    delegate_group! { AbelianGroupBase, fn pow(&self, x: &GroupEl<Self>, e: &El<BigIntRing>) -> GroupEl<Self> }
129    delegate_group! { AbelianGroupBase, fn is_identity(&self, x: &GroupEl<Self>) -> bool }
130
131    fn hash<H: Hasher>(&self, x: &GroupEl<Self>, hasher: &mut H) { self.get_group().hash(x, hasher) }
132}
133
134impl<G> AbelianGroupStore for G
135where
136    G: Deref,
137    G::Target: AbelianGroupStore,
138{
139    type Type = <G::Target as AbelianGroupStore>::Type;
140
141    fn get_group(&self) -> &Self::Type { (**self).get_group() }
142}
143
144/// Analogue of [`RingValue`] for groups.
145#[stability::unstable(feature = "enable")]
146#[repr(transparent)]
147#[derive(Serialize, Deserialize)]
148pub struct GroupValue<G: AbelianGroupBase> {
149    group: G,
150}
151
152impl<G: AbelianGroupBase> From<G> for GroupValue<G> {
153    fn from(value: G) -> Self { Self { group: value } }
154}
155
156impl<G: AbelianGroupBase + Sized> GroupValue<G> {
157    #[stability::unstable(feature = "enable")]
158    pub fn into(self) -> G { self.group }
159
160    #[stability::unstable(feature = "enable")]
161    pub fn from_ref<'a>(group: &'a G) -> &'a Self { unsafe { std::mem::transmute(group) } }
162}
163
164impl<G: AbelianGroupBase> AbelianGroupStore for GroupValue<G> {
165    type Type = G;
166
167    fn get_group(&self) -> &Self::Type { &self.group }
168}
169
170impl<G: AbelianGroupBase + Clone> Clone for GroupValue<G> {
171    fn clone(&self) -> Self {
172        Self {
173            group: self.group.clone(),
174        }
175    }
176}
177
178impl<G: AbelianGroupBase + Copy> Copy for GroupValue<G> {}
179
180/// The additive group of a ring, implements [`AbelianGroupBase`].
181///
182/// # Attention
183///
184/// It is unlikely that you want to use this, except for testing
185/// group-related algorithms.
186///
187/// In most cases, it does not make much sense to compute dlogs in the additive
188/// group of a ring using generic methods, since algorithms as in
189/// [`crate::algorithms::linsolve`] will be much faster.
190#[stability::unstable(feature = "enable")]
191pub struct AddGroupBase<R: RingStore>(pub R);
192
193/// [`AbelianGroupStore`] corresponding to [`AddGroupBase`].
194#[stability::unstable(feature = "enable")]
195#[allow(type_alias_bounds)]
196pub type AddGroup<R: RingStore> = GroupValue<AddGroupBase<R>>;
197
198/// The multiplicative group of a ring, implements [`AbelianGroupBase`].
199#[stability::unstable(feature = "enable")]
200#[derive(Serialize, Deserialize)]
201pub struct MultGroupBase<R: RingStore>(R);
202
203/// [`AbelianGroupStore`] corresponding to [`MultGroupBase`].
204#[stability::unstable(feature = "enable")]
205#[allow(type_alias_bounds)]
206pub type MultGroup<R: RingStore> = GroupValue<MultGroupBase<R>>;
207
208/// Elements from the multiplicative group of `R`.
209#[stability::unstable(feature = "enable")]
210pub struct MultGroupEl<R: RingStore>(El<R>);
211
212impl<R: RingStore> PartialEq for AddGroupBase<R>
213where
214    R::Type: HashableElRing,
215{
216    fn eq(&self, other: &Self) -> bool { self.0.get_ring() == other.0.get_ring() }
217}
218
219impl<R: RingStore> AbelianGroupBase for AddGroupBase<R>
220where
221    R::Type: HashableElRing,
222{
223    type Element = El<R>;
224
225    fn clone_el(&self, x: &Self::Element) -> Self::Element { self.0.clone_el(x) }
226    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { self.0.eq_el(lhs, rhs) }
227    fn op(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { self.0.add(lhs, rhs) }
228    fn inv(&self, x: &Self::Element) -> Self::Element { self.0.negate(self.0.clone_el(x)) }
229    fn identity(&self) -> Self::Element { self.0.zero() }
230    fn hash<H: Hasher>(&self, x: &Self::Element, hasher: &mut H) { self.0.hash(x, hasher) }
231}
232
233impl<R: RingStore> AddGroup<R>
234where
235    R::Type: HashableElRing,
236{
237    #[stability::unstable(feature = "enable")]
238    pub fn new(ring: R) -> Self { Self::from(AddGroupBase(ring)) }
239}
240
241impl<R: RingStore + Clone> Clone for AddGroupBase<R>
242where
243    R::Type: HashableElRing,
244{
245    fn clone(&self) -> Self { Self(self.0.clone()) }
246}
247
248impl<R: RingStore> PartialEq for MultGroupBase<R>
249where
250    R::Type: HashableElRing + DivisibilityRing,
251{
252    fn eq(&self, other: &Self) -> bool { self.0.get_ring() == other.0.get_ring() }
253}
254
255impl<R: RingStore> AbelianGroupBase for MultGroupBase<R>
256where
257    R::Type: HashableElRing + DivisibilityRing,
258{
259    type Element = MultGroupEl<R>;
260
261    fn clone_el(&self, x: &Self::Element) -> Self::Element { MultGroupEl(self.0.clone_el(&x.0)) }
262    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { self.0.eq_el(&lhs.0, &rhs.0) }
263    fn inv(&self, x: &Self::Element) -> Self::Element { MultGroupEl(self.0.invert(&x.0).unwrap()) }
264    fn identity(&self) -> Self::Element { MultGroupEl(self.0.one()) }
265    fn hash<H: Hasher>(&self, x: &Self::Element, hasher: &mut H) { self.0.hash(&x.0, hasher) }
266    fn op(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { MultGroupEl(self.0.mul(lhs.0, rhs.0)) }
267}
268
269impl<R: RingStore> SerializableElementGroup for MultGroupBase<R>
270where
271    R::Type: HashableElRing + DivisibilityRing + SerializableElementRing,
272{
273    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
274    where
275        S: Serializer,
276    {
277        SerializableNewtypeStruct::new("MultGroupEl", SerializeWithRing::new(&el.0, &self.0)).serialize(serializer)
278    }
279
280    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
281    where
282        D: Deserializer<'de>,
283    {
284        DeserializeSeedNewtypeStruct::new("MultGroupEl", DeserializeWithRing::new(&self.0))
285            .deserialize(deserializer)
286            .map(|x| MultGroupEl(x))
287    }
288}
289
290impl<R: RingStore> Clone for MultGroupBase<R>
291where
292    R: Clone,
293    R::Type: HashableElRing + DivisibilityRing,
294{
295    fn clone(&self) -> Self { Self(self.0.clone()) }
296}
297
298impl<R: RingStore> Copy for MultGroupBase<R>
299where
300    R: Copy,
301    R::Type: HashableElRing + DivisibilityRing,
302{
303}
304
305impl<R: RingStore> Debug for MultGroupBase<R>
306where
307    R::Type: Debug + HashableElRing + DivisibilityRing,
308{
309    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "({:?})*", self.0.get_ring()) }
310}
311
312impl<R: RingStore> Clone for MultGroupEl<R>
313where
314    R::Type: HashableElRing + DivisibilityRing,
315    El<R>: Clone,
316{
317    fn clone(&self) -> Self { Self(self.0.clone()) }
318}
319
320impl<R: RingStore> Debug for MultGroupEl<R>
321where
322    R::Type: HashableElRing + DivisibilityRing,
323    El<R>: Debug,
324{
325    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{:?}", self.0) }
326}
327
328impl<R: RingStore> MultGroupBase<R>
329where
330    R::Type: HashableElRing + DivisibilityRing,
331{
332    #[stability::unstable(feature = "enable")]
333    pub fn new(ring: R) -> Self {
334        assert!(ring.is_commutative());
335        return Self(ring);
336    }
337
338    #[stability::unstable(feature = "enable")]
339    pub fn underlying_ring(&self) -> &R { &self.0 }
340
341    /// If `x` is contained in `R*`, returns a [`MultGroupEl`] representing
342    /// `x`. Otherwise, `None` is returned.
343    #[stability::unstable(feature = "enable")]
344    pub fn from_ring_el(&self, x: El<R>) -> Option<MultGroupEl<R>> {
345        if self.0.is_unit(&x) { Some(MultGroupEl(x)) } else { None }
346    }
347
348    /// Returns the ring element represented by the given group element.
349    #[stability::unstable(feature = "enable")]
350    pub fn as_ring_el<'a>(&self, x: &'a MultGroupEl<R>) -> &'a El<R> { &x.0 }
351}
352
353impl<R: RingStore> MultGroup<R>
354where
355    R::Type: HashableElRing + DivisibilityRing,
356{
357    #[stability::unstable(feature = "enable")]
358    pub fn new(ring: R) -> Self { Self::from(MultGroupBase::new(ring)) }
359
360    #[stability::unstable(feature = "enable")]
361    pub fn underlying_ring(&self) -> &R { self.get_group().underlying_ring() }
362
363    /// If `x` is contained in `R*`, returns a [`MultGroupEl`] representing
364    /// `x`. Otherwise, `None` is returned.
365    #[stability::unstable(feature = "enable")]
366    pub fn from_ring_el(&self, x: El<R>) -> Option<MultGroupEl<R>> { self.get_group().from_ring_el(x) }
367
368    /// Returns the ring element represented by the given group element.
369    #[stability::unstable(feature = "enable")]
370    pub fn as_ring_el<'a>(&self, x: &'a MultGroupEl<R>) -> &'a El<R> { self.get_group().as_ring_el(x) }
371}
372
373#[stability::unstable(feature = "enable")]
374pub struct HashableGroupEl<G: AbelianGroupStore> {
375    group: G,
376    el: GroupEl<G>,
377}
378
379impl<G: AbelianGroupStore> HashableGroupEl<G> {
380    #[stability::unstable(feature = "enable")]
381    pub fn new(group: G, el: GroupEl<G>) -> Self { Self { group, el } }
382}
383
384impl<G: AbelianGroupStore> PartialEq for HashableGroupEl<G> {
385    fn eq(&self, other: &Self) -> bool { self.group.eq_el(&self.el, &other.el) }
386}
387
388impl<G: AbelianGroupStore> Eq for HashableGroupEl<G> {}
389
390impl<G: AbelianGroupStore> Hash for HashableGroupEl<G> {
391    fn hash<H: Hasher>(&self, state: &mut H) { self.group.hash(&self.el, state) }
392}
393
394/// Trait for rings whose elements can be serialized.
395///
396/// Serialization and deserialization mostly follow the principles of the `serde` crate, with
397/// the main difference that ring elements cannot be serialized/deserialized on their own, but
398/// only w.r.t. a specific ring.
399#[stability::unstable(feature = "enable")]
400pub trait SerializableElementGroup: AbelianGroupBase {
401    /// Deserializes an element of this ring from the given deserializer.
402    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
403    where
404        D: Deserializer<'de>;
405
406    /// Serializes an element of this ring to the given serializer.
407    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
408    where
409        S: Serializer;
410}
411
412/// Wrapper of a group that implements [`serde::DeserializationSeed`] by trying to deserialize
413/// an element w.r.t. the wrapped group.
414#[stability::unstable(feature = "enable")]
415#[derive(Clone)]
416pub struct DeserializeWithGroup<G: AbelianGroupStore>
417where
418    G::Type: SerializableElementGroup,
419{
420    group: G,
421}
422
423impl<G> DeserializeWithGroup<G>
424where
425    G: AbelianGroupStore,
426    G::Type: SerializableElementGroup,
427{
428    #[stability::unstable(feature = "enable")]
429    pub fn new(group: G) -> Self { Self { group } }
430}
431
432impl<'de, G> DeserializeSeed<'de> for DeserializeWithGroup<G>
433where
434    G: AbelianGroupStore,
435    G::Type: SerializableElementGroup,
436{
437    type Value = GroupEl<G>;
438
439    fn deserialize<D>(self, deserializer: D) -> Result<Self::Value, D::Error>
440    where
441        D: Deserializer<'de>,
442    {
443        self.group.get_group().deserialize(deserializer)
444    }
445}
446
447/// Wraps a group and a reference to one of its elements. Implements [`serde::Serialize`]
448/// and will serialize the element w.r.t. the group.
449#[stability::unstable(feature = "enable")]
450pub struct SerializeWithGroup<'a, G: AbelianGroupStore>
451where
452    G::Type: SerializableElementGroup,
453{
454    group: G,
455    el: &'a GroupEl<G>,
456}
457
458impl<'a, G: AbelianGroupStore> SerializeWithGroup<'a, G>
459where
460    G::Type: SerializableElementGroup,
461{
462    #[stability::unstable(feature = "enable")]
463    pub fn new(el: &'a GroupEl<G>, group: G) -> Self { Self { el, group } }
464}
465
466impl<'a, G: AbelianGroupStore> Serialize for SerializeWithGroup<'a, G>
467where
468    G::Type: SerializableElementGroup,
469{
470    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
471    where
472        S: Serializer,
473    {
474        self.group.get_group().serialize(self.el, serializer)
475    }
476}
477
478/// Wraps a ring and a one of its elements. Implements [`serde::Serialize`] and
479/// will serialize the element w.r.t. the ring.
480#[stability::unstable(feature = "enable")]
481pub struct SerializeOwnedWithGroup<G: AbelianGroupStore>
482where
483    G::Type: SerializableElementGroup,
484{
485    group: G,
486    el: GroupEl<G>,
487}
488
489impl<G: AbelianGroupStore> SerializeOwnedWithGroup<G>
490where
491    G::Type: SerializableElementGroup,
492{
493    #[stability::unstable(feature = "enable")]
494    pub fn new(el: GroupEl<G>, group: G) -> Self { Self { el, group } }
495}
496
497impl<G: AbelianGroupStore> Serialize for SerializeOwnedWithGroup<G>
498where
499    G::Type: SerializableElementGroup,
500{
501    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
502    where
503        S: Serializer,
504    {
505        self.group.get_group().serialize(&self.el, serializer)
506    }
507}
feanor_math/group.rs

feanor_math/
group.rs
