padic ecdlp

padic_ecdlp.sage

# padic ecdlp
# combines https://hackmd.io/@mitsu/ByhK-tZX_ and proposition 4 from https://arxiv.org/pdf/2010.15543


def gen_problem(p, k):
    R = Zmod(p**k)
    S = (randint(1, p), randint(1, p))
    a1 = randint(1, p)
    a2 = R(S[1] ** 2 - (S[0] ** 3 + a1 * S[0]))
    E = EllipticCurve(R, [a1, a2])

    m = randint(1, p ** (k - 1))
    S = E(S)
    T = m * S
    return E, S, T


def padic_ecdlp(p, k, E, S, T):
    # find m (mod p^(k-1)) such that m*S=T
    n = E.change_ring(GF(p)).order()
    Eqp = E.change_ring(Qp(p, k))
    Sx = Eqp(S) * n
    Tx = Eqp(T) * n
    phi = lambda P: P[0] / P[1]

    base = p**4
    ds = []
    while Tx != 0:
        r = ZZ(phi(Tx) / phi(Sx)) % base
        ds.append(r)
        Tx -= r * Sx
        Sx *= base
    return sum([x * base**i for i, x in enumerate(ds)])


k = 21
p = random_prime(1 << 64)
E, S, T = gen_problem(p, k)
rm = padic_ecdlp(p, k, E, S, T)
assert rm * S == T
rm2 = padic_ecdlp(p, k, E, S, T + 123 * p ** (k - 1) * S)
assert rm2 == rm