CPLib.ZP
Defined in cp-library@0.1.1
素数pを法とする整数の環の型ZP pを与えるモジュール。
素数pは静的でなければならない(コンパイル時に決まる必要がある)。
素数pは型パラメータとして与える。例として、p = 17 としたい場合、
- 空の型(フィールドを持たないunboxedな型)P17を作成:type P17 = unbox struct {}.
- P17 : PrimeProviderを実装する。この際PrimeProvider::value関数で17を返すようにする:value = |_| 17_U32;
するとZP P17が環"Z/(17)"を表す型となる。
P100000007、P1000000009, P998244353 はこのモジュールに定義されている。
使用例:
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::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
namespace CPLib.ZP::ZP
inv
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p -> CPLib.ZP::ZP p
ZP pの逆元を求める。
0を与えた場合はプログラムを終了する。
Parameters
x:ZP p型の整数
make
Type: [p : CPLib.ZP::PrimeProvider] Std::I64 -> CPLib.ZP::ZP p
I64から素数を作成する
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が負のときはプログラムを終了する。
Parameters
x:ZP p型の数e:I64型の指数
Types and aliases
namespace CPLib.ZP
P1000000007
Defined as: type P1000000007 = unbox struct { ...fields... }
P1000000009
Defined as: type P1000000009 = unbox struct { ...fields... }
P998244353
Defined as: type P998244353 = unbox struct { ...fields... }
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