以下算法已实现

• 快速傅里叶变换，包括对二的幂次情况的Cooley-Tuckey算法的优化实现，对任意长度的Bluestein算法的实现，以及基于Cooley-Tuckey算法的因子FFT实现。傅里叶变换适用于所有具有合适单位根的环，特别是复数C和合适的有限环Fq。
• 用于快速卷积的Karatsuba算法的优化变体。
• 用于有限域上分解多项式的Cantor-Zassenhaus算法的实现。
• 有理数/整数上的多项式分解（使用Hensel提升）和数域上的多项式分解。
• Lenstra的椭圆曲线算法分解整数（目前非常慢）。
• 用于格减小的LLL算法。
• 主理想环上的基本线性代数。
• 用于检查整数素性的Miller-Rabin测试。
• 基于婴儿步-巨人步和分解算法计算任意离散对数。
• Faugere的F4算法计算Gröbner基。

遗憾的是，目前对无限环（整数、有理数、数域）上的多项式操作非常慢，因为有效的实现需要大量小心以防止系数膨胀，而我没有时间和需求去投资。

最重要的缺失功能

• 矩阵和线性代数的全面处理。目前只有矩阵和线性代数的一个非常简约的抽象crate::matrix，主要供内部使用。
• 对无限环上的多项式进行仔细处理，主要使用专门实现以防止系数膨胀。
• 格减小和LLL算法。这也可能是上述点所需的内容。现在已实现！
• 更仔细设计的内存分配抽象（最好是使用新的crate memory-provider 或类似）。现在使用Rust的allocator-api以及feanor-mempool！
• 更多的数论算法，例如计算Galois群。我还没有确定在哪里划线，因为我认为高级数论算法（椭圆曲线、类群、...）不在这个项目的范围之内。技术上我会把整数分解包括在内，但它对其他算法来说太重要了。

语义版本

在版本 1..x.x 中，库使用了不一致的版本方案。现在已修复，并且从版本 2..x.x 开始使用语义版本，如Cargo手册中所述。请注意，所有标记为#[stability::unstable]的rust库中的项目都免于语义版本。换句话说，这些结构/特质/函数接口的破坏性更改只会增加次要版本号。请注意，除非激活了功能 unstable-enable，否则这些更改对其他crate不可见。

类似项目

最近我了解到一个名为 Symbolica 的项目，它与 Rust 中的符号计算方法类似。与主要用于数论计算的 feanor-math 不同，Symbolica 主要关注多变量多项式（包括浮点数）的计算，在这个领域比 feanor-math 更优化。如果它更适合您的用例，不妨去看看！我个人认为这是一个非常棒的项目。

示例

使用环

以下是一个如何使用库的简单示例，我们在这里实现了费马素性检验

use feanor_math::homomorphism::*;
use feanor_math::assert_el_eq;
use feanor_math::ring::*;
use feanor_math::primitive_int::*;
use feanor_math::rings::zn::zn_big::*;
use feanor_math::rings::zn::*;
use feanor_math::rings::finite::*;
use feanor_math::algorithms;
use oorandom;

fn fermat_is_prime(n: i64) -> bool {
    // the Fermat primality test is based on the observation that a^n == a mod n if n
    // is a prime; On the other hand, if n is not prime, we hope that there are many
    // a such that this is not the case. 
    // Note that this is not always the case, and so more advanced primality tests should 
    // be used in practice. This is just a proof of concept.

    let ZZ = StaticRing::<i64>::RING;
    let Zn = Zn::new(ZZ, n); // the ring Z/nZ

    // check for 6 random a whether a^n == a mod n
    let mut rng = oorandom::Rand64::new(0);
    for _ in 0..6 {
        let a = Zn.random_element(|| rng.rand_u64());
        let a_n = Zn.pow(Zn.clone_el(&a), n as usize);
        if !Zn.eq_el(&a, &a_n) {
            return false;
        }
    }
    return true;
}

assert!(algorithms::miller_rabin::is_prime(StaticRing::<i64>::RING, &91, 6) == fermat_is_prime(91));

如果我们想支持任意整数环 - 例如 BigIntRing::RING，它是对任意精度整数的简单实现 - 我们可以将函数泛型化

use feanor_math::homomorphism::*;
use feanor_math::ring::*;
use feanor_math::integer::*;
use feanor_math::integer::*;
use feanor_math::rings::zn::zn_big::*;
use feanor_math::rings::zn::*;
use feanor_math::rings::finite::*;
use feanor_math::algorithms;

use oorandom;

fn fermat_is_prime<R>(ZZ: R, n: El<R>) -> bool 
    where R: RingStore, R::Type: IntegerRing
{
    // the Fermat primality test is based on the observation that a^n == a mod n if n
    // is a prime; On the other hand, if n is not prime, we hope that there are many
    // a such that this is not the case. 
    // Note that this is not always the case, and so more advanced primality tests should 
    // be used in practice. This is just a proof of concept.

    // ZZ is not guaranteed to be Copy anymore, so use reference instead
    let Zn = Zn::new(&ZZ, ZZ.clone_el(&n)); // the ring Z/nZ

    // check for 6 random a whether a^n == a mod n
    let mut rng = oorandom::Rand64::new(0);
    for _ in 0..6 {
        let a = Zn.random_element(|| rng.rand_u64());
        // use a generic square-and-multiply powering function that works with any implementation
        // of integers
        let a_n = Zn.pow_gen(Zn.clone_el(&a), &n, &ZZ);
        if !Zn.eq_el(&a, &a_n) {
            return false;
        }
    }
    return true;
}

// the miller-rabin primality test is implemented in feanor_math::algorithms, so we can
// check our implementation
let n = BigIntRing::RING.int_hom().map(91);
assert!(algorithms::miller_rabin::is_prime(BigIntRing::RING, &n, 6) == fermat_is_prime(BigIntRing::RING, n));

这个函数现在可以与任何实现了 IntegerRing 的环一起工作，它是 RingBase 的子特质。

实现环

要实现自定义环，只需创建一个结构体并添加一个 impl RingBase 和一个 impl CanIsoFromTo<Self> - 就这么简单！假设我们想提供自己实现的有限二元域 F2，可以这样做。

use feanor_math::homomorphism::*;
use feanor_math::integer::*;
use feanor_math::assert_el_eq;
use feanor_math::ring::*;

#[derive(PartialEq)]
struct F2Base;

impl RingBase for F2Base {
   
    type Element = u8;

    fn clone_el(&self, val: &Self::Element) -> Self::Element {
        *val
    }

    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        *lhs = (*lhs + rhs) % 2;
    }
    
    fn negate_inplace(&self, lhs: &mut Self::Element) {
        *lhs = (2 - *lhs) % 2;
    }

    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        *lhs = (*lhs * rhs) % 2;
    }
    
    fn from_int(&self, value: i32) -> Self::Element {
        // make sure that we handle negative numbers correctly
        (((value % 2) + 2) % 2) as u8
    }

    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
        // elements are always represented by 0 or 1
        *lhs == *rhs
    }

    fn characteristic<I>(&self, ZZ: &I) -> Option<El<I>>
        where I: IntegerRingStore, I::Type: IntegerRing
    {
        Some(ZZ.int_hom().map(2))
    }

    fn is_commutative(&self) -> bool { true }
    fn is_noetherian(&self) -> bool { true }

    fn dbg<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(out, "{}", *value)
    }
}

pub const F2: RingValue<F2Base> = RingValue::from(F2Base);

assert_el_eq!(F2, F2.int_hom().map(1), F2.add(F2.one(), F2.zero()));

一起使用

这个特质的其中一个主要目标是为了使嵌套环变得容易，因此在环的范畴上实现了一个函子。经典的例子是对于任何环 R 都存在的多项式环 R[X]。由于在这种情况下我们既在使用也在实现环，我们应该使用框架的两面。例如，一个简单的多项式环实现可能看起来像这样。

use feanor_math::assert_el_eq;
use feanor_math::ring::*;
use feanor_math::integer::*;
use feanor_math::homomorphism::*;
use feanor_math::rings::zn::*;
use std::cmp::{min, max};

pub struct MyPolyRing<R: RingStore> {
    base_ring: R
}

impl<R: RingStore> PartialEq for MyPolyRing<R> {

    fn eq(&self, other: &Self) -> bool {
        self.base_ring.get_ring() == other.base_ring.get_ring()
    }
}

impl<R: RingStore> RingBase for MyPolyRing<R> {

    // in a real implementation, we might want to wrap this in a newtype, to avoid
    // exposing the vector interface (although exposing that interface might be intended - 
    // the crate does not judge whether this is a good idea)
    type Element = Vec<El<R>>;

    fn clone_el(&self, el: &Self::Element) -> Self::Element {
        el.iter().map(|x| self.base_ring.clone_el(x)).collect()
    }

    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        for i in 0..min(lhs.len(), rhs.len()) {
            self.base_ring.add_assign_ref(&mut lhs[i], &rhs[i]);
        }
        for i in lhs.len()..rhs.len() {
            lhs.push(self.base_ring.clone_el(&rhs[i]))
        }
    }

    fn negate_inplace(&self, val: &mut Self::Element) {
        for x in val {
            self.base_ring.negate_inplace(x);
        }
    }

    fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
        // this is just for demonstration purposes - note that the length of the vectors would slowly increase,
        // even if the degree of the polynomials doesn't
        let mut result = (0..(lhs.len() + rhs.len())).map(|_| self.base_ring.zero()).collect::<Vec<_>>();
        for i in 0..lhs.len() {
            for j in 0..rhs.len() {
                self.base_ring.add_assign(&mut result[i + j], self.base_ring.mul_ref(&lhs[i], &rhs[j]));
            }
        }
        return result;
    }

    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        *lhs = self.mul_ref(lhs, &rhs);
    }

    fn from_int(&self, x: i32) -> Self::Element {
        vec![self.base_ring.int_hom().map(x)]
    }

    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
        let zero = self.base_ring.zero();
        for i in 0..max(lhs.len(), rhs.len()) {
            if !self.base_ring.eq_el(lhs.get(i).unwrap_or(&zero), rhs.get(i).unwrap_or(&zero)) {
                return false;
            }
        }
        return true;
    }

    fn is_commutative(&self) -> bool {
        self.base_ring.is_commutative()
    }

    fn is_noetherian(&self) -> bool {
        // by Hilbert's basis theorem
        self.base_ring.is_noetherian()
    }

    fn dbg(&self, val: &Self::Element, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        // this is just for demonstration purposes - note that this prints zero coefficients
        for i in 0..(val.len() - 1) {
            write!(f, "{} * X^{} + ", self.base_ring.format(&val[i]), i)?;
        }
        write!(f, "{} * X^{}", self.base_ring.format(val.last().unwrap()), val.len() - 1)
    }

    fn characteristic<I>(&self, ZZ: &I) -> Option<El<I>>
        where I: IntegerRingStore, I::Type: IntegerRing
    {
        self.base_ring.get_ring().characteristic(ZZ)
    }
}

// in a real implementation, we definitely should implement also `feanor_math::rings::poly::PolyRing`, and
// possibly other traits (`CanHomFrom<other polynomial rings>`, `RingExtension`, `DivisibilityRing`, `EuclideanRing`)

let base = zn_static::F17;
// we do not use the `RingBase`-implementor directly, but wrap it in a `RingStore`;
// note that here, this is not strictly necessary, but still recommended
let ring = RingValue::from(MyPolyRing { base_ring: base });
let x = vec![0, 1];
let f = ring.add_ref(&x, &ring.int_hom().map(8));
let g = ring.add_ref(&x, &ring.int_hom().map(7));
let h = ring.add(ring.mul_ref(&x, &x), ring.add_ref(&ring.mul_ref(&x, &ring.int_hom().map(-2)), &ring.int_hom().map(5)));
assert_el_eq!(ring, h, ring.mul(f, g));

RingBase 与 RingStore

特质 RingBase 的设计是为了提供一个简单的方式来定义环结构。因此，它提供了一个具有所有环操作（如加法、乘法和等式测试）的基本接口。在许多情况下，定义了基本操作的变体以利用移动语义和内存重用。然而，它们通常具有默认实现，以简化创建新的环。

另一方面，RingStore 是任何可以访问底层 RingBase 对象的对象。这个特质提供了所有环操作的默认实现，这些实现只是将调用委托给底层 RingBase 对象。在正常情况下，这个特质不应为自定义类型实现。

当我们开始嵌套环时，这种分离的主要优势变得明显。比如说，我们有一个基于底层环类型的环类型，例如在基环 R 上的多项式环 PolyRing<R>。在这种情况下，PolyRing 实现 RingBase，但底层环 R 被限制为必须是 RingStore。因此，类型如 PolyRing<R>、PolyRing<&&R> 和 PolyRing<Box<R>> 都可以等价使用，这提供了很大的灵活性，但仍然可以与昂贵的克隆环和零大小环一起工作。

trait RingBase {

    type Element<'a> where Self: 'a;

    ...
}

struct Zn<I: IntegerRingStore> {
    integer_ring: I,
    modulus: El<I>
}

fn galois_field(q: i64, exponent: usize) -> RingExtension<ZnBarett<MempoolBigIntRing>> {
    ...
}