Efficient Polynomial-Time Construction of Prime Numbers

Polynomial-Time Pseudodeterministic Construction of Primes Igor Carboni Oliveira Based on joint work with Lijie Chen, Zhenjian Lu, Hanlin Ren, and Rahul Santhanam

Primes An integer is a prime if it is only divisible by 1 and itself. ?-bit prime: [2n-1,2n - 1] , i.e., binary representation of the form 1xxxxxxx1 Two fundamental computational problems about primes: Primality Testing: check whether a given ?-bit integer is prime AKS primality test: solves this problem in deterministicpoly(?) time Prime Generation: find an ?-bit prime Focus of this talk

Challenge Generating prime numbers: Input: ? Output: A fixed?-bit prime pn. ( i.e., in [2? 1,2?-1] ) Can we solve this problem deterministically in time poly(?)?

A simple approach: Cramr Cram r s conjecture: Let ??denote the ?-th prime, then ??+1 ??= ? log?? Algorithm Cram r: For ? 2? 1to 2? 1 If ? is prime, Output ? and halt 2 Under Cram r s conjecture, this algorithm inspects ? ?2numbers, so it runs in poly ? time. Uses [AKS04] for checking primality! Although Algorithm Cram r is conjectured to run in poly ? time, the provable guarantee is only ? 20.525?time [BHP01] State-of-the-art: ??+1 ??= ? 0.525 ??

State of the art Best known algorithm is due to [LO87]. [LO87] employs techniques from analytic number theory to approx. count primes in an interval [a,b]. It has running time guarantee 2n/2+o(n). [2n-1 , 2n - 1] Approx. # primes in each interval in time 2n/2 Idea: 2n/2

Infinitely Often: Mersenne Infinitely-Often Algorithms Algorithm Mersenne: On infinitely many ?, the algorithm outputs a prime of length ?. Output string is a sequence of ? ones (already a non-trivial notion!) Under this conjecture, Mersenne is an infinitely-often polynomial-time algorithm for generating primes. Conjecture: There are infinitely many Mersenne primes (primes of the form 2? 1).

Generalization: Dense Properties A property ? 0,1 is dense, if for every input length ?, ? 0,1? 2?/poly ? PRIMES is dense: Prime Number Theorem: there are ~?/ln? primes in [1, ?] PRIMES 0,1? 2?/100? Explicit construction problem: For a dense property ?, find a length-? string in ? in poly ? time. Easy with randomness! Algorithm Random: Sample ? 0,1? until ? ? Output ? Deterministic algorithms are open

Complexity Theory and Pseudorandomness ?IW 0,1?: The generator from [IW97] Circuit Lower Bound Hypothesis: ? requires 2 ?-size Boolean circuits Algorithm IW: For ? in ?IW If ? is a prime Output ? and halt Assuming hypothesis, ?IWhits every dense property that is easy to decide In particular, ?IWcontains a prime! Algorithm IW is conjectured to find a prime, but we seem very far from proving this hypothesis State-of-the-art: ? requires 3.1? ? ? size circuits

Summary Almost-everywhere / infinitely often poly-time (under conjectures) Cramer, Mersenne Assuming ? requires exponential-size circuits, Algorithm IW runs in poly ? time. Algorithm IW State of the art Time Complexity ? 20.5? Can we find a prime in ???? ? time provably? Polymath 4: Attempted to use number-theoretic techniques but did not obtain an unconditional improvement.

Relaxing our goal: Pseudodeterminism Algorithm Random: Sample ? 0,1? until ? ? Output ? Drawback of Random: different primes on different executions Pseudodeterministic Randomized Deterministic Algorithm Algorithm Algorithm ?1 ?2 ?3 ?2 ?4 ?1 ?1 ?2 ?1 ?1 ?

A randomized algorithm is pseudodeterministic if on most of its computational branches it outputs the same answer. Any bounded observer thinks the algorithm is deterministic. Pseudodeterministic Randomized Deterministic Algorithm Algorithm Algorithm ?1 ?2 ?3 ?2 ?4 ?1 ?1 ?2 ?1 ?1 ?

Literature Pseudodeterminism was first defined and studied in: Eran Gat and Shafi Goldwasser [GG11]: Probabilistic search algorithms with unique answers and their cryptographic applications . Space complexity [GL19] Query complexity [GGR13], [GIPS21, CDM23] Proof systems [GGH18], [GGH19] Streaming algorithms [GGMW20], [BKKS23] Parallel computation [GG17], [GG21] Computational algebra [Gro15] Learning algorithms [OS18] Approximation algorithms [DPV18] Kolmogorov complexity [O19, LOS21] and more [BB18], [Gol19], [DPWV22], [WDP+22], [CPW23],

Gat-Goldwasser (2011): Is there an efficient pseudodeterministic algorithm for generating prime numbers? More generally, Is it the case that the generation problem for everydense and easy property Q can be solved pseudodeterministically in polynomial time?

Relevant previous work [OS17] There is a sub-exponential algorithm ? such that, for infinitely many? , there is a canonicalprime?? [2? 1,2?) such that ?(1?) outputs ?? with probability at least 1 2 ? over the randomness of ?(1?).

Poly-time pseudodeterministic constructions Theorem There is a polynomial-time algorithm ? such that, for infinitely many? , there is a canonical prime ?? [2? 1,2?) such that ?(1?) outputs ?? with probability at least 1 2 ? over the randomness of ?(1?). What properties of primes are used? Density: A 1/poly(?) fraction of ?-bit strings are prime numbers. Easiness: There is a poly ? -time deterministic algorithm that checks if a given integer is prime.

Theorem (Main Result) Let ? = {?? {0,1}?}? be a property such that: (Dense) There is a polynomial ? such that for all ? , ?? (Easy) There is a deterministic poly-time algorithm deciding ?. 1 ? ? 2?; Then, there is a polynomial-time algorithm ? such that, for infinitely many? , there is a canonical solution ?? ?? such that ?(1?) outputs ?? with probability at least 1 2 ? over the randomness of ?(1?). (Previous work [OS17] also works for all easy and dense properties)

Warm-up: Sub-exponential time construction [OS17] There is a pseudodeterministic algorithm that outputs an ?-bit prime in 2?? 1 time (infinitely often). Idea I: Uniform hardness vs randomness Idea II: Win-win argument 12 / 23

Uniform Hardness vs Randomness y = G(x) For any ? that breaks ?, ??????computes ? ????? ? ? ? = ??is a PRG ? x Trevisan-Vadhan 07 A language ???with special properties that is ??????-complete Corollary If ????doesn t fool ??????, then ???????????computes ???. Impagliazzo-Wigderson 01 (uniform) hardness vs randomness Impagliazzo-Wigderson 97 (non-uniform) hardness vs randomness If ? has special properties, given a distinguisher ? of ?, we can compute ? with a uniform reconstruction oracle algorithm ??????. Given a distinguisher? of ?, we can compute ? with a nonuniform reconstruction oracle algorithm ??????/??????.

Review of the previous approach [OS17] ? = ?? for a large constant ? CandidateHSG ??: 0,1?(?) 0,1? ??? AKS: 0,1? {0,1} accepting a 1/? fraction of inputs ??? on ?-bit inputs (space-? computation) ReconstructionAlgorithm ?AKS: 0,1? {0,1} ??does not hit AKS ?AKScomputes?? ??? ??

Review of the previous approach [OS17] Key Idea: win-win argument ??hits AKS? We have a hitting set generator! Case HIT: ??? ?? and find the first one accepted by AKS. In 2?(?) time, enumerate all outputs of ??? 2? ?= 2?1/?-time construction of a fixed ?-bit prime.

Review of the previous approach [OS17] Key Idea: win-win argument ??doesnothit AKS? We can now compute ??? very FAST! Case AVOID: ??? RAKS is a poly ? = poly ? time randomizedalgorithm for ?? ?? ???covers all space-? computations (naively it takes ?? time to compute) In ?(?) space, one can find the lexicographically first ?-bit prime poly(?)-time randomizedalgorithm that outputs the lexicographically first ?-bit prime w.h.p.

AVOID HIT Digest: ? = ?? ? ??: 0,1? {0,1}, build From a special language ?? ??: 0,1?(?) 0,1? attempting to hit ?-bit primes. If it HITS, we get a 2?(?)-time construction of an ?-bit prime! If it does not hit (AVOIDS), ?? that to get a poly(?) time construction of an ?-bit prime! ?? itself is in poly(?) time, and we use Idea: Polynomial time? HIT casestill makes non-trivial progress Iterate AVOID caseis FAST, but HIT caseis SLOW

The (ideal) Chen-Tell generator (2021) Mbits Uniform ?:{1?} 0,1? ? ? (Circuit of depth ? and width ?) ? ? log T Uniform circuit of depth ? and width ? that computes a function ?:{1?} 0,1? ? = ??is HSG ? Recon ? Chen-Tell: For any integer M such that log T < M < T: For any dense ? that avoids ?, Recon?1?computes ? 1?in randomized time poly ?,? HSG H: {0,1}log T {0,1}M computable in poly(T) time.

Pseudodeterministic constructions from [CT21] T= 2? ? Fix ? = poly ? ???: Brute Force Enumerates all strings of length ?, and outputs the first n-bit prime d= poly ? ? BF0 Reconstruction guarantee: If ????avoids ?BF0, then one can speed-up the computation of BF0in poly ?,? = poly ? time. log T = O(n) Plug in ? = BF0as the hard function Does ???? avoid ?BF0? Recon AKS? Compute the first length-? prime in randomized (i.e. pseudodet) poly ? time Hitting set ?BF0 that hits ???? and is computable in 2? ? time. Use ????as distinguisher

The iterated win-win argument 0,1?1 ? ??= ?? 1 ????0 ????0: 0,1?(log ?0) 0,1?1 ????2: 0,1?(log ?2) 0,1?3 ????1: 0,1?(log ?1) 0,1?2 Case HIT ???0: 1?0 0,1?0 outputs the smallest ?0-bit prime in ?0= 2?(?0) time Case HIT ????0 HITS AKS?? ???1: 1?1 0,1?1 outputs a fixed ?1-bit prime in ?1= poly(?0)time ???2: 1?2 0,1?2 outputs a fixed ?2-bit prime in ?2= poly(?1) time ????1 HITS AKS?? Case AVOID: ????0DOES NOT HIT AKS?? Case AVOID: ????2 DOES NOT HIT AKS?? Case AVOID: ????1DOES NOT HIT AKS?? poly(?0)-time construction of fixed ?0-bit prime! poly(?1)-time construction of fixed ?1-bit prime! poly(?2)-time construction of fixed ?2-bit prime!

A closer look at each iteration ?? ??= length of prime that we want to find ??= HSG containing an ??-bit prime ??= size of ?? ??? Enumerate all strings in ?? and output the first prime ?? ?0= 2? ?0 Next hitting set ??+1 is ?BF? Each iteration: ? for some ? that we set ? for some ? depending on Chen-Tell Compute the first prime in ?? in randomized (i.e. pseudodet) poly ??+1 time ?? ?? 1 ?? ?? 1 Does AKS??+1 avoid ?BF?? Hope: If we set ? large enough, ?? grows faster than ?? A smaller hitting set ??+1 ?BF? that hits AKS??+1 ?? ?? ?

Hope: If we set ? large enough, ?? will grow faster than ?? ! ?? vs ?? ?? ?? ? ?? ? ??= ?0 ??= ?? 1 ? ??= 2?0 ??, for some ?. ??= ?? 1 Want to find ? such that ?? = poly(??). We set ? = 2?. When ? = ? log?0, a simple computation shows that ?? will be comparable to ??.

The algorithm and its correctness Algorithm CLORS23: Let s say ? = ?? for some ? If ? = ? (recall that ?? poly ??) Find the first prime in ?? by brute force Else Use ReconAKS??+1 to output a candidate ??-bit prime If ??contains a prime We can find this prime using brute force in polynomial time! If ??doesn t contain a prime But ?0does There is some ? s.t. ?? contains a prime but ??+1= ?BF? does not. AKS??+1 avoids ?BF?, so ReconAKS??+1 computes BF? correctly!

Omitted Technical Details The HSG of [CT21]doesn t apply to alluniformcomputations: only to low-depth uniform circuits. Luckily, the algorithms ???? we constructed can be implemented by low-depth uniform circuits. The original [CT21] paper gives a HSG with ?(log2 ? log ?) seed length instead of ? log ? . This only gives a quasi-poly time construction instead of poly-time. We improve Chen-Tell by combining it with the Shaltiel-Umans PRG [SU05]. This requires extra work (the original SU reconstruction algorithm is not uniform).

Remarks Interesting fact: Canonical primes depend on the code/implementation of AKS. Corollary. Primes with succinct and efficient descriptions: For every integer m there is n> m and an n-bit prime p with rKpoly(p) = O(log log log n) Other win-win arguments in complexity theory stop at half-exponential bounds. The new iterative win-win paradigm has found another application:

Open Problems Main Challenge: Make the result work on all input lengths (or reduce gap)? [OS17] achieves zero-error (it outputs the canonical prime or ``FAILURE ). Can we get a zero-error polynomial-time infinitely-often algorithm? [OS17] works for every dense property in BPP. We require the property Q to be in P.

Thank you (Special thanks to Hanlin and Lijie for several slides)