anomalous curve - crypto-writeup-public

EllipticCurveにおいて、 $E(F_p).order() == p$ であるようなもの、flobenious traceが1であるような曲線。このような曲線に対しては、SSSAAttackやSmart Attackによって、離散対数問題が多項式時間で解ける

楕円曲線 $E(F_p)$ の位数が $p$ であるとき、そのような $p$ をanomalous primeといい、また、 $y^x \equiv x^3 + B \mod p$ の形のanomalous curve（Bachet anomalous curve）が存在する $p$ を特にBachet anomalous primeと言う。Bachet anomalous primeは必ず中心つき六角数(centered hexagonal number）の形（ $3x^2 + 3x + 1$ ）の形をしており、また、逆も然りである（中心つき六角数が素数または素数の冪乗なら、かならずその値にたいしてanomalous curveが存在する）。

（ちなみに、Tidjeman-Zagier Conjectureより $p^r = (n+1)^3 - n^3$ を満たすような $r$ は $r = 1, 2$ のみである）

これを使ったanomalous curveの構築はこちら

# https://math.boisestate.edu/reu/publications/AnomalousPrimesAndEllipticCarmichaelNumbers.pdf

from sage.all import *
while True:
    n = ZZ.random_element(2**200)
    p = (n + 1) ** 3 - n ** 3
    if is_prime(p):
        break

for i in range(1,100):
    E = EllipticCurve(GF(p), [0, i])
    if E.order() == p:
        print(0)
        print(i)
        print(p)
        g = E.gens()[0]
        print(g[0])
        print(g[1])

わからんけど次のようにすると好きなj-invariant を持ったanomalous curveが構築できるらしい。