(50g) Fibonnaci Pseudoprime Test & Prime Test
02-17-2019, 05:47 PM (This post was last modified: 02-18-2019 06:13 AM by Gerald H.)
Post: #1
 Gerald H Senior Member Posts: 1,457 Joined: May 2014
(50g) Fibonnaci Pseudoprime Test & Prime Test
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   ; ;
02-17-2019, 09:12 PM (This post was last modified: 02-18-2019 09:39 PM by Albert Chan.)
Post: #2
 Albert Chan Senior Member Posts: 1,357 Joined: Jul 2018
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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
02-18-2019, 03:01 AM (This post was last modified: 03-06-2019 08:58 PM by Albert Chan.)
Post: #3
 Albert Chan Senior Member Posts: 1,357 Joined: Jul 2018
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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
02-18-2019, 06:18 AM
Post: #4
 Gerald H Senior Member Posts: 1,457 Joined: May 2014
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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?
02-26-2019, 07:55 AM
Post: #5
 Gerald H Senior Member Posts: 1,457 Joined: May 2014
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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.
02-26-2019, 02:03 PM
Post: #6
 Albert Chan Senior Member Posts: 1,357 Joined: Jul 2018
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
(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
02-26-2019, 04:29 PM
Post: #7
 Gerald H Senior Member Posts: 1,457 Joined: May 2014
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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.
02-26-2019, 06:18 PM (This post was last modified: 02-26-2019 06:49 PM by Albert Chan.)
Post: #8
 Albert Chan Senior Member Posts: 1,357 Joined: Jul 2018
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
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).
02-26-2019, 06:30 PM
Post: #9
 Gerald H Senior Member Posts: 1,457 Joined: May 2014
RE: (50g) Fibonnaci Pseudoprime Test & Prime Test
OEIS

https://oeis.org/A013998

says 658th.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)