ぼくがかんがえたさいきょうの偶奇判定

_even_and_odd_judgment.md

「有限体 $\mathbb{F}_5$ 上の楕円曲線 $E: y^2 = x^3 + ax + b$ (ここでは $a=0, b=2$)」における点の加法演算やスカラー倍演算(点を何倍するか)を定義し、それを使って「ある点 $G=(2,0)$」の何倍かを計算することで、整数 $n$ が「奇数か偶数か」を判定しています。

main.py

MOD = 5
a = 0
b = 2

# 無限遠点(群の恒等元)を None として表現
INF = None

def ec_add(P, Q):
    """有限体上の楕円曲線 E: y^2 = x^3 + a x + b における点 P, Q の加法"""
    if P is INF:
        return Q
    if Q is INF:
        return P
    
    xP, yP = P
    xQ, yQ = Q
    
    # P と Q が x 座標同じ & y 座標が符号反転 (yQ = -yP) => 足すと無限遠点
    if xP == xQ and (yP + yQ) % MOD == 0:
        return INF
    
    if P != Q:
        # P != Q => 通常の加法
        #  slope = (yQ - yP) / (xQ - xP)
        inv = pow(xQ - xP, MOD-2, MOD)
        m = ((yQ - yP) * inv) % MOD
    else:
        # P == Q => 2倍 (自分自身との加法)
        #  slope = (3*xP^2 + a) / (2*yP)
        if yP == 0:
            # y=0 の点は位数2の場合が多く、2倍すると無限遠へ
            return INF
        inv = pow(2*yP, MOD-2, MOD)
        m = ((3 * (xP ** 2) + a) * inv) % MOD

    xR = (m*m - xP - xQ) % MOD
    yR = (m * (xP - xR) - yP) % MOD
    return (xR, yR)

def ec_scalar_mult(P, n):
    """点 P を n 倍する(双対アルゴリズム)"""
    R = INF
    Q = P
    while n > 0:
        if n & 1:
            R = ec_add(R, Q)
        Q = ec_add(Q, Q)
        n >>= 1
    return R

# 楕円曲線上の点 G = (2,0). これが位数2 (2G = INF)
G = (2, 0)

def is_odd(n: int) -> bool:
    # nG が無限遠点(INF)なら n は偶数, そうでなければ奇数
    return ec_scalar_mult(G, n) != INF

if __name__ == "__main__":
    for i in range(1, 101):
        print(i, is_odd(i))