PSW $620 pseudoprime

"""Verifier for "PSW $620 pseudoprime" (statement in psw_620.json).

Background: for a number n that leaves remainder 2 or 3 when divided by 5,
every prime n passes both of these tests:

    Fermat test (base 2):  2**(n - 1) == 1  (mod n)
    Fibonacci test:        F(n + 1)   == 0  (mod n)

where F is the Fibonacci sequence F(0) = 0, F(1) = 1, F(k+1) = F(k) + F(k-1).

Problem: find a composite (non-prime) odd n with n % 5 in (2, 3) that passes
both tests anyway. Pomerance, Selfridge and Wagstaff offer $620 for one.
Since primes pass both tests, the solver must also prove that n is composite
by giving a factor: a number f with 1 < f < n that divides n.

Expected submission: a JSON object with two decimal strings:

    {"n": "1387", "factor": "19"}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the keys "n" and "factor".
  2. Both are well-formed non-negative decimal strings of at most MAX_DIGITS
     digits (see _parse_int).
  3. n is odd and n % 5 is 2 or 3.
  4. 1 < factor < n and factor divides n, which proves n is composite.
  5. The Fermat test passes (if CHECK_FERMAT).
  6. The Fibonacci test passes (if CHECK_FIBONACCI).

The two tests cost roughly the cube of the number of digits of n, which is why
MAX_DIGITS is 1,000 (about 0.2 s) rather than 10,000 (about a minute).
"""
import json

# Switches for the two tests. The real problem needs both. The tests turn one
# off at a time to check known numbers that pass only the other one:
# 1387 = 19 * 73 passes the Fermat test only, 323 = 17 * 19 the Fibonacci test only.
CHECK_FERMAT = True
CHECK_FIBONACCI = True
# Maximum number of digits of n (and of the factor). Checking a 1,500-digit n
# takes about 2 s; if you raise this, raise MAX_BYTES as well.
MAX_DIGITS = 1_000
# Maximum size of the whole submission, in characters.
MAX_BYTES = 3_000


# ---------------------------------------------------------------------------
# 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


def _fib_mod(k, m):
    """Return F(k) mod m, the k-th Fibonacci number reduced modulo m.

    k can have thousands of digits, so F(k) itself can never be computed. The
    "fast doubling" method uses these two identities:

        F(2j)     = F(j) * (2 * F(j+1) - F(j))
        F(2j + 1) = F(j)**2 + F(j+1)**2

    The loop keeps the pair (a, b) = (F(j), F(j+1)), starting from j = 0, and
    reads the binary digits of k from the most significant one. For each
    digit, j is doubled, then increased by 1 if the digit is 1. After the last
    digit j == k. All arithmetic is done modulo m, so the numbers never grow
    beyond the size of m. The loop runs once per binary digit of k.
    """
    a, b = 0, 1  # (F(0), F(1))
    for bit in bin(k)[2:]:  # binary digits of k, most significant first
        c = a * ((2 * b - a) % m) % m  # F(2j) mod m
        d = (a * a + b * b) % m  # F(2j + 1) mod m
        if bit == "1":
            a, b = d, (c + d) % m  # move to j = 2j + 1: (F(2j+1), F(2j+2))
        else:
            a, b = c, d  # move to j = 2j: (F(2j), F(2j+1))
    return a


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

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

    # Step 3: n must be odd and leave remainder 2 or 3 when divided by 5; the
    # Fibonacci test only has its meaning for such n.
    if n % 2 == 0 or n % 5 not in (2, 3):
        return False

    # Step 4: the factor must be a proper divisor of n, proving n is composite.
    if not (1 < f < n) or n % f != 0:
        return False

    # Step 5: Fermat test. Python's three-argument pow never forms the huge
    # number 2**(n - 1); it works modulo n throughout.
    if CHECK_FERMAT and pow(2, n - 1, n) != 1:
        return False

    # Step 6: Fibonacci test: n must divide F(n + 1).
    if CHECK_FIBONACCI and _fib_mod(n + 1, n) != 0:
        return False

    # A composite n passing every enabled test: a genuine solution.
    return True


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