PARI/GP

PARI/GP は計算機代数システムであり，整数論 (因数分解，代数的数理論，楕円曲線等)に関する様々な演算を行うことができます． PARI/GP はマルチプラットフォームであり，多くのプラットフォームで実行できます． GNU General Public Licenseにしたがって公開、配布されています． (http://pari.math.u-bordeaux.fr/)

PARI/GPは標準で，以下の2つのプログラムを備えています．

PARI
C言語のライブラリで，高速な演算を行う関数を提供する．
C言語以外にもC++，Pascal，Fortran，Perl，Pythonからも使うことができます．
gp
対話型に動作するコマンドラインインタフェースのプログラム．これを実行することでPARIの機能を使うことができます．C言語のような制御構文を備えた高度な電卓プログラムとしても使うことができます．gp プログラムが理解して実行するスクリプト言語を GP と呼びます．

PARI/GP の利用方法と主な関数 (コマンド) は PARI/GP 関数，制御構文を用いたプログラミングの概要は PARI/GP プログラムを参照．

PARI/GPの利用例

コマンドラインインタフェースでの PARI/GP の利用例を紹介します．

RSA暗号の解読
公開鍵 n と暗号文 C が与えられたときに，平文 M を求める．
RSA暗号は公開鍵 n が素因数分解できれば，解読できます．しかし，通常 n の大きさは 1024ビット以上ですので不可能ではないが，秘密鍵がないと復号は困難です．ここでは，n が小さい値の場合を例に計算手順を示します．

公開鍵 n = 10403，e = 8743，暗号文 C = 8214 とする．
1. n を素因数分解する．
```
 gp > factor(10403)
 %1 =
 [101 1]
 [103 1]
```
  上記により，n = 10403 が素因数分解され，素数 p = 103，q = 101 が得られる ( n = pq)．
2. LCM (p - 1，q - 1)を求める．
  p - 1 と q - 1 の最小公倍数 r を求める．
```
 gp > lcm(102, 100)
 %2 = 5100
```
  r として 5100 が得られる．
3. 秘密鍵 d を求める．
  d = 1/e mod r を計算する．
```
 gp > Mod(1/8743, 5100)
 %3 = Mod(7, 5100)
```
  秘密鍵 d として 7 が得られる．
4. 暗号文 C を復号する．
  M = C^d mod n を計算する．
```
 gp > Mod(8214^7, 10403)
 %4 = Mod(2722, 10403)
```
  平文 M として 2722 が得られる．
関数の定義
任意の関数を定義して実行する．
```
gp > f(x) = x^3 + 3*x + 1
gp > f(5)
%1 = 141
```
ファイルの実行
関数定義が書かれたファイルを実行する．次ファイル(sum2.gp)は，与えられた n に対して，1² + 2² + ... + n² を計算する．
```
sum2(n) =
{
	local(i, x);

	if(n < 0,
		n = -n;
	);

	x = 0;
	i = 1;
	while(i <= n,
		x = x + i^2;
		i++;
	);
	return(x)
}
```
sum2.gpを読み込んで実行する．
```
gp > \r sum2.gp
gp > sum2(11)
%1 = 506
```