Maxima ... jacobi

書式

jacobi(m, n)

で用い、Jacobi 記号 (m/n) の値を出力する（本来分数で表さなければならないが、テキストベースのため表記の乱用御免）。当然 m や n は整数（あるいは変数）でなければならず、さらに n ≠ 0 でなければならない。

(%i1) jacobi(2 ,35);

(%o1)                            - 1


(%i2) jacobi(3 ,35);

(%o2)                             1


(%i3) jacobi(4 ,35);

(%o3)                             1


(%i4) jacobi(5 ,35);

(%o4)                             0

補足　奇素数 p および p と互いに素な整数 a に対して、記号 (a/p) を次のように定義する：

2 次方程式 x^2 ≡ a mod p が整数解を持つ	⇒	(a/p) = 1
2 次方程式 x^2 ≡ a mod p が整数解を持たない	⇒	(a/p) = -1

更に便宜上 a が p の倍数の場合（a = 0 を含む）は (a/p) = 0 と定めた記号 (　/　) を Legendre 記号あるいは平方剰余記号と呼ぶ。この Legendre 記号を一般の整数の場合に拡張したものが Jacobi 記号である。具体的には、整数 n を素因数分解 n = p₁p₂p₃… p_k（ただし、p_iの中に重複があってもよい）したとき、(a/n) を

(a/n) = (a/p₁) × (a/p₂) × (a/p₃) × … × (a/p_k)

により定義する。なお、n が偶数の場合は考えないことが多いが、Maxima の関数 jacobi では、a の偶奇に従って、(a/2) = 0 or 1 と定義している（方程式 x^2 ≡ a mod 2 は常に整数解を持つ）。

［参考文献］オンラインで読めるものとしては、

Handbook of Applied Cryptography の Chapter 2（PDF pp. 26-27）

に定義とアルゴリズムが証明抜きに簡潔にまとめられている。