PARI/GP

PARI/GPは整数論的計算を行うことに特化した計算環境である。

PARI

計算ライブラリ

GP

スクリプト言語

言語についてちゃんと学ぶには、PARI/GP documentationの"User's Guide to PARI/GP"と"GP Tutorial"を参照。 関数については"Online User's Guide"を参照。 GP Reference Cardは期待するほどには役に立たない。

Syntax of GP

ヘルプ

? funcname

コメント

\\ コメント`

なかなか珍しいバックスラッシュによるコメントアウト。

基本演算

• 加算 +

• 減算 -

• 乗算 *

• 冪算 ^

• 除算 /

  • 整数に対しては分数になる

• 少数切り捨て除算 \

• 四捨五入 \/

• ビットシフト <<, >>

• 比較 <, >, <=, >=, !=(<>), =

  • 注意: [] = 0

• 厳密な比較 ==

• 論理演算 &(&&), |(||)

  • ビット演算はbit*関数群を使用

ベクトル(aka タプル・配列)

• 行ベクトル: [1, 2, 3]

• 列ベクトル: [1, 2, 3]~

• 参照: vector[i] (1-origin)

• 要素数: #vector

? [2, 4, 6][1]
%1 = 2
? #[2, 4, 6]
%2 = 3

行列

• 行列: [1, 2; 3, 4]

• 参照: matrix[i,j]

  • 行参照: matrix[i,]

  • 列参照: matrix[,j]

? [1, 2; 3, 4]
%1 = 
[1 2]

[3 4]

? [1, 2; 3, 4][1, 1]
%2 = 1
? [1, 2; 3, 4][1,]
%3 = [1, 2]
? [1, 2; 3, 4][,1]
%4 = [1, 3]~

初等整数論的演算 ($\mathbb{Z}/n\mathbb{Z}$)

素因数分解

• factor(x): xを素因数分解

• factor(x, lim): lim未満の素数を使用

結果は行列として返される。形式: [素因数1, 素因数1の個数; 素因数2, 素因数2の個数; ...]

? factor(2^17+1)
%1 = 
[3 1]

[43691 1]

有限群・有限体上の点

$n$を法とした$x$: Mod(x, n)

? Mod(3, 7) * 3
%1 = Mod(2, 7)

注意: 単に剰余を計算するなら%演算子がある。

Mod(x, n)からxとnを取り出す

g = Mod(x, n)に対して

• xの取り出し lift(g)

• nの取り出し g.mod

? lift(Mod(2, 7))
%1 = 2
? Mod(2, 7).mod
%2 = 7

逆元

割り算するだけで良い。指数に-1を渡しても良い。

? 1/Mod(2, 7)
%1 = Mod(4, 7)
? Mod(2, 7)^-1
%2 = Mod(4, 7)

$\mathbb{Z}/p\mathbb{Z}$上の離散n乗根

sqrtn(x, n, &z)

存在すればzにxのn乗根の生成元が入る。存在しなければzは0になる。関数自体は主値(最小の元？)を返す。

? sqrtn(Mod(1, 7), 3, &z)
%1 = Mod(1, 7)
? z
%2 = Mod(2, 7)
? [z^0, z^1, z^2]
%3 = [Mod(1, 7), Mod(2, 7), Mod(4, 7)]

User's Guide to PARI/GPに全ての根を得るための方法として次のコードが掲載されている。

sqrtnall(x,n)=
{ my(V,r,z,r2);
  r = sqrtn(x,n, &z);
  if (!z, error("Impossible case in sqrtn"));
  if (type(x) == "t_INTMOD" || type(x)=="t_PADIC" ,
  r2 = r*z; n = 1;
  while (r2!=r, r2*=z;n++));
  V = vector(n); V[1] = r;
  for(i=2, n, V[i] = V[i-1]*z);
  V
}
addhelp(sqrtnall,"sqrtnall(x,n):compute the vector of nth-roots of x");

? sqrtnall(Mod(1, 7), 3)
%3 = [Mod(1, 7), Mod(2, 7), Mod(4, 7)]

$\mathbb{Z}/pq\mathbb{Z}$上の非自明な平方根

TODO

離散対数

znlog(x, g)

gを底としたxの離散対数を求める。 gは$(\mathbb{Z}/n\mathbb{Z})^*$の元である必要がある。

\\ 2^4 = 3 (mod 13)
? znlog(3, Mod(2, 13))
%1 = 4

生成元

znprimroot(n)

Z/nZの生成元を返す。

? g = znprimroot(13)
%1 = Mod(2, 13)

拡張ユークリッドの互除法

bezout(x, y)

$xu + yv = d$ なる[u, v, d]を返す。

\\ gcd(4, 6) = 2
\\ 4*-1 + 6*1 = 2
? bezout(4, 6)
%1 = [-1, 1, 2]

注意: 単に最大公約数を求めるなら直感的なgcd(x, y)がある。

中国人剰余定理

• chinese(x, y): x, yは$\mathbb{Z}/n\mathbb{Z}$の元。

• chinese([x1, x2, ...]): x1, x2, ...は$\mathbb{Z}/n\mathbb{Z}$の元。

2引数でも配列で渡しても良い。

? chinese(chinese(Mod(2, 3), Mod(3, 5)), Mod(2, 7))
%1 = Mod(23, 105)
? chinese([Mod(2, 3), Mod(3, 5), Mod(2, 7)])
%2 = Mod(23, 105)

RSA

ElGamal encryption

楕円曲線

多項式

格子

ペアリング