"""Finite worked-example checks. These do not establish cryptographic hardness."""
from fractions import Fraction as F
from collections import Counter
from itertools import product,combinations
import json,random
checks=[]
def eq(name,a,b):
 assert a==b,(name,a,b)
 checks.append({'name':name,'actual':str(a),'expected':str(b),'status':'pass'})
def chi(mask,r):return (-1)**((mask&r).bit_count()%2)
# Uniform-position next-bit prediction for the repeated first/last bit example.
zs=[tuple(x)+(x[0],) for x in product([0,1],repeat=3)]
accept=[]
for i in range(5):
 v=F(0)
 for z in zs:
  for tail in product([0,1],repeat=4-i):
   h=z[:i]+tail;v+=F(h[0]==h[-1],8*2**(4-i))
 accept.append(v)
eq('prefix hybrid accepting probabilities',accept,[F(1,2)]*4+[F(1)])
eq('telescoping total',sum(accept[i]-accept[i-1] for i in range(1,5)),F(1,2))
success=F(0)
for z in zs:
 for i in range(1,5):
  for b in range(2):
   for tail in product([0,1],repeat=4-i):
    trial=z[:i-1]+(b,)+tail;d=(trial[0]==trial[-1]);prediction=b if d else 1-b
    success+=F(prediction==z[i-1],8*4*2*2**(4-i))
eq('uniform-position predictor success',success,F(5,8))
# Goldreich-Levin toy randomized response function.
g=[F(2,5)*chi(5,r)+F(3,10)*chi(2,r) for r in range(8)]
coeff=[sum((g[r]*chi(a,r) for r in range(8)),F(0))/8 for a in range(8)]
eq('GL nonzero Fourier coefficients',{i:v for i,v in enumerate(coeff) if v},{2:F(3,10),5:F(2,5)})
eq('GL Parseval mean-square',sum(v*v for v in g)/8,F(1,4));eq('GL direction 101 success',(1+coeff[5])/2,F(7,10))
eps=F(1,20);good=eps/(1-eps);eq('capstone good-input fraction',good,F(1,19));eq('capstone list cap',2/eps**2,F(800));eq('capstone inversion success',F(2,3)*good,F(2,57))
# GGM toy paths.
def ggm(k,s):
 for b in s:k=(k+1)%4 if b=='0' else k^2
 return k
eq('GGM 001',ggm(1,'001'),1);eq('GGM 011',ggm(1,'011'),2);eq('GGM repeated 001',ggm(1,'001'),1)
# Feistel inversion for every 2-bit round function and every input.
def enc(L,R,fs):
 for f in fs:L,R=R,L^f[R]
 return L,R
def dec(L,R,fs):
 for f in reversed(fs):L,R=R^f[L],L
 return L,R
one_cases=0
for f in product(range(4),repeat=4):
 images=set()
 for L,R in product(range(4),repeat=2):
  out=enc(L,R,[f]);assert dec(*out,[f])==(L,R);images.add(out);one_cases+=1
 assert len(images)==16
checks.append({'name':'Feistel inverse for every 2-bit round function and input','cases':one_cases,'status':'pass'})
fs=[[1]*4,list(range(4)),[2]*4];trace=[(3,1)]
for f in fs:trace.append(enc(*trace[-1],[f]))
eq('article Feistel trace',trace,[(3,1),(1,2),(2,3),(3,0)])
rng=random.Random(6022);attack_cases=0
for _ in range(256):
 fs=[[rng.randrange(4) for _ in range(4)] for j in range(3)]
 for L,Lp,R in product(range(4),repeat=3):
  if L==Lp:continue
  a,b=enc(L,R,fs[:2]);ap,bp=enc(Lp,R,fs[:2]);assert a^ap==L^Lp
  b,c=enc(L,R,fs);bp,cp=enc(Lp,R,fs)
  if b==bp:continue
  crafted=(b,c^(L^Lp));assert crafted not in[(b,c),(bp,cp)]
  out=dec(*crafted,fs);assert out[1]==R^b^bp;attack_cases+=1
checks.append({'name':'Three-round inverse-query identity across random round tables','nondegenerate_cases':attack_cases,'status':'pass'})
fs=[[r^1 for r in range(4)],[(r+1)%4 for r in range(4)],[(2*r)%4 for r in range(4)]]
eq('capstone Feistel first ciphertext',enc(0,1,fs),(0,0));eq('capstone Feistel second ciphertext',enc(2,1,fs),(2,2));eq('capstone crafted inverse',dec(0,2,fs),(0,3))
# GF(4) with a^2+a+1=0, represented by low-bit coefficient of 1, high-bit coefficient of a.
def mul(a,b):
 p=0
 while b:
  if b&1:p^=a
  b>>=1;a<<=1
  if a&4:a^=7
 return p
outputs=Counter()
for a,b in product(range(4),repeat=2):
 z=tuple((v&b).bit_count()%2 for v in[1,a,mul(a,a)]);outputs[''.join(map(str,z))]+=1
eq('F4 outputs',dict(sorted(outputs.items())),{'000':6,'011':2,'100':2,'101':2,'110':2,'111':2})
bias={format(mask,'03b'):F(sum(count*chi(mask,int(z,2)) for z,count in outputs.items()),16) for mask in range(1,8)}
eq('F4 nonzero-character biases',bias,{'001':F(1,4),'010':F(1,4),'011':F(1,2),'100':F(0),'101':F(1,4),'110':F(1,4),'111':F(1,2)})
eq('F4 maximum bias',max(abs(v) for v in bias.values()),F(1,2));eq('F4 support-event advantage',F(1)-F(len(outputs),8),F(1,4))
eq('F4 total variation',sum(abs(F(outputs.get(format(z,'03b'),0),16)-F(1,8)) for z in range(8))/2,F(1,4))
eq('F4 alpha seed vector',tuple((v&1).bit_count()%2 for v in[1,2,mul(2,2)]),(1,0,1))
# All quadratic graphs over F5.
polys=list(product(range(5),repeat=3));sets=[{(x,(a+b*x+c*x*x)%5) for x in range(5)} for a,b,c in polys]
eq('NW set count',len(sets),125);assert all(len(s)==5 for s in sets)
intersections=[len(a&b) for a,b in combinations(sets,2)];eq('NW maximal intersection',max(intersections),2)
checks.append({'name':'NW pairwise intersections checked','cases':len(intersections),'status':'pass'})
def bitset(points):return sum(1<<(5*x+y) for x,y in points)
left=0;right=0
for j in range(5):left^=bitset({(x,j) for x in range(5)});right^=bitset({(x,(x+j)%5) for x in range(5)})
eq('NW five horizontal parity masks',left,(1<<25)-1);eq('NW five sloped parity masks',right,(1<<25)-1);eq('NW ten-output linear relation',left^right,0)
# Complete tiny seed enumeration, and acceptance-gap constants.
outs=[(a,b,a^b) for a,b in product([0,1],repeat=2)];eq('OR seed table',outs,[(0,0,0),(0,1,1),(1,0,1),(1,1,0)])
eq('OR acceptance under tiny generator',F(sum(any(z) for z in outs),4),F(3,4));eq('OR acceptance under uniform',F(7,8),F(7,8));eq('BPP yes margin',F(2,3)-F(1,12),F(7,12));eq('BPP no margin',F(1,3)+F(1,12),F(5,12))
print(json.dumps({'status':'pass','checks':len(checks),'results':checks,'scope':'Finite arithmetic, truth tables and structural identities only; no cryptographic assumption is certified.'},ensure_ascii=False,indent=2))