|
(50g) Fibonnaci Pseudoprime Test & Prime Test +- HP Forums (http://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 11:47 AM 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: :: |