#!/usr/bin/env python3 """Exact indexed specifications and bounds for finite-algebra elimination. No large determinant or source polynomial is expanded. The source circuits are reused at their pinned versions. Run --source-checkout PATH to authenticate the existing files in a complete checkout. Standard library only. """ from __future__ import annotations import argparse, hashlib, json, math from pathlib import Path HERE = Path(__file__).resolve().parent def ell(n: int) -> int: if n < 1: raise ValueError('positive integer required') return (n-1).bit_length() def sha256(path: Path) -> str: return hashlib.sha256(path.read_bytes()).hexdigest() def authenticate(c: dict, root: Path) -> None: spec = root/c['source_specification'] if sha256(spec) != c['source_specification_sha256']: raise ValueError(f"changed source specification: {spec}") raw=(root/c['source_certificate']).read_bytes() git_sha=hashlib.sha1(b'blob '+str(len(raw)).encode()+b'\0'+raw).hexdigest() if git_sha != c['source_certificate_git_blob_sha']: raise ValueError('changed source certificate') src=json.loads(raw) fields={'generator_weights':'generator_weights', 'generator_log_norms':'generator_operator_log2_norm_bounds', 'guard_weight':'guard_weight','guard_log_norm':'guard_operator_log2_norm_bound', 'point_guard_weight':'point_guard_weight', 'point_guard_log_norm':'point_guard_operator_log2_norm_bound'} for key, old in fields.items(): if c[key] != src[old]: raise ValueError(f'input mismatch: {key}') s=json.loads(spec.read_text()) if len(s['monic_relations']) != c['p']+c['s']: raise ValueError('wrong generator count') if s.get('closed_equations') or s.get('indexed_guard_polynomials'): raise ValueError('the theorem requires no further residual equations') def bounds(c: dict) -> dict: p,s=c['p'],c['s']; ds=c['point_degrees'] if len(ds)!=p or min(ds)<2 or s<1: raise ValueError('invalid degrees') b=math.prod(ds); n=b*(1< None: ap=argparse.ArgumentParser();ap.add_argument('--source-checkout',type=Path);args=ap.parse_args() inputs=json.loads((HERE/'inputs.json').read_text()); reports=[] for c in inputs: if args.source_checkout: authenticate(c,args.source_checkout) result=bounds(c);reports.append(result) folder=HERE/c['name'];folder.mkdir(exist_ok=True) spec=dict(format='integer-polynomial-indexed-finite-algebra/triangular-v24', source_commit=c['source_commit'],source_specification=c['source_specification'], source_specification_sha256=c['source_specification_sha256'], total_variables=c['total_variables'],multiply_by_input=c['multiply_by_input'], fixed_parameter=c['fixed_parameter'], construction=RECIPE,bounds=result) (folder/'polynomial-specification.json').write_text(json.dumps(spec,indent=2)+'\n') (folder/'construction-certificate.json').write_text(json.dumps(result,indent=2)+'\n') report=dict(schema='triangular-elimination-bounds/v24',inputs_sha256=sha256(HERE/'inputs.json'), complete_checkout_sources_authenticated=bool(args.source_checkout),constructions=reports) (HERE/'bounds.json').write_text(json.dumps(report,indent=2)+'\n') for r in reports: print(r['name'],r['degree_bound'],'<2^'+str(r['degree_strict_power_of_two']), 'support <2^'+str(r['support_strict_power_of_two']), 'log2 l1 <=',r['coefficient_l1_log2_bound'], 'height <2^(2^'+str(r['coefficient_height_double_power_exponent'])+')') if __name__=='__main__': main()