Heuristic primality test with an offer $620 for a counterexample

Question

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)$?

Answer 1

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}$$

Answer 2

$$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.

Answer 3

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.