PARI/GP

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

PARI: 計算ライブラリ
GP: スクリプト言語

言語についてちゃんと学ぶには、PARI/GP documentationの"Users' Guide to PARI/GP"と"GP Tutorial"を参照。関数については"Online User's Guide"を参照。

GP Reference Cardは期待するほどには役に立たない。

PARI/GP
Syntax of GP
初等整数論的演算 ($\mathbb{Z}/n\mathbb{Z}$)
楕円曲線
多項式
格子
ペアリング

Syntax of GP

ヘルプ

? funcname

\\ コメント`

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

基本演算

加算 +
減算 -
乗算 *
冪算 ^
除算 /
- 整数に対しては分数になる
少数切り捨て除算 \
四捨五入 \/
ビットシフト <<, >>
比較 <, >, <=, >=, !=(<>), =
- 注意: [] = 0
厳密な比較 ==
論理演算 &(&&), |(||)
- ビット演算はない？

ベクトル(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を取り出す

TODO

逆元

指数に-1を渡すだけで良い。

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

離散n乗根

$\mathbb{Z}/p\mathbb{Z}$に対しては指数に分数を渡すとn乗根の一つが得られる。

? Mod(3, 11)^(1/3)
%1 = Mod(9, 11)
\\ 自明な根しか出てこない
\\ Mod(1, 7)の3乗根は1, 2, 4
? Mod(1, 7)^(1/3)
%2 = Mod(1, 7)

nが素数でない$\mathbb{Z}/n\mathbb{Z}$に対しては一切動かず自明な根すら返さない。

? Mod(1, 6)^(1/2)
  ***   at top-level: Mod(1,6)^(1/2)
  ***                         ^------
  *** _^_: gpow: modulus 6 is not prime.
  ***   Break loop: type 'break' to go back to GP

$\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)