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

use crate::algorithms::int_bisect;
use crate::divisibility::*;
use crate::pid::{EuclideanRing, EuclideanRingStore};
use crate::primitive_int::StaticRing;
use crate::ring::*;

/// Trait for principal ideal rings that additionally are local rings, i.e. have a unique
/// maximal ideal.
///
/// Note that in this case, the unique maximal ideal is clearly generated by a single element.
/// Such an element can be accessed via [`PrincipalLocalRing::max_ideal_gen()`]. Equivalently,
/// a principal local ring can be characterized by the property that for any elements `x, y`,
/// either `x | y` or `y | x`.
///
/// Principal local rings are also valuation rings, i.e. have a function `val: R -> ZZ_>0 u {∞}`
/// that satisfies `val(xy) = val(x) + val(y)`, `val(x + y) >= min(val(x), val(y))` and if `val(x)
/// >= val(y)` then `y | x`. This can be accessed using [`PrincipalLocalRing::valuation()`].
#[stability::unstable(feature = "enable")]
pub trait PrincipalLocalRing: EuclideanRing {
    /// Returns a generator `p` or the unique maximal ideal `(p)` of this ring.
    ///
    /// In other words, for each element `x` we have either that `p | x` or `x | 1`.
    fn max_ideal_gen(&self) -> &Self::Element;

    /// Returns the smallest nonnegative integer `e` such that `p^e = 0` where `p` is
    /// the generator of the maximal ideal.
    fn nilpotent_power(&self) -> Option<usize>;

    /// Returns the largest nonnegative integer `e` such that `p^e | x` where `p` is
    /// the generator of the maximal ideal.
    fn valuation(&self, x: &Self::Element) -> Option<usize> {
        assert!(self.is_noetherian());
        if self.is_zero(x) {
            return None;
        }
        let ring = RingRef::new(self);
        return Some(int_bisect::find_root_floor(&StaticRing::<i64>::RING, 0, |e| {
            if *e < 0
                || ring
                    .checked_div(x, &ring.pow(ring.clone_el(ring.max_ideal_gen()), *e as usize))
                    .is_some()
            {
                -1
            } else {
                1
            }
        }) as usize);
    }
}

/// [`RingStore`] for [`PrincipalLocalRing`]
#[stability::unstable(feature = "enable")]
pub trait PrincipalLocalRingStore: EuclideanRingStore
where
    Self::Type: PrincipalLocalRing,
{
    delegate! { PrincipalLocalRing, fn max_ideal_gen(&self) -> &El<Self> }
    delegate! { PrincipalLocalRing, fn valuation(&self, x: &El<Self>) -> Option<usize> }
    delegate! { PrincipalLocalRing, fn nilpotent_power(&self) -> Option<usize> }
}

impl<R> PrincipalLocalRingStore for R
where
    R: RingStore,
    R::Type: PrincipalLocalRing,
{
}