(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: :: 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) 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 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. |