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

use crate::integer::*;
use crate::primitive_int::StaticRing;
use crate::ring::*;

#[stability::unstable(feature = "enable")]
pub fn erathostenes(B: u64) -> Vec<u64> {
    let mut primes = Vec::new();
    primes.push(2);
    let mut list = Vec::new();
    list.resize((B / 2) as usize, true);
    for i in 1..(B / 2) {
        let n = i * 2 + 1;
        if list[i as usize] {
            primes.push(n);
            for k in 1..(((B - 1) / n - 1) / 2 + 1) {
                let j = ((2 * k + 1) * n - 1) / 2;
                list[j as usize] = false;
            }
        }
    }
    return primes;
}

#[stability::unstable(feature = "enable")]
pub fn enumerate_primes<I>(ZZ: I, B: &El<I>) -> Vec<El<I>>
where
    I: RingStore,
    I::Type: IntegerRing,
{
    let bound = int_cast(ZZ.clone_el(B), StaticRing::<i128>::RING, &ZZ) as u64;
    erathostenes(bound)
        .into_iter()
        .map(|p| int_cast(p as i128, &ZZ, StaticRing::<i128>::RING))
        .collect()
}

#[cfg(test)]
use crate::DEFAULT_PROBABILISTIC_REPETITIONS;
#[cfg(test)]
use crate::algorithms;

#[test]
fn test_enumerate_primes() {
    assert_eq!(vec![2], erathostenes(3));
    assert_eq!(vec![2, 3], erathostenes(4));
    assert_eq!(vec![2, 3, 5, 7, 11, 13, 17, 19], erathostenes(20));
    assert_eq!(vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31], erathostenes(32));
}

#[test]
fn test_enumerate_primes_large() {
    for p in enumerate_primes(&StaticRing::<i64>::RING, &100000) {
        assert!(algorithms::miller_rabin::is_prime(
            &StaticRing::<i64>::RING,
            &p,
            DEFAULT_PROBABILISTIC_REPETITIONS
        ));
    }
}