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

feanor_math/
group.rs
