# Heuristic primality test with an offer $620 for a counterexample There is a heuristic primality test which combine the Fermat test and the Fibonacci test (with an offer$620 for a counterexample):

$$(1)\quad 2^{p−1} \equiv 1 \pmod p$$
$$(2)\quad f_{p+1} \equiv 0 \pmod p$$, where $$f_n$$ is the $$n$$-th Fibonacci number.

If $$(1)\;\&\;(2)$$ are true for a number of the form $$p \equiv \pm2 \pmod 5$$ then $$p$$ is supposed to be prime. Due to Wikipedia the test is very efficient, but how to implement $$(2)$$ efficiently for very big numbers?

Also due to Wikipedia there is a method suitable for recursive calculation of $$f_n$$:

$$(3)\quad f_{2n-1}=f_n^2+f_{n-1}^2$$
$$(4)\quad f_{2n}=f_n\cdot(f_n+2f_{n-1})$$

This could be reformulated to calculate $$f_n \pmod m$$ but is very slow for big numbers.

My question:

Is there an efficient way to implement $$(2)$$?

Why, sure. Calculation of $$f_n$$ is not much more complicated than calculation of $$2^n$$, and can be done by multiplication of $$2\times2$$ matrices: $$\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^n\cdot\begin{pmatrix}1\\ 1\end{pmatrix} = \begin{pmatrix}f_{n+1}\\ f_n\end{pmatrix}$$

• Is it fast for $n\approx 10^{100}$ or greater?
– Lehs
Commented Nov 26, 2019 at 15:41
• Is $2^n\pmod p$ fast for these $n$? I believe it is. Same thing here. Commented Nov 26, 2019 at 15:43
• @Lehs This imatrix method s very well-known and mentioned here many times in the past, e.g. nine years ago here, where I remark the same method works for any such recurrence. Commented Nov 26, 2019 at 15:49
• Points to be mentioned are (1) you're not computing $f_n$, you're computing $f_n \mod p$, so huge numbers will not arise, and (2) you're computing powers by repeated squaring, so the complexity is $O(\log n)$. Commented Nov 26, 2019 at 16:17
• Other things to mention is you can reformulate (3) and (4) above into $$f_{4n}=(f_n\cdot(f_n+2f_{n-1}))\cdot((f_n\cdot(f_n+2f_{n-1}))+2(f_n^2+f_{n-1}^2))$$ etc to jump by leaps and bounds.
– user645636
Commented Nov 26, 2019 at 18:55

$$f_{4n}=3\cdot f_n^4 + 8\cdot f_{n-1}\cdot f_n^3 + 6\cdot f_{n-1}^2\cdot f_n^2 + 4\cdot f_{n-1}^3\cdot f_n$$ $$f_{4n-1}=2\cdot f_n^4+4f_{n-1}f_n^3+6f_{n-1}^2f_n^2+f_{n-1}^4$$ If I didn't mess up the expansions (double checked now). You can do this 8 more times, substituting in the formula for the last one you expanded and get to use $$f_n$$ and $$f_{n-1}$$ to calculate: $$f_{\tiny{13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096n}}$$ so $$10^{100}$$ is no problem as that multiplier alone has 155 digits. You might want to generalize the formula for $$f_{y^2 n}$$ a bit more to figure out the rest of the difference. but to be fair you asked for values above $$10^{100}$$ I hope that this at least answers that question from the previous answers comments.

The Heuristic (I think) is likely false and it is rather simple to see.

Let $$n = p_1*p_2*...*p_k$$ with $$k ≥ 5$$ odd and assume that for all primes $$p | n$$:

I. $$p^2=4 \pmod 5$$

II. $$p-1 | n-1$$

III. $$p+1 | n+1$$

Then $$n$$ is a counterexample to this Heuristic.

Proof:

If condition I is met, then $$n=±2 \pmod 5$$. If condition II holds, then $$n$$ is a Carmichael number (it follows from Korselt's criterion), and then $$2^{n-1}\equiv 1 \pmod n$$. If the last condition III holds, then for all primes $$p|n$$, $$p=±2 \pmod 5$$ so that $$f_{p+1} \equiv 0 \pmod p$$ and Korselt's criterion can also be generalized here, so that $$f_{n+1} \equiv 0 \pmod n$$.

Edit/Note: Such a counterexample with these particular properties must have at least 5 prime factors (previously, was assumed 3). See here.

• In order for $n$ to be Carmichael, each prime factor $p_i$ must be unique too. Just thought Id point that out since you didnt mention it. Not sure if/how it impacts your argument. Commented Nov 30, 2021 at 16:48
• I dont fully follow the logic here. Why do you need all $p=\pm 2 (\mod 5)$? Wouldnt one suffice? Commented Nov 30, 2021 at 16:52
• One would suffice (by Fermat's Little Theorem). This decreases the chance of finding a counterexample though. There are only two possibilities with using only one congruence, whereas there are 6 different possibilities if both congruences are simultaneously included. Commented Nov 30, 2021 at 19:58