Day 159-Q3 — 2026-09-24 — Lenstra の楕円曲線法（ECM・「群の位数を曲線ごとに引き直せる」Pollard p−1）

📋 コピーimport sys, random, math


class Found(Exception):
    def __init__(self, f):
        self.f = f


def inv(x, n):
    x %= n
    g = math.gcd(x, n)
    if g != 1:
        raise Found(g)          # g == n のときは呼び出し側が「この曲線は失敗」と扱う
    return pow(x, -1, n)


def ec_add(P, Q, a, n):
    """アフィン Weierstrass 曲線 y^2 = x^3 + a x + b 上の加法（mod n）。None は無限遠点。"""
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2:
        if (y1 + y2) % n == 0:
            return None
        lam = (3 * x1 * x1 + a) * inv(2 * y1, n) % n
    else:
        lam = (y2 - y1) * inv(x2 - x1, n) % n
    x3 = (lam * lam - x1 - x2) % n
    return (x3, (lam * (x1 - x3) - y1) % n)


def ec_mul(k, P, a, n):
    R = None
    while k:
        if k & 1:
            R = ec_add(R, P, a, n)
        P = ec_add(P, P, a, n)
        k >>= 1
    return R


def primes_upto(B):
    s = bytearray([1]) * (B + 1); s[0] = s[1] = 0
    for i in range(2, int(B ** 0.5) + 1):
        if s[i]:
            s[i * i::i] = bytearray(len(s[i * i::i]))
    return [i for i in range(B + 1) if s[i]]


def ecm(n, B1=2000, curves=1000, rng=random.Random(159)):
    ps = primes_upto(B1)
    for _ in range(curves):
        x = rng.randrange(n); y = rng.randrange(n); a = rng.randrange(n)
        b = (y * y - x * x * x - a * x) % n           # P=(x,y) が曲線に乗るよう b を決める
        g = math.gcd(4 * a * a * a + 27 * b * b, n)   # 特異曲線を除く
        if 1 < g < n:
            return g
        if g == n:
            continue
        P = (x, y)
        try:
            for p in ps:                               # ステージ1: P <- lcm(1..B1) * P
                pk = p
                while pk * p <= B1:
                    pk *= p
                P = ec_mul(pk, P, a, n)
                if P is None:
                    break                              # mod n でも無限遠点 = 両方の素因数で同時に消えた
        except Found as e:
            if 1 < e.f < n:
                return e.f
            # e.f == n: 両方の法で同時に無限遠点。曲線を替える
    return None


def main():
    n = int(sys.stdin.readline())
    if n % 2 == 0:
        print(2); return
    f = ecm(n)
    print(f)


main()