平方剰余
こんにちは。もう少し暗号を続けます。それに必要な数学の知識として平方剰余を取り上げます。
具体例から考えてみる
整数\(x\)に対して\(x^2\)を求め、素数\(p\)で割った余りを考えていきます。
\(p=2\)として考える
\(x=-2\)のとき、\(x^2 \div p = 4 \div 2 = 2 \cdots 0 \)
\(x=-1\)のとき、\(x^2 \div p = 1 \div 2 = 0 \cdots 1 \)
\(x=0\)のとき、\(x^2 \div p = 0 \div 2 = 0 \cdots 0 \)
\(x=1\)のとき、\(x^2 \div p = 1 \div 2 = 0 \cdots 1 \)
\(x=2\)のとき、\(x^2 \div p = 4 \div 2 = 2 \cdots 0 \)
\(x=3\)のとき、\(x^2 \div p = 9 \div 2 = 4 \cdots 1 \)
\(x=4\)のとき、\(x^2 \div p = 16 \div 2 = 8 \cdots 0 \)
となって、\(p=2\)で割ったとき、割り切れるか余りが\(1\)になるかのいずれかです。割り切れるのは\(x\)が偶数のとき、余りが\(1\)になるのは\(x\)が奇数のときです。
\(p=3\)として考える
次に、\(p\)を奇数として、整数\(x\)に対して\(x^2\)を求め、奇素数\(p\)で割った余りを考えていきます。
\(x=-2\)のとき、\(x^2 \div p = 4 \div 3 = 1 \cdots 1 \)
\(x=-1\)のとき、\(x^2 \div p = 1 \div 3 = 0 \cdots 1 \)
\(x=0\)のとき、\(x^2 \div p = 0 \div 3 = 0 \cdots 0 \)
\(x=1\)のとき、\(x^2 \div p = 1 \div 3 = 0 \cdots 1 \)
\(x=2\)のとき、\(x^2 \div p = 4 \div 3 = 1 \cdots 1 \)
\(x=3\)のとき、\(x^2 \div p = 9 \div 3 = 3 \cdots 0 \)
\(x=4\)のとき、\(x^2 \div p = 16 \div 3 = 5 \cdots 1 \)
\(x=5\)のとき、\(x^2 \div p = 25 \div 3 = 8 \cdots 1 \)
\(x=6\)のとき、\(x^2 \div p = 36 \div 3 = 12 \cdots 0 \)
となって、\(3\)で割った余りは\( \cdots , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , \cdots \)と\(0,1,1\)の順に繰り返されることがわかります。
また、\(x^2\)を\(3\)で割ったとき、余りが\(2\)になることがないこともわかります。
\(p=5\)として考える
次に、\(p=5\)として考えていきます。\(x\)が負の場合も同じ繰り返しになるので、これ以降省略します。
\(x=0\)のとき、\(x^2 \div p = 0 \div 5 = 0 \cdots 0 \)
\(x=1\)のとき、\(x^2 \div p = 1 \div 5 = 0 \cdots 1 \)
\(x=2\)のとき、\(x^2 \div p = 4 \div 5 = 0 \cdots 4 \)
\(x=3\)のとき、\(x^2 \div p = 9 \div 5 = 1 \cdots 4 \)
\(x=4\)のとき、\(x^2 \div p = 16 \div 5 = 3 \cdots 1 \)
\(x=5\)のとき、\(x^2 \div p = 25 \div 5 = 5 \cdots 0 \)
\(x=6\)のとき、\(x^2 \div p = 36 \div 5 = 7 \cdots 1 \)
となって、\(5\)で割った余りは\( \cdots , 0 , 1 , 4 , 4 , 1 , \cdots \)の順に繰り返されることがわかります。
また、\(x^2\)を\(5\)で割ったとき、余りが\(2,3\)になることがないこともわかります。
\(p=7\)として考える
次に、\(p=7\)として考えていきます。
\(x=0\)のとき、\(x^2 \div p = 0 \div 7 = 0 \cdots 0 \)
\(x=1\)のとき、\(x^2 \div p = 1 \div 7 = 0 \cdots 1 \)
\(x=2\)のとき、\(x^2 \div p = 4 \div 7 = 0 \cdots 4 \)
\(x=3\)のとき、\(x^2 \div p = 9 \div 7 = 1 \cdots 2 \)
\(x=4\)のとき、\(x^2 \div p = 16 \div 7 = 2 \cdots 2 \)
\(x=5\)のとき、\(x^2 \div p = 25 \div 7 = 3 \cdots 4 \)
\(x=6\)のとき、\(x^2 \div p = 36 \div 7 = 5 \cdots 1 \)
\(x=7\)のとき、\(x^2 \div p = 49 \div 7 = 7 \cdots 0 \)
となって、\(7\)で割った余りは\( \cdots , 0 , 1 , 4 , 2 , 2 , 4 , 1 , \cdots \)の順に繰り返されることがわかります。
また、\(x^2\)を\(7\)で割ったとき、余りが\(3,5,6\)になることがないこともわかります。
\(p=11\)として考える
長くなっていますが、\(p=11\)についても考えます。
\(x=0\)のとき、\(x^2 \div p = 0 \div 11 = 0 \cdots 0 \)
\(x=1\)のとき、\(x^2 \div p = 1 \div 11 = 0 \cdots 1 \)
\(x=2\)のとき、\(x^2 \div p = 4 \div 11 = 0 \cdots 4 \)
\(x=3\)のとき、\(x^2 \div p = 9 \div 11 = 1 \cdots 9 \)
\(x=4\)のとき、\(x^2 \div p = 16 \div 11 = 1 \cdots 5 \)
\(x=5\)のとき、\(x^2 \div p = 25 \div 11 = 2 \cdots 3 \)
\(x=6\)のとき、\(x^2 \div p = 36 \div 11 = 3 \cdots 3 \)
\(x=7\)のとき、\(x^2 \div p = 49 \div 11 = 4 \cdots 5 \)
\(x=8\)のとき、\(x^2 \div p = 64 \div 11 = 5 \cdots 9 \)
\(x=9\)のとき、\(x^2 \div p = 81 \div 11 = 7 \cdots 4 \)
\(x=10\)のとき、\(x^2 \div p = 100 \div 11 = 9 \cdots 1 \)
\(x=11\)のとき、\(x^2 \div p = 121 \div 11 = 11 \cdots 0 \)
となって、\(11\)で割った余りは\( \cdots , 0 , 1 , 4 , 9 , 5 , 3 , 3 , 5 , 9 , 4 , 1 , \cdots \)の順に繰り返されることがわかります。
また、\(x^2\)を\(11\)で割ったとき、余りが\(2,6,7,8,10\)になることがないこともわかります。
平方剰余と平方非剰余とルジャンドル記号
ここまでで調べたことで、\(x^2\)を\(p\)で割ったときの余りとして現れるものと、現れないものがあることがわかりました。余りに現れる数のうち\(0\)でないものを平方剰余、現れないものを平方非剰余といいます。また、\(x\)が\(p\)の倍数のとき（\(x^2\)が\(p\)で割り切れるとき）はいずれでもないものとします。
\(a\)が奇素数\(p\)の平方剰余となっているかどうかを、次のような記号で表します（ルジャンドル記号）。
\[\begin{eqnarray} \left( \frac{a}{p} \right) = \begin{cases} 1 & ( a が平方剰余のとき ) \\ -1 & (aが平方非剰余のとき) \\ 0 & ( a がpの倍数のとき ) \end{cases}\end{eqnarray}\]
例えば、\(9\)は\(11\)の平方剰余となっている（\(x^2\)を\(11\)で割った余りに\(9\)が現れる）ので、\( \left( \frac{9}{11} \right) = 1\)となります。
また、\(10\)は\(11\)の平方非剰余となっている（\(x^2\)を\(11\)で割った余りに\(10\)が現れない）ので、\( \left( \frac{10}{11} \right) = -1\)となります。
ヤコビ記号
正の奇数\(n\)が\(n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}\)と因数分解できるものとします。ここで\(p_1,p_2,\cdots,p_k\)は奇素数とします。このときヤコビ記号（左辺）をルジャンドル記号（右辺）を用いて次のように定義します。
\[ \left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{e_1} \left( \frac{a}{p_2} \right)^{e_2} \cdots \left( \frac{a}{p_k} \right)^{e_k} \]
このとき、ヤコビ記号で表される\(\left( \frac{a}{n} \right) \)は、必ずしも\(a\)が\(n\)の平方剰余になっているか否かを示していないことに注意が必要です。
ヤコビ記号の性質
ヤコビ記号では次の性質が成り立ちます。（証明は省略します）
１．
\[ \left( \frac{a_1 a_2}{n} \right) = \left( \frac{a_1}{n} \right) \left( \frac{a_2}{n} \right) \]
２．（第１補充法則）
\[ \begin{eqnarray} \left( \frac{-1}{n} \right) = {(-1)}^{\frac{n-1}{2}} = \begin{cases} 1 & ( p \equiv 1 \bmod 4 のとき) \\ -1 & ( p \equiv 3 \bmod 4 のとき) \end{cases} \end{eqnarray}\]
３．（第２補充法則）
\[ \begin{eqnarray} \left( \frac{2}{n} \right) = {(-1)}^{\frac{n^2-1}{8}} = \begin{cases} 1 & ( p \equiv 1,7 \bmod 8 のとき) \\ -1 & ( p \equiv 3,5 \bmod 8 のとき) \end{cases} \end{eqnarray} \]
４．（相互法則）\(m,n\)がともに\(3\)以上の奇数のとき
\[ \left( \frac{m}{n} \right) \left( \frac{n}{m} \right) = {(-1)}^{\frac{m-1}{2} \frac{n-1}{2}} \]
これを書き直すと
\[ \begin{eqnarray} \left( \frac{m}{n} \right) = \begin{cases} \left( \frac{n}{m} \right) & ( m \equiv 1 \bmod 4 または n \equiv 1 \bmod 4のとき) \\ – \left( \frac{n}{m} \right) & ( m \equiv n \equiv 3 \bmod 4 のとき) \end{cases} \end{eqnarray} \]
平方剰余に関するプログラム（ライブラリを用いた場合）
毎度のPythonで使ってみます。（０を含めた）平方剰余を求め、その解を求めます。次にルジャンドル記号の値を求めるプログラムは次になります。
import sympy
def odd_prime( n ):
composite = []
prime = []
p = 3
while p < n:
if not p in composite:
prime.append( p )
k = 3
while p*k < n:
if not p*k in composite:
composite.append( p*k )
k += 2
p += 2
return prime
#平方剰余のリストを作る
for i in range( 1, 20 ):
quadratic = sympy.quadratic_residues( i )
print( 'i=', i, quadratic )
#平方剰余に対して平方根を求める
for q in quadratic:
print( 'x^2 ≡ {0} mod {1} の解は、x = {2}'.format( q, i, sympy.sqrt_mod( q, i ) ) )
# 素数pの平方剰余か否かを求める
prime = odd_prime( 20 )
for p in prime:
for k in range( 0, p+1 ):
print( '(k/p) = ({0}/{1}) = {2}'.format( k, p, sympy.legendre_symbol( k, p ) ) )
実行結果は次になります。
i= 1 [0]
x^2 ≡ 0 mod 1 の解は、x = 0
i= 2 [0, 1]
x^2 ≡ 0 mod 2 の解は、x = 0
x^2 ≡ 1 mod 2 の解は、x = 1
i= 3 [0, 1]
x^2 ≡ 0 mod 3 の解は、x = 0
x^2 ≡ 1 mod 3 の解は、x = 1
i= 4 [0, 1]
x^2 ≡ 0 mod 4 の解は、x = 0
x^2 ≡ 1 mod 4 の解は、x = 1
i= 5 [0, 1, 4]
x^2 ≡ 0 mod 5 の解は、x = 0
x^2 ≡ 1 mod 5 の解は、x = 1
x^2 ≡ 4 mod 5 の解は、x = 2
i= 6 [0, 1, 3, 4]
x^2 ≡ 0 mod 6 の解は、x = 0
x^2 ≡ 1 mod 6 の解は、x = 1
x^2 ≡ 3 mod 6 の解は、x = 3
x^2 ≡ 4 mod 6 の解は、x = 2
i= 7 [0, 1, 2, 4]
x^2 ≡ 0 mod 7 の解は、x = 0
x^2 ≡ 1 mod 7 の解は、x = 1
x^2 ≡ 2 mod 7 の解は、x = 3
x^2 ≡ 4 mod 7 の解は、x = 2
i= 8 [0, 1, 4]
x^2 ≡ 0 mod 8 の解は、x = 0
x^2 ≡ 1 mod 8 の解は、x = 1
x^2 ≡ 4 mod 8 の解は、x = 2
i= 9 [0, 1, 4, 7]
x^2 ≡ 0 mod 9 の解は、x = 0
x^2 ≡ 1 mod 9 の解は、x = 1
x^2 ≡ 4 mod 9 の解は、x = 2
x^2 ≡ 7 mod 9 の解は、x = 4
i= 10 [0, 1, 4, 5, 6, 9]
x^2 ≡ 0 mod 10 の解は、x = 0
x^2 ≡ 1 mod 10 の解は、x = 1
x^2 ≡ 4 mod 10 の解は、x = 2
x^2 ≡ 5 mod 10 の解は、x = 5
x^2 ≡ 6 mod 10 の解は、x = 4
x^2 ≡ 9 mod 10 の解は、x = 3
i= 11 [0, 1, 3, 4, 5, 9]
x^2 ≡ 0 mod 11 の解は、x = 0
x^2 ≡ 1 mod 11 の解は、x = 1
x^2 ≡ 3 mod 11 の解は、x = 5
x^2 ≡ 4 mod 11 の解は、x = 2
x^2 ≡ 5 mod 11 の解は、x = 4
x^2 ≡ 9 mod 11 の解は、x = 3
i= 12 [0, 1, 4, 9]
x^2 ≡ 0 mod 12 の解は、x = 0
x^2 ≡ 1 mod 12 の解は、x = 1
x^2 ≡ 4 mod 12 の解は、x = 4
x^2 ≡ 9 mod 12 の解は、x = 3
i= 13 [0, 1, 3, 4, 9, 10, 12]
x^2 ≡ 0 mod 13 の解は、x = 0
x^2 ≡ 1 mod 13 の解は、x = 1
x^2 ≡ 3 mod 13 の解は、x = 4
x^2 ≡ 4 mod 13 の解は、x = 2
x^2 ≡ 9 mod 13 の解は、x = 3
x^2 ≡ 10 mod 13 の解は、x = 6
x^2 ≡ 12 mod 13 の解は、x = 5
i= 14 [0, 1, 2, 4, 7, 8, 9, 11]
x^2 ≡ 0 mod 14 の解は、x = 0
x^2 ≡ 1 mod 14 の解は、x = 1
x^2 ≡ 2 mod 14 の解は、x = 4
x^2 ≡ 4 mod 14 の解は、x = 2
x^2 ≡ 7 mod 14 の解は、x = 7
x^2 ≡ 8 mod 14 の解は、x = 6
x^2 ≡ 9 mod 14 の解は、x = 3
x^2 ≡ 11 mod 14 の解は、x = 5
i= 15 [0, 1, 4, 6, 9, 10]
x^2 ≡ 0 mod 15 の解は、x = 0
x^2 ≡ 1 mod 15 の解は、x = 1
x^2 ≡ 4 mod 15 の解は、x = 2
x^2 ≡ 6 mod 15 の解は、x = 6
x^2 ≡ 9 mod 15 の解は、x = 3
x^2 ≡ 10 mod 15 の解は、x = 5
i= 16 [0, 1, 4, 9]
x^2 ≡ 0 mod 16 の解は、x = 0
x^2 ≡ 1 mod 16 の解は、x = 1
x^2 ≡ 4 mod 16 の解は、x = 2
x^2 ≡ 9 mod 16 の解は、x = 5
i= 17 [0, 1, 2, 4, 8, 9, 13, 15, 16]
x^2 ≡ 0 mod 17 の解は、x = 0
x^2 ≡ 1 mod 17 の解は、x = 1
x^2 ≡ 2 mod 17 の解は、x = 6
x^2 ≡ 4 mod 17 の解は、x = 2
x^2 ≡ 8 mod 17 の解は、x = 5
x^2 ≡ 9 mod 17 の解は、x = 3
x^2 ≡ 13 mod 17 の解は、x = 8
x^2 ≡ 15 mod 17 の解は、x = 7
x^2 ≡ 16 mod 17 の解は、x = 4
i= 18 [0, 1, 4, 7, 9, 10, 13, 16]
x^2 ≡ 0 mod 18 の解は、x = 0
x^2 ≡ 1 mod 18 の解は、x = 1
x^2 ≡ 4 mod 18 の解は、x = 2
x^2 ≡ 7 mod 18 の解は、x = 5
x^2 ≡ 9 mod 18 の解は、x = 3
x^2 ≡ 10 mod 18 の解は、x = 8
x^2 ≡ 13 mod 18 の解は、x = 7
x^2 ≡ 16 mod 18 の解は、x = 4
i= 19 [0, 1, 4, 5, 6, 7, 9, 11, 16, 17]
x^2 ≡ 0 mod 19 の解は、x = 0
x^2 ≡ 1 mod 19 の解は、x = 1
x^2 ≡ 4 mod 19 の解は、x = 2
x^2 ≡ 5 mod 19 の解は、x = 9
x^2 ≡ 6 mod 19 の解は、x = 5
x^2 ≡ 7 mod 19 の解は、x = 8
x^2 ≡ 9 mod 19 の解は、x = 3
x^2 ≡ 11 mod 19 の解は、x = 7
x^2 ≡ 16 mod 19 の解は、x = 4
x^2 ≡ 17 mod 19 の解は、x = 6
(k/p) = (0/3) = 0
(k/p) = (1/3) = 1
(k/p) = (2/3) = -1
(k/p) = (3/3) = 0
(k/p) = (0/5) = 0
(k/p) = (1/5) = 1
(k/p) = (2/5) = -1
(k/p) = (3/5) = -1
(k/p) = (4/5) = 1
(k/p) = (5/5) = 0
(k/p) = (0/7) = 0
(k/p) = (1/7) = 1
(k/p) = (2/7) = 1
(k/p) = (3/7) = -1
(k/p) = (4/7) = 1
(k/p) = (5/7) = -1
(k/p) = (6/7) = -1
(k/p) = (7/7) = 0
(k/p) = (0/11) = 0
(k/p) = (1/11) = 1
(k/p) = (2/11) = -1
(k/p) = (3/11) = 1
(k/p) = (4/11) = 1
(k/p) = (5/11) = 1
(k/p) = (6/11) = -1
(k/p) = (7/11) = -1
(k/p) = (8/11) = -1
(k/p) = (9/11) = 1
(k/p) = (10/11) = -1
(k/p) = (11/11) = 0
(k/p) = (0/13) = 0
(k/p) = (1/13) = 1
(k/p) = (2/13) = -1
(k/p) = (3/13) = 1
(k/p) = (4/13) = 1
(k/p) = (5/13) = -1
(k/p) = (6/13) = -1
(k/p) = (7/13) = -1
(k/p) = (8/13) = -1
(k/p) = (9/13) = 1
(k/p) = (10/13) = 1
(k/p) = (11/13) = -1
(k/p) = (12/13) = 1
(k/p) = (13/13) = 0
(k/p) = (0/17) = 0
(k/p) = (1/17) = 1
(k/p) = (2/17) = 1
(k/p) = (3/17) = -1
(k/p) = (4/17) = 1
(k/p) = (5/17) = -1
(k/p) = (6/17) = -1
(k/p) = (7/17) = -1
(k/p) = (8/17) = 1
(k/p) = (9/17) = 1
(k/p) = (10/17) = -1
(k/p) = (11/17) = -1
(k/p) = (12/17) = -1
(k/p) = (13/17) = 1
(k/p) = (14/17) = -1
(k/p) = (15/17) = 1
(k/p) = (16/17) = 1
(k/p) = (17/17) = 0
(k/p) = (0/19) = 0
(k/p) = (1/19) = 1
(k/p) = (2/19) = -1
(k/p) = (3/19) = -1
(k/p) = (4/19) = 1
(k/p) = (5/19) = 1
(k/p) = (6/19) = 1
(k/p) = (7/19) = 1
(k/p) = (8/19) = -1
(k/p) = (9/19) = 1
(k/p) = (10/19) = -1
(k/p) = (11/19) = 1
(k/p) = (12/19) = -1
(k/p) = (13/19) = -1
(k/p) = (14/19) = -1
(k/p) = (15/19) = -1
(k/p) = (16/19) = 1
(k/p) = (17/19) = 1
(k/p) = (18/19) = -1
(k/p) = (19/19) = 0
平方剰余に関するプログラム（ライブラリを用いない場合）
ライブラリを使わないで、上のプログラムと同じ動作をするプログラムは次になります。（legendre_symbol( k, p )関数の引数pが奇素数でないときにエラーを出さない点で挙動が異なります。）
def odd_prime( n ):
composite = []
prime = []
p = 3
while p < n:
if not p in composite:
prime.append( p )
k = 3
while p*k < n:
if not p*k in composite:
composite.append( p*k )
k += 2
p += 2
return prime
#平方剰余のリストを作る
def quadratic_residues( n ):
quadratic = []
for x in range( 0, n ):
m = (x*x) % n
if not m in quadratic:
quadratic.append( m )
return sorted( quadratic )
#平方剰余に対して平方根を求める
def sqrt_mod( x, n ):
for i in range( 0, n ):
if ((i*i) % n) == x:
return i
return None
# 素数pの平方剰余か否かを求める
def legendre_symbol( m, n ):
if m % n == 0:
return 0
else:
return -1 + 2*int( m in quadratic_residues( n ) )
if __name__ == '__main__':
#平方剰余のリストを作る
for i in range( 1, 20 ):
quadratic = quadratic_residues( i )
print( 'i=', i, quadratic )
#平方剰余に対して平方根を求める
for q in quadratic:
print( 'x^2 ≡ {0} mod {1} の解は、x = {2}'.format( q, i, sqrt_mod( q, i ) ) )
# 素数pの平方剰余か否かを求める
prime = odd_prime( 20 )
for p in prime:
for k in range( 0, p+1 ):
print( '(k/p) = ({0}/{1}) = {2}'.format( k, p, legendre_symbol( k, p ) ) )
念のため実行結果を載せておきます。
i= 1 [0]
x^2 ≡ 0 mod 1 の解は、x = 0
i= 2 [0, 1]
x^2 ≡ 0 mod 2 の解は、x = 0
x^2 ≡ 1 mod 2 の解は、x = 1
i= 3 [0, 1]
x^2 ≡ 0 mod 3 の解は、x = 0
x^2 ≡ 1 mod 3 の解は、x = 1
i= 4 [0, 1]
x^2 ≡ 0 mod 4 の解は、x = 0
x^2 ≡ 1 mod 4 の解は、x = 1
i= 5 [0, 1, 4]
x^2 ≡ 0 mod 5 の解は、x = 0
x^2 ≡ 1 mod 5 の解は、x = 1
x^2 ≡ 4 mod 5 の解は、x = 2
i= 6 [0, 1, 3, 4]
x^2 ≡ 0 mod 6 の解は、x = 0
x^2 ≡ 1 mod 6 の解は、x = 1
x^2 ≡ 3 mod 6 の解は、x = 3
x^2 ≡ 4 mod 6 の解は、x = 2
i= 7 [0, 1, 2, 4]
x^2 ≡ 0 mod 7 の解は、x = 0
x^2 ≡ 1 mod 7 の解は、x = 1
x^2 ≡ 2 mod 7 の解は、x = 3
x^2 ≡ 4 mod 7 の解は、x = 2
i= 8 [0, 1, 4]
x^2 ≡ 0 mod 8 の解は、x = 0
x^2 ≡ 1 mod 8 の解は、x = 1
x^2 ≡ 4 mod 8 の解は、x = 2
i= 9 [0, 1, 4, 7]
x^2 ≡ 0 mod 9 の解は、x = 0
x^2 ≡ 1 mod 9 の解は、x = 1
x^2 ≡ 4 mod 9 の解は、x = 2
x^2 ≡ 7 mod 9 の解は、x = 4
i= 10 [0, 1, 4, 5, 6, 9]
x^2 ≡ 0 mod 10 の解は、x = 0
x^2 ≡ 1 mod 10 の解は、x = 1
x^2 ≡ 4 mod 10 の解は、x = 2
x^2 ≡ 5 mod 10 の解は、x = 5
x^2 ≡ 6 mod 10 の解は、x = 4
x^2 ≡ 9 mod 10 の解は、x = 3
i= 11 [0, 1, 3, 4, 5, 9]
x^2 ≡ 0 mod 11 の解は、x = 0
x^2 ≡ 1 mod 11 の解は、x = 1
x^2 ≡ 3 mod 11 の解は、x = 5
x^2 ≡ 4 mod 11 の解は、x = 2
x^2 ≡ 5 mod 11 の解は、x = 4
x^2 ≡ 9 mod 11 の解は、x = 3
i= 12 [0, 1, 4, 9]
x^2 ≡ 0 mod 12 の解は、x = 0
x^2 ≡ 1 mod 12 の解は、x = 1
x^2 ≡ 4 mod 12 の解は、x = 2
x^2 ≡ 9 mod 12 の解は、x = 3
i= 13 [0, 1, 3, 4, 9, 10, 12]
x^2 ≡ 0 mod 13 の解は、x = 0
x^2 ≡ 1 mod 13 の解は、x = 1
x^2 ≡ 3 mod 13 の解は、x = 4
x^2 ≡ 4 mod 13 の解は、x = 2
x^2 ≡ 9 mod 13 の解は、x = 3
x^2 ≡ 10 mod 13 の解は、x = 6
x^2 ≡ 12 mod 13 の解は、x = 5
i= 14 [0, 1, 2, 4, 7, 8, 9, 11]
x^2 ≡ 0 mod 14 の解は、x = 0
x^2 ≡ 1 mod 14 の解は、x = 1
x^2 ≡ 2 mod 14 の解は、x = 4
x^2 ≡ 4 mod 14 の解は、x = 2
x^2 ≡ 7 mod 14 の解は、x = 7
x^2 ≡ 8 mod 14 の解は、x = 6
x^2 ≡ 9 mod 14 の解は、x = 3
x^2 ≡ 11 mod 14 の解は、x = 5
i= 15 [0, 1, 4, 6, 9, 10]
x^2 ≡ 0 mod 15 の解は、x = 0
x^2 ≡ 1 mod 15 の解は、x = 1
x^2 ≡ 4 mod 15 の解は、x = 2
x^2 ≡ 6 mod 15 の解は、x = 6
x^2 ≡ 9 mod 15 の解は、x = 3
x^2 ≡ 10 mod 15 の解は、x = 5
i= 16 [0, 1, 4, 9]
x^2 ≡ 0 mod 16 の解は、x = 0
x^2 ≡ 1 mod 16 の解は、x = 1
x^2 ≡ 4 mod 16 の解は、x = 2
x^2 ≡ 9 mod 16 の解は、x = 3
i= 17 [0, 1, 2, 4, 8, 9, 13, 15, 16]
x^2 ≡ 0 mod 17 の解は、x = 0
x^2 ≡ 1 mod 17 の解は、x = 1
x^2 ≡ 2 mod 17 の解は、x = 6
x^2 ≡ 4 mod 17 の解は、x = 2
x^2 ≡ 8 mod 17 の解は、x = 5
x^2 ≡ 9 mod 17 の解は、x = 3
x^2 ≡ 13 mod 17 の解は、x = 8
x^2 ≡ 15 mod 17 の解は、x = 7
x^2 ≡ 16 mod 17 の解は、x = 4
i= 18 [0, 1, 4, 7, 9, 10, 13, 16]
x^2 ≡ 0 mod 18 の解は、x = 0
x^2 ≡ 1 mod 18 の解は、x = 1
x^2 ≡ 4 mod 18 の解は、x = 2
x^2 ≡ 7 mod 18 の解は、x = 5
x^2 ≡ 9 mod 18 の解は、x = 3
x^2 ≡ 10 mod 18 の解は、x = 8
x^2 ≡ 13 mod 18 の解は、x = 7
x^2 ≡ 16 mod 18 の解は、x = 4
i= 19 [0, 1, 4, 5, 6, 7, 9, 11, 16, 17]
x^2 ≡ 0 mod 19 の解は、x = 0
x^2 ≡ 1 mod 19 の解は、x = 1
x^2 ≡ 4 mod 19 の解は、x = 2
x^2 ≡ 5 mod 19 の解は、x = 9
x^2 ≡ 6 mod 19 の解は、x = 5
x^2 ≡ 7 mod 19 の解は、x = 8
x^2 ≡ 9 mod 19 の解は、x = 3
x^2 ≡ 11 mod 19 の解は、x = 7
x^2 ≡ 16 mod 19 の解は、x = 4
x^2 ≡ 17 mod 19 の解は、x = 6
(k/p) = (0/3) = 0
(k/p) = (1/3) = 1
(k/p) = (2/3) = -1
(k/p) = (3/3) = 0
(k/p) = (0/5) = 0
(k/p) = (1/5) = 1
(k/p) = (2/5) = -1
(k/p) = (3/5) = -1
(k/p) = (4/5) = 1
(k/p) = (5/5) = 0
(k/p) = (0/7) = 0
(k/p) = (1/7) = 1
(k/p) = (2/7) = 1
(k/p) = (3/7) = -1
(k/p) = (4/7) = 1
(k/p) = (5/7) = -1
(k/p) = (6/7) = -1
(k/p) = (7/7) = 0
(k/p) = (0/11) = 0
(k/p) = (1/11) = 1
(k/p) = (2/11) = -1
(k/p) = (3/11) = 1
(k/p) = (4/11) = 1
(k/p) = (5/11) = 1
(k/p) = (6/11) = -1
(k/p) = (7/11) = -1
(k/p) = (8/11) = -1
(k/p) = (9/11) = 1
(k/p) = (10/11) = -1
(k/p) = (11/11) = 0
(k/p) = (0/13) = 0
(k/p) = (1/13) = 1
(k/p) = (2/13) = -1
(k/p) = (3/13) = 1
(k/p) = (4/13) = 1
(k/p) = (5/13) = -1
(k/p) = (6/13) = -1
(k/p) = (7/13) = -1
(k/p) = (8/13) = -1
(k/p) = (9/13) = 1
(k/p) = (10/13) = 1
(k/p) = (11/13) = -1
(k/p) = (12/13) = 1
(k/p) = (13/13) = 0
(k/p) = (0/17) = 0
(k/p) = (1/17) = 1
(k/p) = (2/17) = 1
(k/p) = (3/17) = -1
(k/p) = (4/17) = 1
(k/p) = (5/17) = -1
(k/p) = (6/17) = -1
(k/p) = (7/17) = -1
(k/p) = (8/17) = 1
(k/p) = (9/17) = 1
(k/p) = (10/17) = -1
(k/p) = (11/17) = -1
(k/p) = (12/17) = -1
(k/p) = (13/17) = 1
(k/p) = (14/17) = -1
(k/p) = (15/17) = 1
(k/p) = (16/17) = 1
(k/p) = (17/17) = 0
(k/p) = (0/19) = 0
(k/p) = (1/19) = 1
(k/p) = (2/19) = -1
(k/p) = (3/19) = -1
(k/p) = (4/19) = 1
(k/p) = (5/19) = 1
(k/p) = (6/19) = 1
(k/p) = (7/19) = 1
(k/p) = (8/19) = -1
(k/p) = (9/19) = 1
(k/p) = (10/19) = -1
(k/p) = (11/19) = 1
(k/p) = (12/19) = -1
(k/p) = (13/19) = -1
(k/p) = (14/19) = -1
(k/p) = (15/19) = -1
(k/p) = (16/19) = 1
(k/p) = (17/19) = 1
(k/p) = (18/19) = -1
(k/p) = (19/19) = 0
今回は力尽きてこれでおしまいにします。後半のヤコビ記号の計算をするプログラムを作っていないのはナイショです。それではまた。