Combining strong pseudoprime test to base 2 and an Elliptic Curve test

primality-test

I read Kubra Nari, Enver Ozdemir and Neslihan Aysen Ozkirisci: Strong pseudoprimes to base 2, in The Ramanujan Journal, 2022-04-26 (paywalled¹). Compared to a free earlier version at arXiv, the text is improved², and there are some algorithmic changes³.

The proposed tests are the classical strong pseudoprime test to base 2 followed by either one of two variants of an Elliptic Curve primality test. They conjecture the tests are true prime tests, and claim having "checked all integers less than $10^{22}$" against the simplest variant (that was $10^{21}$ in the arXiv v1 version).

Q1: Does their Elliptic Curve primality test bear any relation to the Lucas Pseudoprime test, which could explain it's claimed effectiveness? Recall that it remains unknown if A217120 intersects A001262.

Q2: How is the claimed check to $10^{22}$ feasible? Except if I miss some shortcut, that requires enumerating the strong pseudoprimes to base 2 A001262 up to $10^{22}>2^{73}$, and AFAIK the largest effort in that direction stopped at $2^{64}$ (Jan Feitsma: Pseudoprimes, 2013-03; compiled by William Galway, Tables of pseudoprimes and related data, 2013-04).

Q3: Anyone understands how exactly at step 4 of the Primality Test Algorithm (correspondingly step 12 of Algorithm 2) we are supposed to choose $P$? If that's as $P=\big(\ell^2,\ell(\ell^2-a)\big)$ [fixing the formula given] with $\ell\not\equiv a\pmod n$, how do we choose $\ell$ (and as an aside change it should it turns out to be unsuitable)?

Q4: In the proof of theorem 3.2 (2.2 in arXiv v1), I fail to see why $b(n−1)P=\infty \mod q$ regardless of the choice of $P$. Any clue?

¹ But there's a subscription plan with free introductory offer. This is not to be construed as a recommendation for anything.

² The abstract and text now mention that the paper is about a probabilistic primality test. The text justifies that by the iterative nature of the choice of $a$ given the state of the art (I only see this as making the analysis of the run time heuristic).

³ I have spotted these algorithmic differences in the journal version:

  • In the Primality Test Algorithm (section 2.1 arXiv v1):
    • At step 2, the search for $a$ starts at $a=3$ and is for $\left(\frac a n\right)=-1$.
    • Step 4 now is:

      Find a point $P\mod n$ such that $2bP$ is not the identity mod $n$, where $b$ is the least common multiple of the numbers from $1$ to $20$. Note that for any $\ell\in\mathbb Z_n$, $((\ell^2,\ell(\ell-a))$ is a point on $E\mod n$.

    • At step 5, parameter $b$ is as in step 4 [that is $232792560$ I believe].
  • In the simplified algorithm 2 (which looks like the Primality Test Algorithm except with $b=1$)
    • Step 2 reads: $a=3$
    • Step 5 reads: $\ \text{if}\ \left(\frac a n\right)=-1\ \text{then}$

Best Answer

The second author kindly and promptly answered my email, and a subsequent one. This clarifies:

  • Q2: The test used a pre-existing list of strong pseudo primes less than $10^{22}$.

  • Q3: $\ell$ is selected at random, and the point $P$ computed from that with $\ell^2$ the $x$ coordinate.

    This potentially makes the algorithm probabilistic in the nature of the result it produces.

  • Q4: I had missed a condition part of the theorem statement, and it's impact on the proof.

In further analysis of the paper, I spotted these (correctable) issues

  • Algorithm 1 is incorrect. The law it implements is not associative. Try it with $n=13$, $a=5$, and $(2\boxplus3)\boxplus7$, which is different from $2\boxplus(3\boxplus7)$. If Algorithm 1 is used in Algorithm 2, that sometime causes some primes to be misidentified as composite.
  • For input $n=1194649=1093^2$ and $n=12327121=3511^2$, perhaps others, the test hangs in a hopeless search for $a$ with $\left(\frac a n\right)=-1$. That occurs for any $n$ a square strong pseudoprime to base $2$, including the square of either of the two known Wieferich primes A001220. That "sequence is believed to be infinite" according to OEIS.
  • In Primality test algorithm step 4, we must read $P=\big(\ell^2,\ell(\ell^2-a)\big)$ where there is $P=\big(\ell^2,\ell(\ell-a)\big)$. This follows from the correct $\big(b^2,b(b^2-a)\big)$ earlier on.
Related Question