haar_lib/num/
ff.rs

1//! 有限体
2use crate::num::arithmetic::Arithmetic;
3use std::ops::Neg;
4
5/// 有限体
6#[allow(clippy::wrong_self_convention)]
7pub trait FF: Clone {
8    /// 有限体の元の型
9    type Element: FFElem;
10    /// `u64`から生成する。
11    fn from_u64(&self, a: u64) -> Self::Element;
12    /// `i64`から生成する。
13    fn from_i64(&self, a: i64) -> Self::Element;
14    /// `a/b`を生成する。
15    fn frac(&self, a: i64, b: i64) -> Self::Element {
16        self.from_i64(a) / self.from_i64(b)
17    }
18    fn modulo(&self) -> u32;
19}
20
21/// 有限体の元
22pub trait FFElem: Sized + Copy + Neg<Output = Self> + PartialEq + Arithmetic {
23    /// 内部の値を取り出す。
24    fn value(self) -> u32;
25    /// 剰余の除数を返す。
26    fn modulo(self) -> u32;
27    /// `self`の`p`乗を返す。
28    fn pow(self, p: u64) -> Self;
29    /// `self`の乗法の逆元を返す。
30    fn inv(self) -> Self {
31        self.pow(self.modulo() as u64 - 2)
32    }
33}
haar_lib/num/ff.rs

haar_lib/num/
ff.rs
