素数
確かめてみる。
まず、もし
となって
を得る。ここで、
から
を得る。ゆえに、いずれの場合も
逆に、
を満たす整数
の判別式は
という整数
ところで、
であり、
を満たす整数
あとは、いずれに該当するかを調べればいい。これについても平方剰余記号を使って調べられる。
証明には
のどれかになること。これは、
と書けることからわかる。これを
今年の素数年でやってみる。
こんな感じ。
この3つ。
はじめに、何らかの方法で1~10000の間の素数を
def getLargePrimes(p, a, b):
# 1~100000000のうち、aとbの間にあるものを抽出する感じ。
# pには1~10000の中の素数がすべて入っているとする。
result = []
for i in range(a, b):
isPrime = True
for k in p:
if k * k > i: break
if i % k == 0:
isPrime = False
break
if isPrime:
result.append(i)
return result
その中から然るべきモジュロの素数を出してからは、次のコードで
を用いて欲しい値を出す。そのために
def routine(q):
# まずa, b, cを出すには、モジュロqでの15の平方根を出す必要がある。
# それをbとし、aはqで、cについては15=b^2-acから出す。すなわちc=(b^2-15)/q.
b = 0
for i in range(q):
if i * i % q == 15:
b = q - i
break
a = q
c = int((b*b - 15) / q)
# 2次形式(a, b, c)を簡約してaが±1か±2になるようにする感じ。
# 各ステップでは新しい(c, b', a')をまずb'がbと|c|でモジュロで同じでかつ
# 2|b'|≦|c|となるようにする。で、b'^2-a'c=15からa'を出す。
# そのあとn=(b-b')/cを出してx'=nx+y, y'=xと変換する(x=1,y=0からスタート)。
# 最後にxとyを出力して終了。
x=1
y=0
for i in range(100):
if abs(a)==1 or abs(a)==2: break
if int(b) == 0: break
b2 = b % abs(c)
a2 = int((b2*b2-15) / c)
n = (b - b2) / c
a = c
b = b2
c = a2
z = x
x = n * x + y
y = z
print("(x, y) = (" + str(x) + ", " + str(y) + ")")
print("(x-y, x-2y) = (" + str(x-y) + ", " + str(x-2*y) + ")")
print("(x+2y, x+y) = (" + str(x+2*y) + ", " + str(x+y) + ")")
print(a, b, c)
def main():
routine(20200903)
"""
出力結果:
(x, y) = (289.0, 1665.0)
(x-y, x-2y) = (-1376.0, -3041.0)
(x+2y, x+y) = (3619.0, 1954.0)
-2 1 7
-2 1 7なので(x+2y, x+y)を採用。
"""
以上です。ここまでお読みいただきありがとうございました。