"""Reproduces Part B of the study "How encryption software tests for prime numbers, and what a proof of
the generalized Riemann hypothesis would change" (https://vaultan.app/research/prime-testing-grh/).

What it does, for each size of number (512 to 4096 bits):

  computed   B = floor(2 * (ln n)^2) for the largest n of that size (n = 2^bits - 1), which is Bach's
             bound for Miller's test under the generalized Riemann hypothesis (Bach 1990): a composite n
             has a witness no larger than B. The number of bases 2..B, and the number of primes up to B.
  measured   the time of one Miller-Rabin round (one modular exponentiation plus squarings) on a real
             prime of that size, on this machine, with GMP through gmpy2: the median and the mean of
             ROUND_SAMPLES rounds. On a shared machine the mean is higher than the median because of
             pauses; whole-test times are wall-clock, so compare them with the mean.
  measured   for the sizes in FULL: the wall-clock time of the whole deterministic Miller test with every
             prime base up to B, run to the end on that prime.
  estimated  for the other sizes: the time of the whole test, from SAMPLE evenly spaced prime bases
             (seconds per base, times the number of prime bases). Marked "extrapolated" in the output.
  estimated  the time with every integer base 2..B (seconds per base times the number of bases).

Usage:   pip install gmpy2
         python3 prime-testing-grh.py            # about 25 minutes on a 2-core cloud machine
         python3 prime-testing-grh.py --quick    # only 512 and 1024 bits in full, the rest sampled
Output:  prime-testing-grh-computed.json and prime-testing-grh.csv in the current folder.

In the website repository (website/research/code/), the script also writes its output into the study's data
file, website/research/prime-testing-grh.json, as the "computation" block, replacing the previous run. That is
the only step: `python3 website/build.py` then publishes the data file and builds the page and both CSV files
(prime-testing-grh.csv from this block, prime-testing-grh-libraries.csv from the library data) from it. A
--quick run never touches the data file. Pass --no-study to leave it alone in any case.

The machine's load average (1-minute, from the operating system) is recorded at the start, after each size and
at the end, so a reader can see how busy the machine was. The run itself keeps one core busy, so on an
otherwise idle machine the 1-minute figure settles near 1.

Timings depend on the machine; the counts of bases do not. The seed is fixed, so the same primes are tested.
No network access; the only file read is the study's data file, when it is there.
"""
import csv
import json
import math
import os
import pathlib
import platform
import random
import statistics
import sys
import time

import gmpy2
from gmpy2 import mpz

SIZES = [512, 1024, 1536, 2048, 3072, 4096]
FULL = [512, 1024, 1536, 2048]      # deterministic test run to the end
SAMPLE = 2000                        # prime bases timed for the sizes that are extrapolated
ROUND_SAMPLES = 200                  # random-base rounds timed for the per-round figure
SEED = 20261120
STUDY = pathlib.Path(__file__).resolve().parent.parent / 'prime-testing-grh.json'


def bach_bound(bits):
    """floor(2 * (ln n)^2) for n = 2^bits - 1, with 200-bit floating point."""
    with gmpy2.context(gmpy2.get_context(), precision=200):
        ln_n = gmpy2.log(mpz(2) ** bits - 1)
        return int(gmpy2.floor(2 * ln_n * ln_n))


def primes_up_to(limit):
    sieve = bytearray([1]) * (limit + 1)
    sieve[0:2] = b'\x00\x00'
    for i in range(2, math.isqrt(limit) + 1):
        if sieve[i]:
            sieve[i * i::i] = bytearray(len(range(i * i, limit + 1, i)))
    return [i for i in range(2, limit + 1) if sieve[i]]


def random_prime(bits, rng):
    """A prime of exactly `bits` bits with the top two bits set, the shape RSA key generation uses."""
    while True:
        c = mpz(rng.getrandbits(bits)) | (mpz(3) << (bits - 2)) | 1
        p = gmpy2.next_prime(c - 2)
        if p.bit_length() == bits:
            return p


def miller_round(n, d, s, a):
    """One round of the Miller-Rabin test of odd n to base a, with n - 1 = 2^s * d. True if n passes."""
    x = gmpy2.powmod(a, d, n)
    if x == 1 or x == n - 1:
        return True
    for _ in range(s - 1):
        x = gmpy2.powmod(x, 2, n)
        if x == n - 1:
            return True
    return False


def split(n):
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    return d, s


def main():
    quick = '--quick' in sys.argv
    full = [512, 1024] if quick else FULL
    rng = random.Random(SEED)
    rows = []
    loads = [os.getloadavg()[0]]
    all_primes = primes_up_to(bach_bound(max(SIZES)))
    for bits in SIZES:
        bound = bach_bound(bits)
        bases = [p for p in all_primes if p <= bound]
        n = random_prime(bits, rng)
        d, s = split(n)
        # one round with a random base, as libraries do it
        times = []
        for _ in range(ROUND_SAMPLES):
            a = mpz(rng.randrange(2, int(n) - 1))
            t = time.perf_counter()
            ok = miller_round(n, d, s, a)
            times.append(time.perf_counter() - t)
            assert ok
        round_s, round_mean = statistics.median(times), statistics.mean(times)
        if bits in full:
            t = time.perf_counter()
            passed = all(miller_round(n, d, s, mpz(a)) for a in bases)
            det_s = time.perf_counter() - t
            per_base = det_s / len(bases)
            how = 'measured'
            assert passed
        else:
            step = max(1, len(bases) // SAMPLE)
            sample = bases[::step]
            t = time.perf_counter()
            passed = all(miller_round(n, d, s, mpz(a)) for a in sample)
            per_base = (time.perf_counter() - t) / len(sample)
            det_s = per_base * len(bases)
            how = 'extrapolated'
            assert passed
        row = dict(bits=bits, bach_bound=bound, integer_bases=bound - 1, prime_bases=len(bases),
                   round_seconds_median=round_s, round_seconds_mean=round_mean, deterministic_prime_bases_seconds=det_s, deterministic_how=how,
                   bases_timed=len(bases) if how == 'measured' else len(sample),
                   seconds_per_small_base=per_base, deterministic_all_bases_seconds=per_base * (bound - 1),
                   tested_prime_hex=hex(int(n)))
        rows.append(row)
        loads.append(os.getloadavg()[0])
        print(json.dumps({k: v for k, v in row.items() if k != 'tested_prime_hex'}), 'load', loads[-1], flush=True)
        out = dict(seed=SEED, sizes=rows, machine=dict(cpu=cpu_name(), cores=cores(), python=platform.python_version(),
                                                       gmpy2=gmpy2.version(), gmp=gmpy2.mp_version(),
                                                       load_1min=dict(start=loads[0], max=max(loads[1:]), end=loads[-1],
                                                                      after_each_size=loads[1:])),
                   run_date=time.strftime('%Y-%m-%d', time.gmtime()), full_sizes=full, sample_bases=SAMPLE)
        json.dump(out, open('prime-testing-grh-computed.json', 'w'), indent=1)
    cols = [c for c in rows[0] if c != 'tested_prime_hex']
    with open('prime-testing-grh.csv', 'w', newline='') as f:
        w = csv.DictWriter(f, fieldnames=cols, extrasaction='ignore')
        w.writeheader()
        w.writerows(rows)
    if not quick and '--no-study' not in sys.argv and STUDY.exists():
        study = json.loads(STUDY.read_text(encoding='utf-8'))
        study['computation'] = out
        STUDY.write_text(json.dumps(study, indent=1, ensure_ascii=False), encoding='utf-8')
        print('wrote the computation block of', STUDY)


def cpu_name():
    try:
        for line in open('/proc/cpuinfo'):
            if line.startswith('model name'):
                return line.split(':', 1)[1].strip()
    except OSError:
        pass
    return platform.processor() or platform.machine()


def cores():
    import os
    return os.cpu_count()


if __name__ == '__main__':
    main()
