3
$\begingroup$

I'm studying a paper by the authors of the Baillie-PSW primality checker here, but am baffled by a detail of its Lucas primality test.

A BPSW implementation typically:

  1. Sorts out $n \le 3$, even $n$, then $n$ divisible by small factors.
  2. Subjects $n$ to a strong base-2 Fermat primality test.
  3. Check for squareness of $n$.
  4. Subjects $n$ to a strong Lucas primality test with a particular protocol for selection of its $P$, $D$ and $Q$ parameters.
  5. If the preliminaries, the strong Fermat test, check for squareness and the strong Lucas test all fail to prove $n$ composite, then $n$ is assumed prime.

The Lucas primality test for $n$ requires three auxiliary integer parameters, $P$, $D$ and $Q$, related by the equation $D = P^2 - 4Q \ne 0$. The BPSW authors insist on certain additional properties: In particular, that a value of $D$ is required such that the Jacobi symbol $\left( \frac{D}{n} \right)$ is -1 (if it's 0 then lucky you! You've found a factor!). They point out clearly that if $n$ or $D$ is square, then the Jacobi symbol will be $\ge 0$ (by the rules of the symbol).

The authors offer several strategies for selection of $P,D,Q$. The most popular is due to John Selfridge:

  1. Select the first $D \in \{ 5, -7, 9, -11, 13, -15, \ldots \}$ s.t. $\left( \frac{D}{n} \right) = -1$ (or 0) holds.
  2. $P=1$
  3. $Q = (P^2 - D)/4 = (1-D)/4$

The authors also point out that if $Q \ne \pm 1$ on top of $\left( \frac{D}{n} \right) = -1$, then the primality test can be strengthened even further at very low additional cost.

Finally, the authors also prove that the search for a $D$ satisfying the Jacobi-symbol requirement usually terminates within 2-3 evaluations.

And now we get to my question. As described, Selfridge's strategy starts off with $D=5$. If this is accepted, then $Q=(1-5)/4=-4/4=-1$, losing primality-checking strength. Next up is $D=7$, which is OK, but if that doesn't work then we're at $D=9$, which is square (and thus, unusable (?)). And soon enough you might encounter $D=25$, which is also square.

Why does the most-commonly-used BPSW Lucas parameter-selection strategy start with such a poor set of values? What makes this strategy preferable?

For that matter, all strategies examined by the author ask for the first $D$ in some series to satisfy $\left( \frac{D}{n} \right) = -1$, and yet the authors seem to gloss over the possibility of random search, or a search started at a high(er) value of $D$, where

  1. $Q$ would be guaranteed $\ne \pm 1$
  2. Square $D$ are much less dense.

especially in light of their proof that only 2-3 values of $D$ need to be checked on average before a suitable one is found.

You could even design a strategy that is guaranteed to avoid square $D$'s. In much the same way that incrementing $1$ by successive odd integers $3, 5, 7, \ldots$ generates all squares ($1^2+3=2^2$, $2^2+5=3^2$, $3^2+7=4^2 \ldots$), incrementing $2$ by those same successive odd integers produces numbers that cannot be square ($5, 10, 17, 26, 37, 50, \ldots$). Taking every second non-square so produced would satisfy the requirement that 4 divides evenly $(1-D)$: 5, 17, 37...

Why is that? Does the BPSW algorithm rely on the first, or low, values of $D$?

My research has led me to only this page by Thomas R. Nicely, who writes only a single off-hand sentence on the topic:

Additional conditions sometimes imposed (Riesel, 1994, p. 130), that N not divide Q and that D be square-free, were found to be irrelevant to this application of Lucas sequences.

which doesn't really tell me much.

$\endgroup$
1
  • 1
    $\begingroup$ A couple comments. The testing for small factors is purely something practical for any implementation and isn't part of BPSW itself. For D values, skipping 9 and 25 is easy enough, or just let the Jacobi computation find it. Note that ~85% of arbitrary inputs will select D=5 or -7, so it really isn't a big deal. Also note oeis.org/A217719 (extra strong test) where Baillie (many years later) just uses Q=1, P=3,4,5,6,7,... until (D|n)=-1. Pari/GP's test uses Q=1,P=3,5,7,... until (D|n)=-1. Re the ES test, note Nicely's comments are in error. $\endgroup$
    – DanaJ
    Oct 3, 2016 at 17:10

2 Answers 2

3
$\begingroup$

First, computing Jacobi (D/n) is roughly equivalent to GCD(n, something). Compared to the rest of the primality test, this is a tiny amount of calculation.

Second, the last section of the Lucas Pseudoprime paper shows that you usually don't need to try very many D's before finding one with (D/n) = -1.

Third, I have found that exactly how you get P, Q doesn't matter much in the sense that the number of Lucas pseudoprimes up to x is roughly the same. As the person writing the above question noted, it is a good idea to make sure abs(Q) > 1. Method A* in the Lucas Pseudoprimes paper does this.

I would say the strategy is convenient, but not necessarily "preferable" to other methods. Except that, after all these years of using method A or A*, no one has found a counterexample. If you choose another method for finding P and Q, you run the risk that one of the resulting Lucas pseudoprimes would be a strong pseudoprime base 2.

A suggestion for strengthening the test: I would also suggest checking, at the end of the calculation, that V_{n+1} = 2Q (mod n). I'm currently using method A* and looking for composite solutions. So far, n = 913 is the only odd composite n up to 60 billion that satisfies this congruence. Once V_{n+1} has been calculated (mod n), this additional check is virtually free.

$\endgroup$
2
  • 2
    $\begingroup$ Holy smokes, are you the Robert Baillie himself? $\endgroup$ Jul 19, 2017 at 17:34
  • $\begingroup$ I just across this thread again. There are now more data: We found only FIVE odd composites under 10^15 for which V_{n+1} = 2Q (mod n). See arxiv.org/abs/2006.14425 $\endgroup$ Jun 27, 2021 at 19:24
2
$\begingroup$

Here Is The Deterministic Lucas Primality Test, Only One Test Needed To Rule Out Any Composite Number, NO Need For Checking Strong Pseudoprimes Base Two, Good Luck

here i will present to you best way of choosing $P, Q$ and $D$ parameters for Lucas primality test. this selection is always correct and no composite number will pass this test. here is my overview of $BPSW$ test.

Weakness of BPSW Test

  • it is not dynamic, for any number $n$ always selection of $D$ start with $5$. At the end we use the same $D$ to test primality of many $n$
  • second order is controlled by previous two terms, so for checking the primality of a number we should device a way that check all two terms at a point that we use to test the primality of number $n$.
  • combined tests, lucas and spsp2 test

New Way Of Selecting $P, Q$ and $D$

Let $n$ be a number that we are testing for primality, calculate $y = floor(\sqrt{n})$. Then check if $n$ is perfect square. Let $D = P^2 + 4Q$, use small $P$, $\{1, 2, ..., 9\}$ prefer primes. then calculate $D$ by varying $Q$, $Q> y - 1$, calculate Jacobi symbol $(D/n)$, $(D/n)= - 1$. then you are done. set your $P, Q$ and $D$. Use Jacobi symbol to avoid factorization of big numbers

Testing

we dont need to repeat the mistakes, compute $U_n$ and $U_{n+ 1}$. if $n$ is prime, $\{U_n, U_{n+1}\} = \{n - 1, 0\}$ the number of $Q$ that you will need to test depends on the Value of $P$. is $P$ is $!$ maximum $47$ $Q$s, does not depend on $n$. Many composite numbers satisfy only one test of these two, and many of them the divisibility test.

$\endgroup$
1
  • $\begingroup$ It's still probabilistic. If you have a proof it's deterministic I'd love to see it. $\endgroup$ Feb 20, 2020 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .