1import random, sys, pathlib2sys.path.insert(0, str(pathlib.Path(__file__).resolve().parents[1] / "src"))3from wp34.ec import Curve, random_prime_order_curve4from wp34 import dlp567def _instance(bits, seed, j0=False):8 rng = random.Random(seed)9 E = random_prime_order_curve(bits, rng, j0=j0)10 d = rng.randrange(1, E.n)11 return E, d, E.mul(d, E.G)121314def test_bsgs_rho_kangaroo_agree():15 for seed in range(3):16 E, d, Q = _instance(22, seed)17 assert dlp.bsgs(E, E.G, Q)[0] == d18 assert dlp.pollard_rho(E, E.G, Q, seed=seed)[0] == d19 assert dlp.pollard_rho_dp(E, E.G, Q, dp_bits=3, walks=4, seed=seed)[0] == d20 assert dlp.pollard_rho_dp(E, E.G, Q, dp_bits=3, walks=4, seed=seed, neg_map=True)[0] == d21 assert dlp.kangaroo(E, E.G, Q, 0, E.n - 1, seed=seed)[0] == d22 lo = max(0, d - 2**12); hi = lo + 2**1323 assert dlp.kangaroo(E, E.G, Q, lo, hi, seed=seed)[0] == d242526def test_bsgs_memory_tradeoff():27 E, d, Q = _instance(20, 9)28 for m in [2**6, 2**8, 2**10, 2**12]:29 dd, st = dlp.bsgs(E, E.G, Q, m=m)30 assert dd == d and st["memory_entries"] == m313233def test_pohlig_hellman_small():34 E = Curve(10007, 1, 6)35 N = E.count_points_naive()36 rng = random.Random(4)37 P = E.random_point(rng)38 order = E.order_of_point(P, bound=N + 1)39 d = rng.randrange(1, order)40 Q = E.mul(d, P)41 assert dlp.pohlig_hellman(E, P, Q, order)[0] == d42