1"""secp256k1 domain parameters (SEC 2 v2.0, §2.4.1) and exact verification of their algebraic properties."""2from __future__ import annotations3from .ec import Curve, cube_roots_of_unity, legendre45p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F6a = 07b = 78Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F817989Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B810n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036414111h = 112# GLV endomorphism constants as used by libsecp256k1 (Hankerson–Menezes–Vanstone, Alg. 3.74; Gallant–Lambert–Vanstone 2001)13beta = 0x7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE14lam = 0x5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD7215# a basis of the GLV lattice {(k1,k2): k1 + k2·λ ≡ 0 mod n} as published in libsecp256k1 (scalar_impl.h)16a1 = 0x3086D221A7D46BCDE86C90E49284EB1517b1 = -0xE4437ED6010E88286F547FA90ABFE4C318a2 = 0x114CA50F7A8E2F3F657C1108D9D44CFD819b2 = a12021CURVE = Curve(p, a, b, n=n, h=h, G=(Gx, Gy), name="secp256k1")222324def verify_parameters() -> dict:25 """Exact checks on the standard parameters. Returns a dictionary of named boolean/int facts."""26 from sympy import isprime, factorint27 E = CURVE28 facts = {}29 facts["p_is_prime"] = bool(isprime(p))30 facts["p_equals_2^256-2^32-977"] = p == 2**256 - 2**32 - 97731 facts["p_mod_3"] = p % 332 facts["p_mod_4"] = p % 433 facts["n_is_prime"] = bool(isprime(n))34 facts["G_on_curve"] = E.is_on_curve(E.G)35 facts["nG_is_infinity"] = E.mul(n, E.G) is None36 facts["cofactor"] = h37 facts["discriminant_nonzero"] = E.discriminant() != 038 facts["j_invariant"] = E.j_invariant()39 t = p + 1 - n # trace of Frobenius (cofactor 1 ⇒ #E = n)40 facts["trace_t"] = t41 facts["hasse_bound_ok"] = abs(t) <= 2 * (p ** 0.5 + 1) # float only as a sanity bound; exact check below42 facts["hasse_exact"] = t * t <= 4 * p43 facts["anomalous"] = n == p44 disc = t * t - 4 * p45 facts["frobenius_discriminant"] = disc46 # CM discriminant: t² − 4p = −3·f² for a j = 0 ordinary curve (End ≅ Z[ω])47 f2 = (-disc) // 348 import math49 f = math.isqrt(f2)50 facts["disc_is_minus3_times_square"] = (-disc) % 3 == 0 and f * f == f251 facts["conductor_f"] = f52 # Cube roots of unity: beta³ ≡ 1 (mod p), lam³ ≡ 1 (mod n), and beta, lam ≠ 153 facts["beta_cubed_is_1_mod_p"] = pow(beta, 3, p) == 1 and beta != 154 facts["lambda_cubed_is_1_mod_n"] = pow(lam, 3, n) == 1 and lam != 155 facts["beta^2+beta+1=0 mod p"] = (beta * beta + beta + 1) % p == 056 facts["lambda^2+lambda+1=0 mod n"] = (lam * lam + lam + 1) % n == 057 # The endomorphism φ(x,y) = (βx, y) equals [λ] on G (and hence on the whole cyclic group)58 phiG = (beta * Gx % p, Gy)59 facts["phi_G_on_curve"] = E.is_on_curve(phiG)60 facts["phi_G_equals_lambda_G"] = E.mul(lam, E.G) == phiG61 # The other pairing (β², λ²) also holds; (β, λ²) does not62 facts["phi2_G_equals_lambda2_G"] = E.mul(lam * lam % n, E.G) == (beta * beta % p * Gx % p, Gy)63 facts["beta_lambda2_mismatch"] = E.mul(lam * lam % n, E.G) != phiG64 # GLV lattice basis: a_i + b_i·λ ≡ 0 (mod n), determinant = n65 facts["glv_basis_v1"] = (a1 + b1 * lam) % n == 066 facts["glv_basis_v2"] = (a2 + b2 * lam) % n == 067 facts["glv_basis_det_is_n"] = abs(a1 * b2 - a2 * b1) == n68 # Points with x = 0 exist iff 7 is a quadratic residue; none ⇒ no 3-torsion visible on x = 069 facts["x0_points_exist"] = legendre(7, p) == 170 # Embedding degree (MOV/Frey–Rück): smallest k ≤ 100 with n | p^k − 171 k = None72 for kk in range(1, 101):73 if pow(p, kk, n) == 1:74 k = kk75 break76 facts["embedding_degree_le_100"] = k77 # Twist order and its factorisation of the small part78 twist = 2 * p + 2 - n79 facts["twist_order"] = twist80 small = factorint(twist, limit=10**6)81 cof = 182 for q, e in small.items():83 if q > 10**6:84 cof = q ** e85 facts["twist_small_factors"] = {str(q): e for q, e in small.items() if q <= 10**6}86 facts["twist_cofactor_bits"] = cof.bit_length()87 facts["twist_cofactor_is_prime"] = bool(isprime(cof))88 # n − 1 and p − 1 small-factor structure (relevant to Pohlig–Hellman in F_n* / F_p*)89 facts["n_minus_1_small_factors"] = {str(q): e for q, e in factorint(n - 1, limit=10**6).items() if q <= 10**6}90 facts["p_minus_1_small_factors"] = {str(q): e for q, e in factorint(p - 1, limit=10**6).items() if q <= 10**6}91 return facts929394def glv_decompose(k: int) -> tuple[int, int]:95 """Decompose k ≡ k1 + k2·λ (mod n) with |k1|,|k2| ≈ √n using the published lattice basis (Babai rounding)."""96 # Following GLV (2001): c1 = round(b2·k/n), c2 = round(−b1·k/n); k1 = k − c1·a1 − c2·a2; k2 = −c1·b1 − c2·b297 c1 = (b2 * k + n // 2) // n98 c2 = (-b1 * k + n // 2) // n99 k1 = k - c1 * a1 - c2 * a2100 k2 = -c1 * b1 - c2 * b2101 assert (k1 + k2 * lam - k) % n == 0102 return k1, k2103