Skip to content

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

Trait implementations

impl CPLib.ZP::P1000000007 : CPLib.ZP::PrimeProvider

impl CPLib.ZP::P1000000009 : CPLib.ZP::PrimeProvider

impl CPLib.ZP::P998244353 : CPLib.ZP::PrimeProvider

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Add

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Div

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Eq

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Mul

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Neg

impl [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p : Std::Sub

impl CPLib.ZP::ZP p : Std::ToString