 (50g) Fibonnaci Pseudoprime Test & Prime Test - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (50g) Fibonnaci Pseudoprime Test & Prime Test (/thread-12451.html) (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-17-2019 05:47 PM 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   ; ;``` RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-17-2019 09:12 PM 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 RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-18-2019 03:01 AM 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 RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-18-2019 06:18 AM 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? RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019 07:55 AM 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. RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-26-2019 02:03 PM (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 RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019 04:29 PM 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. RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Albert Chan - 02-26-2019 06:18 PM 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). RE: (50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-26-2019 06:30 PM OEIS https://oeis.org/A013998 says 658th.