(50g) Fibonnaci Pseudoprime Test & Prime Test

[Gerald H]

Edited as per next posting 2019-02-18.

Designating the members of Fibonnaci sequence

0,1,1,2,3,5......

as

f(0), f(1), f(2), f(3), f(4), f(5).......

and setting for integer N

g(N) := 1 if N = +/-1 mod 5
g(N) := -1 if N = +/-2 mod 5
g(N) := 0 if N = 0 mod 5

then if integer N is prime

f(N - g(N)) = 0 mod N.

The programme below runs the above test speedily.

Caveat: Some composite numbers, Fibonnaci pseudoprimes, pass the test, the programme erroneously returning 1, indicating primality, rather than 0.

However no number of the form

N = +/-2 mod 5

which passes the above test & is a base 2 pseudoprime has been shown to be composite (as of 2019-02-17, ref Crandall & Pomerance, Prime Numbers).



Size: 320.

CkSum: # ECD0h

Code:

::
  CK1&Dispatch
  # FF
  ::
    ::
      FPTR2 ^ZABS
      FPTR2 ^DupZIsTwo?
      casedrptru
      FPTR2 ^DupZIsEven?
      casedrpfls
      DUP
      ZINT 5
      Z=
      casedrptru
      DUP
      ZINT 5
      FPTR2 ^QMod
      FPTR2 ^ZABS
      FPTR2 ^DupQIsZero?
      case2drpfls
      FPTR2 ^ZIsOne?
      ITE
      ZINT -1
      ZINT 1
      OVER
      FPTR2 ^QAdd
      SWAP
      ::
        SWAPDUP
        ZINT 2
        Z<
        case
        SWAPDROP
        FPTR2 ^Z>ZH
        ZINT -2
        ZINT 0
        ZINT 1
        4PICK
        FPTR2 ^ZBits
        SWAPDROP#1-_
        ZERO_DO
        FPTR2 ^ZSQ_
        5PICK
        FPTR2 ^ZMod
        SWAP
        FPTR2 ^ZSQ_
        5PICK
        FPTR2 ^ZMod
        2DUP
        FPTR2 ^RSUBext
        DUP
        FPTR2 ^RADDext
        3PICK
        FPTR2 ^RADDext
        3UNROLL
        FPTR2 ^RADDext
        SWAPROT
        FPTR2 ^RADDext
        3PICK
        ISTOP-INDEX
        #1-
        FPTR2 ^ZBit?
        SWAPDROP
        ITE
        ::
          DUPUNROT
          FPTR2 ^QAdd
          ZINT -2
        ;
        ZINT 2
        3UNROLL
        LOOP
        4UNROLL3DROP
        SWAP
        FPTR2 ^Mod
      ;
      FPTR2 ^QIsZero?
    ;
    COERCEFLAG
  ;
;

[Albert Chan]

Using Mathematica, this shows first few Fibonacci pseudoprimes, below 1000:

f[n_] := Fibonacci[n - Part[{0, 1, -1, -1, 1}, Mod[n,5]+1]];
fprimeQ[n_] := (Mod[f[n], n] == 0);

Select[Table[i, {i,1000}], fprimeQ[#] != PrimeQ[#]&]

→ {1, 25, 60, 120, 125, 180, 240, 300, 323, 360, 377, 480, 540, 600, 625, 660, 720, 840, 900, 960}

Edit: tried above code to strong pseduoprimes, base-2: https://oeis.org/A001262
→ smallest number that is both strong base-2 and Fibonacci pseduoprime is 252601

[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

[Gerald H]

Thank you, Albert, for spotting the "typo".

Fibonnaci pseudoprime test more expensive than SPSP test.

You are clearly interested in questions such as primality - Do you have any number theory programmes for 50g not yet published?

[Gerald H]

As to the strength of this test, the 658th Perrin pseudoprime is

102307272286413

giving a probability of randomly coming across one of

1 in 155,482,176,727

which is good enough for most purposes.

[Albert Chan]

(02-26-2019 07:55 AM)Gerald H Wrote:  As to the strength of this test, the 658th Perrin pseudoprime is

102307272286413

giving a probability of randomly coming across one of

1 in 155,482,176,727

which is good enough for most purposes.

From Perrin pseudoprimes upto 10^16 with factorization list, above number should be 10 230 727 286 413

Fibonacci Primality testing is deterministic, what is the meaning of probability here ?

If "this test" refer to PRP test, chance of non-witness is 1 in 7, very bad.
If "this test" refer to SPRP test, chance of non-witness is 1 in 14, still bad.

This is much worse than my recent find: 999 999 512 881

[Gerald H]

Sorry for the lack of clarity.

To be clearer: If you test a randomly chosen integer up to 102307272286413 using the Perrin primality test the probability of an error is 1 in 155,482,176,727.

[Albert Chan]

Hi, Gerald H

Thanks for the clarity. However, probability calculations a bit off.

N = 10 230 727 286 413, were the 658th Perrin pseudoprimes.

Probability of Perrin pseduoprimes (for values upto N) ~ 658 / N ~ 1 in 15.548 billion

Corrected: N should be 658th Perrin pseudoprimes (not 534).

[Gerald H]

OEIS

https://oeis.org/A013998

says 658th.