Skip to content

Instantly share code, notes, and snippets.

@maple3142

maple3142/padic_ecdlp.sage

Created April 8, 2025 06:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save maple3142/24ed4621e8b8c9839bb100a0236235a2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save maple3142/24ed4621e8b8c9839bb100a0236235a2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. maple3142 created this gist Apr 8, 2025.
    42 changes: 42 additions & 0 deletions padic_ecdlp.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,42 @@
    # 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