Polynomial-time Pseudodeterministic Construction of Primes and Motivational Challenges
Exploring the challenges and advancements in generating prime numbers, particularly focusing on a pseudodeterministic construction method within polynomial time. The discussion includes reviewing previous approaches, fundamental computational problems related to primes, motivational problem statements, simple algorithms, attempts at improvements, and considerations for designing fast deterministic algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Polynomial-time Pseudodeterministic Construction of Primes Lijie Chen UC Berkeley Zhenjian Lu University of Oxford Igor C. Oliveira University of Warwick Rahul Santhanam University of Oxford Hanlin Ren University of Oxford
Todays Plan Our Result: Motivation Construction of Primes, and all easy and dense P-property Proof Overview Review of the previous approach A ``winlog ? approach
Todays Plan Our Result: Motivation Construction of Primes, and all easy and dense P-property Proof Overview Review of the previous approach A ``winlog ? approach
Primes An integer is a prime if it is only divisible by 1 and itself. Fundamental computational problems about primes: Primality Testing: check whether a given ?-bit integer is prime AKS primality test: solving this problem in deterministicpoly(?) time Prime Generation: find an ?-bit prime! Focus of this talk
Motivational Problem Generating prime numbers: Input: ? Output: A fixed?-bit prime pN. ( i.e., in [2? 1,2?) ) Can we solve this problem deterministically in time poly(?)?
A Simple Algorithm 1. Enumerate N-bit integers in sequence, testing each one for primality using the AKS Algorithm. 2. Strong number-theoretic conjectures (Cram r s conjecture) imply this algorithm halts in poly(N) time, but they seem beyond the power of current techniques. 3. Best provableguarantee on running time for this algorithm is 20.525 N, due to [BHP2001].
Attempts at Improvements Best known algorithm is due to [LO87]. It proceeds via approximate computation of the zeta function and has running time guarantee 2N/2+o(N). The Polymath 4 Project (2009) attempted to improve the state of the art but succeeded only in giving conditional improvements [TCH12].
A Relaxed Requirement Fast deterministic algorithms seem to be hard to design and analyse, but perhaps randomness could help us? An obvious randomized algorithm: Generate ?-bit integer ? at random. Test for primality, outputting ? if the test succeeds. (By the Prime Number Theorem, probability of success is (1/?).) Problem:This doesn t generate a fixedprime! Output depends on the randomness of the algorithm.
It is not so clear how to obtain a fast deterministic algorithm. On the other hand, randomized generation is easy, but does not produce a fixed prime number. Is there an intermediate notion that could perhaps be useful?
Deterministic, Randomized Fix a property Q, such as Primes. Given N (in unary), Find an element/string yN in Q such that |yN| = N. 1N 1N Computation paths of the Algorithm y4 yN = f(1N) y1 y2 y3 y1 Deterministic (output in Q) Randomized (w.h.p., output in Q)
Pseudodeterministic Pseudodeterministic Algorithm: A canonical solution is outputed with high probability. 1N 1N 1N f(1N) y2 f(1N) f(1N) f(1N) y4 yN = f(1N) y1 y2 y3 y1 Pseudodeterministic (w.h.p., fixed output in Q) Deterministic (output in Q) Randomized (w.h.p., output in Q)
Pseudodeterministic Algorithms By standard amplification, we can assume the canonical solution is outputed with probability at least 1 exp(-N). Viewed as a black-box, the output of the algorithm is deterministic to any computationally bounded observer.
Literature on pseudodeterminism Pseudodeterminism was first defined and studied in: Eran Gat and Shafi Goldwasser [GG11]: Probabilistic search algorithms with unique answers and their cryptographic applications . Further investigated in [GGR13], [GG15], [Gro15], [GGH17], [OS17]. Some of these works developed algorithms for specific problems such as finding a bipartite matching (in parallel), a non-zero of a polynomial, etc.
Questions Gat-Goldwasser (2011): Is there an efficient pseudodeterministic algorithm for generating prime numbers? More generally, Is it the case that the generation problem for every dense and easy propertyQ can be solved pseudodeterministically in polynomial time?
Previous work [OS 17] 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?). 15
Todays Plan Our Result: Motivation Construction of Primes, and all easy and dense P-property Proof Overview Review of the previous approach A ``winlog ? approach
Our Result: Pseudodeterministic Construction of infinitely many primes 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 by us? Dense: A 1/poly(?) fraction of ?-bit integers are primes Easy: There is a poly ? -time algorithm checking if a given integer is a prime
Our Result: Pseudodeterministic Construction of dense and easy properties Theorem Let ? = {?? {0,1}?}? be a property such that: (Dense) There is a polynomial ? such that for all ? , ?? (Easy) There is a 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?). [OS 17] also works for all easy and dense properties
Todays Plan Our Result: Motivation Construction of Primes, and all easy and dense P-property Proof Overview Review of the previous approach A ``winlog ? approach
Review of the previous approach [OS17] A win-win argument from Hardness vs. Randomness (Our presentation is somewhat different from the original paper) UniformHardness vs. Randomness via Reconstruction [IW 01], [TV 07], [CRTY 20] There is a language ??? such that PSPACE-completeness ??? is PSPACE-complete, meaning that any polynomial-space computation can be reduced to it in polynomial time.
Review of the previous approach [OS17] There is a PSPACE-complete language ??? such that Uniform Hardness vs. Randomness ??: 0,1? {0,1} be the restriction of ??? to ?-bit inputs. For any reasonable Let ?? parameter ? ?, there is a candidate hitting set generator??? and a poly(?)-time randomized oraclealgorithm?: 0,1? {0,1} such that ??: 0,1? 0,1? ?? is computable in 2?(?) time. ??? For any oracle ?: 0,1? {0,1} satisfying (1) ?accepts at least 1/? fraction of inputs and (2) ??? ??doesnot hit ? (i.e., ?rejects all outputs of ??? ??) We have that ??computes?? ??
Review of the previous approach [OS17] A candidateHSG ??: 0,1?(?) 0,1? ??? An oracle ?: 0,1? {0,1} accepting a 1/? fraction of inputs ??? on ?-bit inputs (space-? computation) A reconstructionalgorithm ??: 0,1? {0,1} ??does not hit ? ??computes?? ??? ??
Review of the previous approach [OS17] ? = ?? for a big constant ? A candidateHSG ??: 0,1?(?) 0,1? ??? AKS: 0,1? {0,1} checktheprimality in poly(?) time ??? on ?-bit inputs (space-? computation) A reconstructionalgorithm ?AKS: 0,1? {0,1} ??does not hit AKS ?AKScomputes?? ??? ??
Review of the previous approach [OS17] A win-win argument from Hardness vs. Randomness ?? hits AKS? We have a hitting set generator! ?? and find the first one accepted by AKS. 2? ?= 2?1/?-time construction of a fixed ?-bit prime. Case HIT: ??? In 2?(?) time, enumerate all outputs of ???
Review of the previous approach [OS17] A win-win argument from Hardness vs. Randomness ??doesnot hit AKS? We can now compute ??? very FAST! Case AVOID: ??? ???covers all space-? computation, naively it takes ?? time to compute RAKS is a poly ? = poly ? time randomizedalgorithm for ?? In ?(?) space, one can find the lexicographically first ?-bit prime ??. poly(?)-time randomizedalgorithm that outputs the lexicographically first ?-bit prime w.h.p.
Digest: How does it work? ??: 0,1? {0,1}, we build a From a powerful language ?? candidate HSG ??: 0,1?(?) 0,1?, attempting to hit ?-bit primes. If it hits, we have a 2?(?)-time construction of ?-bit prime! If it does nothit, ?? that to get a poly(?) time construction of ?-bit prime! ?? itself is in poly(?) time, and we use Why can t we get polynomial time? The second case is fine, but the first case is TOO SLOW Key idea: keep recursing on the first case!
Todays Plan Our Result: Motivation Construction of Primes, and all easy and dense P-property Proof Overview Review of the previous approach A ``winlog ? approach
Key technique tool: Chen-Tell Generator Uniform Hardness vs. RandomnessFORALL COMPUTATION* Previously, the hardness vs. randomness trade-off only works for somePSPACE-complete language ??? Uniform Hardness vs. Randomness (Informal, [CT 21]) Let ??: 1? 0,1? be ANY?-time uniform computation. For any reasonable parameter ? ?, there is a candidate hitting set generator???: 0,1?(log ?) 0,1? and a poly(?)-time randomized oraclealgorithm?:{1?} 0,1? such that ??? is computable in poly(?) time. For any oracle ?: 0,1? {0,1} satisfying (1) ?accepts at least 1/? fraction of inputs and (2) ???doesnot hit ? (i.e., ?rejects all outputs of ???) We have that ??1?= ?(1?) w.h.p.
Key technique tool: Chen-Tell Generator A candidateHSG ???: 0,1?(log ?) 0,1? ??: 1? 0,1? be ANY?-timeuniform computation An oracle ?: 0,1? {0,1} accepting a 1/? fraction of inputs A reconstructionalgorithm ??: 1? 0,1? ???does not hit ? ??1?= ?(1?)
Instantiate the New HSG: Case AVOID ? = ?? for a big constant ? A candidateHSG ????: 0,1?(?) 0,1? ???: 1? 0,1? outputs the smallest?-bit prime in ? = 2?(?) time AKS: 0,1? {0,1} checktheprimality in poly(?) time A reconstructionalgorithm ?AKS:{1?} 0,1? ????does not hit AKS ?AKS1?= ?(1?) Case AVOID: ????does not hit AKS? ?AKS1? outputs the smallest?-bit prime in randomized poly ? = poly(?) time.
Instantiate the New HSG: Case HIT ? = ?? for a big constant ? A candidateHSG ????: 0,1?(?) 0,1? ???: 1? 0,1? outputs the smallest?-bit prime in ? = 2?(?) time AKS: 0,1? {0,1} checktheprimality in poly(?) time A reconstructionalgorithm ?AKS:{1?} 0,1? ????does not hit AKS ?AKS1?= ?(1?) Case HIT: ????HITS AKS? By enumerating all outputs of ???? and check, we have a 2?(?)-time deterministic algorithm that outputs a fixed?-bit prime. (Not fast enough!)
Instantiate the New HSG: Case HIT ?1= ?0? for a big constant ? A candidateHSG ????0: 0,1?(?0) 0,1?1 ???0: 1?0 0,1?0 outputs the smallest ?0-bit prime in ? = 2?(?0) time AKS: 0,1?1 {0,1} checktheprimality in poly(?1) time A reconstructionalgorithm ?AKS:{1?0} 0,1?0 ????0does not hit AKS ?AKS1?0 = ?(1?0) Case HIT: ????0HITS AKS? By enumerating all outputs of ????0 and check, we have a 2?(?0)-time deterministic algorithm that outputs a fixed ?1-bit prime. (Not fast enough!)
Why do we stop here? ? for a big constant ? ?1= ?0 Case HIT: ????0 HITS AKS?? ???1: 1?1 0,1?1: enumerating all outputs of ????0 and output the first prime; a ?1= 2?(?0) time deterministic algorithm outputting a fixed?1-bit prime A candidateHSG ????0: 0,1?(?0) 0,1?1 ???0: 1?0 0,1?0 outputs the smallest ?0-bit prime in ?0= 2?(?0) time Case AVOID: ????0DOES NOT HITS AKS?? poly(?0)-time construction of fixed ?0-bit prime!
Why do we stop here? ?1= ?0 ? for a big constant ?; ?2= ?1 ? ???2: 1?2 0,1?2: enumerating all outputs of ????1 and output the first prime; a ?2= poly(?1) time deterministic algorithm outputting a fixed?2-bit prime Case HIT: ????1 HITS AKS?2 A candidateHSG ????1: 0,1?(log ?1) 0,1?2 ???1: 1?1 0,1?1: a ?1= 2?(?0) time deterministic algorithm outputting a fixed?1-bit prime Case AVOID: ????1 DOES NOT HITS AKS?2 poly(?1)-time construction of fixed ?1-bit prime!
A ?????? ? Argument ? ??= ?? 1 A candidateHSG ????0: 0,1?(log ?0) 0,1?1 A candidateHSG ????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 HITS AKS?? Case AVOID: ????2 DOES NOT HITS AKS?? Case AVOID: ????1DOES NOT HITS 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!
When do we stop? ? ??= ?? 1 pick ? large enough so that ?? grows faster than ??! ; A candidateHSG ?????: 0,1?(log ??) 0,1??+1 Case HIT ????: 1?? 0,1?? outputs a fixed ??-bit prime in ??= poly(?? 1) time ????+1: 1??+1 0,1??+1 outputs a fixed ??+1-bit prime in ??+1= poly(??) time ????? HITS AKS??+1 Case AVOID: ?????+1 DOES NOT HITS AKS??+2 Case AVOID: ????? DOES NOT HITS AKS??+1 poly(??)-time construction of fixed ??-bit prime! poly(??+1)-time construction of fixed ??+1-bit prime! For some ? = ?(log ?0), ????: 1?? 0,1?? runs in poly(??) time, and we stop there.
Summary Given a ?(?)-time algorithm ?? that constructs an ?-bit prime, we build a HSG ??? attempting to hit ?-bit primes, for ? = ??. If it hits, we have poly ? ? construction of ?-bit prime. (Now a better algorithm!) If it does not hit, we immediately get a poly(?)-time construction of ?-bit prime. (DONE) In the first case, we iteratethe same argument again on the new and better algorithm that constructs ?-bit prime. Until the running time becomes polynomial. At the end of the day, we have several input lengths ?0, ,??, and we know that on at least one of them we have poly-time pseudodeterministicconstruction of primes. = poly(?(?1/?))-time
Omitted Technical Details Unfortunately, the HSG of Chen-Tell does not apply to alluniformcomputation; but only low-depth uniform circuits. Luckily, all the algorithms ???? we constructed can be implemented by low-depth circuits. The original Chen-Tell paper gives you a HSG with ?(log2 ?) seed length instead of ?(log ?); Doing the math, this only gives a quasi-poly time construction of fixed prime instead of poly-time. We improve the original Chen-Tell by combining it with the Shaltiel-Umans generator. Need to work much harder, new ideas include a clever use of the construction of a cryptographic PRG from one-way permutation.
Problems and Future Directions Infinitely often deterministic generation of an n-bit prime in time 2o(n)? Make our result work on all input lengths? [OS 17] indeed achieved zero-error (the algorithm either outputs the canonical prime, or ``FAILURE ). Can our algorithm be made zero-error too? More applications of our techniques? WINlog ? Argument ImprovedChen-Tell generator
