CPLib.ZP
Defined in cp-library@0.14.0
素数pを法とする整数の環の型ZP pを与えるモジュール。
素数pは静的でなければならない(コンパイル時に決まる必要がある)。
制約:pは素数, p < 2^31
素数pは型パラメータとして与える。例として、p = 17 としたい場合、
- 空の型(フィールドを持たないunboxedな型)
P17を作成:type P17 = unbox struct {}. P17 : PrimeProviderを実装する。この際PrimeProvider::value関数で17を返すようにする:value = |_| 17_U32;
するとZP P17が環"Z/(17)"を表す型となる。
幾つかの有名な素数nに対する PrimeProvider Pn はこのモジュールに定義されている。
使用例:
module Main;
import CPLib.ZP;
type P17 = unbox struct {};
impl P17 : PrimeProvider {
create = P17 {};
value = |p| 17_U32;
}
main : IO ();
main = (
let zp = ZP::make(-5) : ZP P17;
let zp = zp * zp;
assert_eq(|_|"case 1", zp.@value, 8_U32);; // (-5)*(-5) = 25 = 8 mod 17
pure()
);
Values
namespace CPLib.ZP
fft
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::FFTDirection -> Std::Array (CPLib.ZP::ZP p) -> Std::Array (CPLib.ZP::ZP p)
ZP p型の配列に対して高速フーリエ変換を行う
制約:2^c | (p-1) かつ |x| <= 2^c なる c が存在する
計算量:O(n log n + sqrt(p))、n = |x|。pがこのモジュールに定義されている素数ならO(n log n)
Parameters
dir: FFTの方向(順方向か逆方向か)x:ZP p型の配列
inv
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p -> CPLib.ZP::ZP p
ZP pの逆元を求める。
0を与えた場合はプログラムを終了する。
計算量:O(log p)
Parameters
x:ZP p型の整数
make
Type: [p : CPLib.ZP::PrimeProvider] Std::I64 -> CPLib.ZP::ZP p
I64からZP pの値を作成する
計算量:O(1)
Parameters
x:I64型の整数
power
Type: [p : CPLib.ZP::PrimeProvider] Std::I64 -> CPLib.ZP::ZP p -> CPLib.ZP::ZP p
x^e mod p を計算する。
xが0かつeが負のときはプログラムを終了する。
計算量:O(log p)
Parameters
x:ZP p型の数e:I64型の指数
primitive_root
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p
法pの原始根を一つ得る
計算量:O(sqrt(p))。pがこのモジュールに定義されている素数ならO(1)
namespace CPLib.ZP::PrimeProvider
create
Type: [p : CPLib.ZP::PrimeProvider] p
Trait member of CPLib.ZP::PrimeProvider
value
Type: [p : CPLib.ZP::PrimeProvider] p -> Std::U32
Trait member of CPLib.ZP::PrimeProvider
Types and aliases
namespace CPLib.ZP
FFTDirection
Defined as: type FFTDirection = unbox union { ...variants... }
高速フーリエ変換の方向(順方向か逆方向か)を表す型
variant forward
Type: ()
variant inverse
Type: ()
P1000000007
Defined as: type P1000000007 = unbox struct { ...fields... }
P1000000009
Defined as: type P1000000009 = unbox struct { ...fields... }
P167772161
Defined as: type P167772161 = unbox struct { ...fields... }
NTT-friendly prime (2^25 | p-1)
P469762049
Defined as: type P469762049 = unbox struct { ...fields... }
NTT-friendly prime (2^26 | p-1)
P754974721
Defined as: type P754974721 = unbox struct { ...fields... }
NTT-friendly prime (2^24 | p-1)
P998244353
Defined as: type P998244353 = unbox struct { ...fields... }
NTT-friendly prime (2^23 | p-1)
ZP
Defined as: type ZP p = unbox struct { ...fields... }
素数pを法とする整数の環
field value
Type: Std::U32
field prime
Type: p
Traits and aliases
namespace CPLib.ZP
trait p : PrimeProvider
method create
Type: p
method value
Type: p -> Std::U32