feanor-math 3.5.18

A library for number theory, providing implementations for arithmetic in various rings and algorithms working on them.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use crate::ring::*;
use crate::rings::finite::*;

/// Operation on a ring `R` that only makes sense if `R` implements
/// the trait [`crate::rings::finite::FiniteRing`].
///
/// Used through the trait [`FiniteRingSpecializable`].
#[stability::unstable(feature = "enable")]
pub trait FiniteRingOperation<R>
where
    R: ?Sized,
{
    type Output;

    /// Runs the operations, with the additional assumption that `R: FiniteRing`.
    fn execute(self) -> Self::Output
    where
        R: FiniteRing;

    /// Runs the operation in case that `R` is not a [`FiniteRing`].
    fn fallback(self) -> Self::Output;
}

/// Trait for ring types that can check (at compile time) whether they implement
/// [`crate::rings::finite::FiniteRing`].
///
/// This serves as a workaround while specialization is not properly supported.
#[stability::unstable(feature = "enable")]
pub trait FiniteRingSpecializable: RingBase {
    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output;

    fn is_finite_ring() -> bool {
        struct CheckIsFinite;
        impl<R: ?Sized + RingBase> FiniteRingOperation<R> for CheckIsFinite {
            type Output = bool;
            fn execute(self) -> Self::Output
            where
                R: FiniteRing,
            {
                true
            }
            fn fallback(self) -> Self::Output { false }
        }
        return Self::specialize(CheckIsFinite);
    }
}

#[cfg(test)]
use crate::homomorphism::*;
#[cfg(test)]
use crate::integer::*;
#[cfg(test)]
use crate::rings::extension::extension_impl::*;
#[cfg(test)]
use crate::rings::extension::galois_field::*;
#[cfg(test)]
use crate::rings::extension::*;
#[cfg(test)]
use crate::rings::field::*;
#[cfg(test)]
use crate::rings::rational::*;
#[cfg(test)]
use crate::rings::zn::*;

#[test]
fn test_specialize_finite_field() {
    struct Verify<'a, R>(&'a R, i32)
    where
        R: ?Sized + RingBase;

    impl<'a, R: ?Sized> FiniteRingOperation<R> for Verify<'a, R>
    where
        R: RingBase,
    {
        type Output = bool;

        fn execute(self) -> bool
        where
            R: FiniteRing,
        {
            assert_el_eq!(
                BigIntRing::RING,
                BigIntRing::RING.int_hom().map(self.1),
                self.0.size(&BigIntRing::RING).unwrap()
            );
            return true;
        }

        fn fallback(self) -> Self::Output { return false; }
    }

    let ring = zn_64::Zn::new(7).as_field().ok().unwrap();
    assert!(<AsFieldBase<zn_64::Zn>>::specialize(Verify(ring.get_ring(), 7)));

    let ring = GaloisField::new(3, 2);
    assert!(GaloisFieldBase::specialize(Verify(ring.get_ring(), 9)));

    let ring = GaloisField::new(3, 2).into().unwrap_self();
    assert!(<AsFieldBase<FreeAlgebraImpl<_, _, _, _>>>::specialize(Verify(
        ring.get_ring(),
        9
    )));

    let ring = RationalField::new(BigIntRing::RING);
    assert!(!<RationalFieldBase<_>>::specialize(Verify(ring.get_ring(), 0)));

    let QQ = RationalField::new(BigIntRing::RING);
    let ring = FreeAlgebraImpl::new(&QQ, 2, [QQ.neg_one()]).as_field().ok().unwrap();
    assert!(!<AsFieldBase<FreeAlgebraImpl<_, _, _, _>>>::specialize(Verify(
        ring.get_ring(),
        0
    )));

    let base_ring = GaloisField::new(3, 2).into().unwrap_self();
    let ring = FreeAlgebraImpl::new(&base_ring, 3, [base_ring.neg_one(), base_ring.one()])
        .as_field()
        .ok()
        .unwrap();
    assert!(<AsFieldBase<FreeAlgebraImpl<_, _, _, _>>>::specialize(Verify(
        ring.get_ring(),
        729
    )));
}