2
$\begingroup$

Background

An Euler pseudoprime $n$ to a coprime base $a$ is a composite, odd $n$ which satisfies $$a^{\frac{n-1}{2}} \equiv \pm 1\ (\text{mod } n).$$ Wikipedia link.

This is always the case for primes, so it is remarkable when composites slip through. I'll reproduce the argument here, from Fermat's Little Thm:

  1. (FLT) if $p=2q+1$ is prime, and coprime to $a$, then $a^{p-1} \equiv 1\ (\text{mod }p)$. Therefore,
  2. $a^{(2q+1) -1} \equiv 1\ (\text{mod }p)$
  3. $a^{2q} -1 \equiv 0\ (\text{mod }p)$. Factoring gives
  4. $(a^q+1)(a^q-1)\equiv 0\ (\text{mod }p)$. Conclusion:
  5. $a^{q} \equiv \pm 1\ (\text{mod } n)$

I spent some time working on/around with this, and happened to find a fast primality check, which fails 12 times under 100 million.

The Algorithm

The algorithm runs as follows, given odd $n$:

  1. For the first $\lfloor\text{log}_2(n)\rfloor$ primes $p$, determine if $$p^{\frac{n-1}{2}} \equiv \pm 1\ (\text{mod}\ n)$$
  2. If this holds for all such $p$, output PROBABLY PRIME.
  3. Else, output COMPOSITE

...and that's it.

Question

Why does this work so well? I threw out a lot in stripping it down, most noatably, the requirement that $(p,n)=1$. Somehow it fails less, and requires around $O(\text{log}^3 n)$ checks, rather than $O(\text{log}^6 n)$ (from the most recent unconditional AKS bound). Can I expect it to fail more or less often as I extend the range?

I am actively researching, and wanted to know if anyone has seen or heard of something similar or good references to read.

The failure cases ($n \lt 10^8$), for the curious, are
1. 3,828,001 = 101 *151 *251
2. 17,098,369 = 113 *337 *449
3. 17,236,801 = 151 *211 *541
4. 23,382,529 = 97 *193 *1249
5. 37,964,809 = 109 *379 *919
6. 56,052,361 = 211 *421 *631
7. 62,756,641 = 109 *241 *2389
8. 68,154,001 = 151 *601 *751
9. 79,411,201 = 193 *257 *1601
10. 84,350,561 = 107 *743 *1061
11. 90,698,401 = 103 *647 *1361
12. 92,625,121 = 181 *631 *811

$\endgroup$
2
  • 1
    $\begingroup$ "The standard for deterministic algorithms" is certainly not $\sqrt{n}$. See the AKS primality test. $\endgroup$ Sep 2, 2016 at 22:58
  • $\begingroup$ @RobertIsrael True, thanks. Updated to reflect the bound for AKS. $\endgroup$
    – ZMoltion
    Sep 2, 2016 at 23:55

3 Answers 3

5
$\begingroup$

One can go slightly further, as Euler did, and note that it isn't just $\pm 1$ but $(a|p)$ (the Jacobi symbol). Using this with various bases to make a probable prime test is the Solovay-Strassen test. As Peter points out, at most 1/2 of the bases can be liars for a composite, leading to the idea that using random bases we have a $2^{-k}$ probability of a composite passing $k$ tests. Using fixed bases (e.g. the first $k$ primes) allows adversaries to fool you every time unless you can show you use enough bases that it is not possible for any composite to pass (see Miller's test below).

This has been supplanted by the Miller-Rabin test, which takes essentially identical time and allows only 1/4 of the bases, so is in some sense twice as efficient. It is quite commonly used.

There are deterministic sets of bases that can be used if your input is limited in size, and some clever hashing methods to further reduce the number of bases required for a deterministic and correct answer for a given input.

Probably the most popular method for serious contemporary use is the BPSW test, which runs in $O(\log^2 n)$ time, has been shown to have no counterexamples under $2^{64}$, and no known larger counterexamples after 36 years of use and searching. We expect they exist, but are very rare (there are good reasons why). Some people are more pessimistic and add one or more M-R tests on top.

Note that your test is not $O(\log n)$, as modular exponentiation is at least $O(\log^2 n)$, so your algorithm is $O(\log^3 n)$. It is similar to Miller's test, which is $O(\log^4 n)$ because the lowest current limit on the number of bases needed is $2\log^2 n$. It has the advantage of a lot more rigorous math showing that the test is absolutely correct, if the generalized Riemann Hypothesis is correct. Proving the Riemann Hypothesis has been giving us a wee bit of bother for some time however. In practice it turns out that even if one assumes this, we have faster implementations for most input sizes we care about anyway.

AKS is of course important in that it shows deterministic bounds of $O(\log^6 n)$ for all inputs. But in practice it's very slow, and not used. Constants matter, as does not ignoring all the caveats. For instance, APR-CL has a complexity of $O(\log^{c\log\log\log n} n)$, which is not polynomial -- asymptotically AKS is better. But $\log\log\log n$ grows so slowly that we can just replace it with the constant 3 for any number we'd consider computing, and now it's obvious that it will be faster than AKS for every input we'd ever use. Which, it turns out, is just what the empirical data shows. That ECPP internally uses randomness doesn't hinder us and we see approximately $O(\log^4 n)$ in practice, even though we don't have rigorous proofs of this.

$\endgroup$
1
$\begingroup$

A composite number has a chance of $50$% to pass the given test for some random number $a$. So, if a number passes $20$ tests, the probability is very high that the number is prime.

Even better is the strong pseudoprime-test based on fermat's little theorem. It can be shown that at most $25$% of the bases coprime to the given number will let a composite number pass the test, so with enough tests, the primilaty can be virtually guaranteed. If the number fails such a strong-pseudoprime test, it must be composite.

$\endgroup$
0
$\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$
12
  • 1
    $\begingroup$ I'm not sure I follow your argument entirely, do you have a longer write up or a proof I could look over? $\endgroup$
    – ZMoltion
    Mar 22, 2018 at 16:23
  • $\begingroup$ I dont have any paper, this is the new discovery... i will try to write one if possible. But i have evidences why this is true i cant explain it here $\endgroup$ Mar 22, 2018 at 17:25
  • $\begingroup$ Also I welcome someone to prove this conjecture, that no composite will pass this test $\endgroup$ Mar 22, 2018 at 17:28
  • 1
    $\begingroup$ I mean, I'll test this idea when I go home to $10^8$, and further investigate. I agree that BPSW has a hard time differentiating between D's which are the most appropriate. My personal BPSW variant uses an Euler-Jacobi PP/strong Lucas PP test, which runs just a little faster in the ranges I use commonly. $\endgroup$
    – ZMoltion
    Mar 22, 2018 at 17:31
  • $\begingroup$ It seems wrong to propose this as deterministic and not yet have a proof. $\endgroup$
    – ZMoltion
    Mar 22, 2018 at 17:32

You must log in to answer this question.

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