Third Wieferich prime

"""Verifier for "Third Wieferich prime" (statement in wieferich_third.json).

Problem: find a prime p with 2**64 < p < 10**24 such that

    2**(p - 1) == 1   (mod p**2)

Primes with this property are called Wieferich primes. By Fermat's little
theorem every odd prime satisfies 2**(p - 1) == 1 (mod p); Wieferich primes
satisfy it modulo p**2 as well. Only two are known, 1093 and 3511, and every
prime below 2**64 has already been checked.

Expected submission: a JSON object with one decimal string:

    {"p": "20000000000000000000"}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the key "p".
  2. p is a well-formed non-negative decimal string of at most MAX_DIGITS
     digits (see _parse_int).
  3. MIN_P < p < MAX_P, both bounds strict.
  4. p is prime. Because p < 10**24, sympy's isprime gives a proven answer:
     below about 3.3 * 10**24 it uses a Miller-Rabin test with a set of bases
     known to be exact, rather than a probabilistic test.
  5. 2**(p - 1) mod p**2 equals 1. Python's three-argument pow computes this
     directly without ever forming the huge number 2**(p - 1).
"""
import json

from sympy import isprime

# Lower bound (exclusive). 2**64 skips the range already searched, which also
# excludes the known Wieferich primes 1093 and 3511. The tests set it to 0 to
# check that those two known primes are accepted.
MIN_P = 2**64
# Upper bound (exclusive). Keep it below about 3.3 * 10**24: above that,
# sympy's isprime is no longer guaranteed to be exact.
MAX_P = 10**24
# p < 10**24 has at most 24 digits, so longer strings are rejected at parse time.
MAX_DIGITS = 24
# Maximum size of the whole submission, in characters.
MAX_BYTES = 100


# ---------------------------------------------------------------------------
# Input-parsing helpers. The same code is copied into every verifier so that
# each file works on its own.
# ---------------------------------------------------------------------------

def _parse_int(s, max_digits, allow_neg=False):
    """Convert a strictly formatted decimal string to an int, or raise ValueError.

    Accepted: "0", "42", and "-42" when allow_neg is True.
    Rejected: anything that is not a string (for example a JSON number), "",
    "+42", " 42", "007", "-0", non-ASCII digits such as "٣", and strings with
    more than max_digits digits.
    """
    # Cheap length check before any real work: at most max_digits digits,
    # plus one character for an optional minus sign.
    if not isinstance(s, str) or len(s) > max_digits + 1:
        raise ValueError
    # Split off the sign. A "-" is only allowed where negative values make sense.
    neg = s.startswith("-")
    if neg and not allow_neg:
        raise ValueError
    body = s[1:] if neg else s
    # What remains must be 1 to max_digits ASCII digits with no leading zero
    # ("0" on its own is fine). isascii() is needed because isdigit() also
    # accepts digits from other scripts.
    if not (body.isascii() and body.isdigit()) or len(body) > max_digits or (len(body) > 1 and body[0] == "0"):
        raise ValueError
    # "-0" is not a canonical way to write zero.
    if neg and body == "0":
        raise ValueError
    # Python (3.11 and later) refuses int() on strings longer than 4300 digits
    # by default, so the number is built from chunks of 4000 digits.
    n = 0
    for i in range(0, len(body), 4000):
        chunk = body[i:i + 4000]
        n = n * 10 ** len(chunk) + int(chunk)
    return -n if neg else n


def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if not isinstance(solution, str) or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution)
    # It must be an object (not a list, string or number) whose keys are
    # exactly the expected ones: nothing missing, nothing extra.
    if not isinstance(d, dict) or set(d) != set(keys):
        raise ValueError
    return d


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    # Steps 1-2: read the JSON object and parse p.
    sol = _load(solution, ("p",), MAX_BYTES)
    p = _parse_int(sol["p"], MAX_DIGITS)

    # Steps 3-4: p must lie strictly between the bounds and be prime.
    if not (MIN_P < p < MAX_P) or not isprime(p):
        return False

    # Step 5: the Wieferich condition, 2**(p - 1) mod p**2 == 1.
    return pow(2, p - 1, p * p) == 1


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic. Any exception (malformed JSON, a bad
    number, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False