(50g) Fibonnaci Pseudoprime Test & Prime Test

[Albert Chan]

To show what is involved doing Fibonacci Primality Test.
Example: Prove N = 56789 is composite

N-1 = 56788 = 0b1101110111010100, build fib(N-1) mod N, in steps, using Doubling Formulas:

fib(2x)     = fib(x)*(2*fib(x+1) − fib(x))         = fib(x)*(2*fib(x-1) + fib(x))
fib(2x+1) = fib(x)^2 + fib(x+1)^2

Code:

Bits fib (mod N)
1    f1≡1                               f2≡1
1    f3≡1+1≡2                           f4≡1+2≡3
0    f6≡2*(2*3-2)≡8                     f7≡2^2+3^2≡13
1    f13≡8^2+13^2≡233                   f14≡13*(2*8+13)≡377
1    f27≡233^2+377^2≡26051              f28≡377*(2*233+377)≡33866
1    f55≡26051^2+33866^2≡21363          f56≡33866*(2*26051+33866)≡47414
0    f110≡21363*(2*47414-21363)≡11991   f111≡21363^2+47414^2≡2618
1    f221≡11991^2+2618^2≡33577          f222≡2618*(2*11991+2618)≡15486
1    f443≡33577^2+15486^2≡35950         f444≡15486*(2*33577+15486)≡22925
1    f887≡35950^2+22925^2≡28657         f888≡22925*(2*35950+22925)≡36994
0    f1774≡28657*(2*36994-28657)≡2092   f1775≡28657^2+36994^2≡52634
1    f3549≡2092^2+52634^2≡3880          f3550≡52634*(2*2092+52634)≡49872
0    f7098≡3880*(2*49872-3880)≡41159    f7099≡3880^2+49872^2≡33866
1    f14197≡41159^2+33866^2≡42723       f14198≡33866*(2*41159+33866)≡4690
0    f28394≡42723*(2*4690-42723)≡39076  f28395≡42723^2+4690^2≡18237
0    f56788≡39076*(2*18237-39076)≡33347 ≠ 0 -> n is composite

It seems Fibonacci Primality Test involved doubled the work, compared to SPRP-test