pubkeys.py

import secrets

# secp256k1 parameters
p = 2**256 - 2**32 - 977
a = 0
b = 7

def random_256bit_int():
    # random 32-byte string interpreted as big-endian integer
    return int.from_bytes(secrets.token_bytes(32), "big")

def is_field_element(x):
    # valid field element if in [0, p-1]
    return 0 <= x < p

def has_curve_point(x):
    """
    Returns True if there exists a y such that y^2 = x^3 + 7 (mod p).
    Uses Euler's criterion to test if RHS is a quadratic residue.
    """
    rhs = (pow(x, 3, p) + b) % p
    if rhs == 0:
        return True
    ls = pow(rhs, (p - 1) // 2, p)
    # 1  -> quadratic residue
    # p-1-> non-residue
    return ls == 1

def experiment(trials=100_000):
    invalid_field = 0
    valid_field = 0
    valid_point  = 0

    for _ in range(trials):
        x = random_256bit_int()

        if not is_field_element(x):
            invalid_field += 1
            continue

        valid_field += 1

        if has_curve_point(x):
            valid_point += 1

    print(f"Trials: {trials}")
    print(f"Invalid field elements: {invalid_field} "
          f"({invalid_field / trials:.3e})")
    print(f"Valid field elements:   {valid_field} "
          f"({valid_field / trials:.6f})")
    print(f"Valid curve points:     {valid_point} "
          f"({valid_point / valid_field:.6f} of valid field elements)")

if __name__ == "__main__":
    experiment(100_000)