1と2のリビジョン間の差分

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)

-  ⇤ ← 2014-02-06 00:12:20時点のリビジョン1 → 
  サイズ: 385
  編集者: ytoku
  コメント:
+   ← 2014-02-07 04:42:43時点のリビジョン2 → ⇥
  サイズ: 3992
  編集者: ytoku
  コメント:
-削除された箇所はこのように表示されます。
+追加された箇所はこのように表示されます。
 行 8:
-== 初等整数論的演算 ($\mathbb{Z}/n\mathbb{Z}$) ==
=== 有限群・有限体上の点 ===
+言語についてちゃんと学ぶには、PARI/GP documentationの"Users' Guide to PARI/GP"と"GP Tutorial"を参照。
関数については"Online User's Guide"を参照。

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

<<TableOfContents>>

= 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]

}}}

== 有限群・有限体上の点 ==
-行 11:
+行 92:
+{{{
? Mod(3, 7) * 3
%1 = Mod(2, 7)
}}}
-行 12:
+行 97:
-== 楕円曲線 ==
+注意: 単に剰余を計算するなら`%`演算子がある。
-行 14:
+行 99:
-== 格子 ==
+== Mod(x, n)からxとnを取り出す ==
TODO
-行 16:
+行 102:
-== ペアリング ==
+== 逆元 ==
指数に-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)
}}}

== RSA ==

== ElGamal encryption ==

= 楕円曲線 =

= 多項式 =

= 格子 =

= ペアリング =