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]

乱数生成

random(n)

nが整数であれば[0, n)の範囲の整数をランダムに返す。

大きい素数を生成

nextprime(n)を用いればnとほぼ同じ大きさの素数が得られる。

\\ 10^10の次の素数
? nextprime(10^10)
%1 = 10000000019
\\ 128bitの素数をランダムに生成
? nextprime(2^127 + random(2^127))
%2 = 267183150806405707118987831126661135943

有限群・有限体上の点

$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

乗法群の位数

znorder(g)

gを生成元とする$\mathbb{Z}/n\mathbb{Z}$の部分巡回群の位数を返す。

離散対数

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上の生成元を返す。

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

最大公約数

• gcd(x, y)

• gcd([x1, x2, ...])

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

? gcd(4, 6)
%1 = 2
? gcd(gcd(12, 18), 30)
%2 = 6
? gcd([12, 18, 30])
%3 = 6

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

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]

中国人剰余定理

• 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

正当な計算例

\\ 鍵生成
p = 13
q = 17
e = 7
n = p*q
phi = (p-1)*(q-1)
d = lift(1/Mod(e, phi))
pk = [n, e]
sk = [n, d]

\\ 平文
m = Mod(8, n)
\\ 暗号化
c = m^e
\\ 復号
m = c^d

攻撃例: 離散対数問題を解ける場合の既知平文攻撃(KPA)

d = znlog(lift(m), c)

ElGamal暗号

正当な計算例

\\ 鍵生成
\\ p=2*q+1 is prime
\\ #<g> = q
q = 29
p = 2*q+1
g = znprimroot(p)^2
x = random(q)
h = g^x
pk = [p, q, g, h]
sk = [p, x]
\\ 平文
\\ m \in <g> に注意
m = g ^ 2
\\ 暗号化
r = random(q)
c1 = g^r
c2 = m * h^r
c = [c1, c2]
\\ 復号
m = c2 / c1^x

q, pのランダムな生成

q = nextprime(2^127 + random(2^127))
p = 1; until(isprime(p), q = nextprime(q+2); p = 2*q+1)

攻撃例: 離散対数問題を解ける場合の唯鍵攻撃(KOA)

x = znlog(lift(h), g)

攻撃例: 離散対数問題を解ける場合の暗号文単独攻撃(COA)

KOAできるので意味なし

r = znlog(lift(c1), g)
m = c2 / h^r

楕円曲線

多項式

格子

ペアリング