Infinite sets of primes with fast primality tests and quick generation of large primes

Abstract

Infinite sets <italic>P</italic> and <italic>Q</italic> of primes are described, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P subset-of upper Q"> <mml:semantics> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>⊂<!-- ⊂ --></mml:mo> <mml:mi>Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">P \subset Q</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For any natural number <italic>n</italic> it can be decided if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper P"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \in P</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in (deterministic) time <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis left-parenthesis log n right-parenthesis Superscript 9 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>9</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O({(\log n)^9})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is a main result of the paper. Also, for every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper Q"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \in Q</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, we show how to randomly produce a proof of the primality of <italic>n</italic>. The expected time is that needed for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 and one half"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> </mml:mrow> <mml:annotation encoding="application/x-tex">1\frac {1}{2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> exponentiations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mod n"> <mml:semantics> <mml:mrow> <mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\bmod n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also show how to randomly generate <italic>k</italic>-digit integers which will be in <italic>Q</italic> with probability proportional to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k Superscript negative 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{k^{ - 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Combined with the fast verification of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper Q"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \in Q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> just mentioned, this gives an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis k Superscript 4 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>4</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O({k^4})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> expected time algorithm to generate and certify primes in a given range and is probably the fastest method to generate large certified primes known to belong to an infinite subset. Finally, it is important that <italic>P</italic> and <italic>Q</italic> are relatively dense (at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c n Superscript 2 slash 3 slash log n"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">c{n^{2/3}}/\log n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> elements less than <italic>n</italic>). Elements of <italic>Q</italic> in a given range may be generated quickly, but it would be costly for an adversary to search <italic>Q</italic> in this range, a property that could be useful in cryptography.

Locations

• Mathematics of Computation - View - PDF