20070418, 17:20  #1 
∂^{2}ω=0
Sep 2002
República de California
2^{4}×733 Posts 
"New primality proving test from Alex Petrov"
Just got the following email: I uploaded the 2 inline images to my ftp stash, but for some reason the GIFs won't display in my Firefox browser  the formulae in the GIFs are much less confusing when rendered into Fibonaccisequence terms as I do below anyway, but in case you're interested, you can always save the image files locally (Rightclick/"Save link as" in Firefox), and use an application of your choice (e.g. Windoze picture and fax viewer on WinPC) to view the originals.
I must say, I've been called many things, but "the known specialist in the theory of numbers..."  I suspect that's just a mangled translation from the Russian for "one of the usual suspects who spend too much time loitering at mersenneforum.org, slouched against a wall with a cigarette dangling perilously from their lips, trying to look all tough and grownup." On another point of verbiage, I believe by "n numbers" he means "positive integers." ================ From: "Alexey Petrov" <alexeypetrovjob@yandex.ru> To: <ewmayer@aol.com> Subject: New primality proving test from Alex Petrov Date: Wed, 18 Apr 2007 19:36:16 +0800 Good day, dear Mr. Ernst W. Mayer! Excuse me for bad English, i’m Russian. I write You, because You are the known specialist in the theory of numbers. Recently I invented new (as it seems to me) primality proving test All n numbers, ending in 1 or 9, are primes, if a condition is executed: http://hogranch.com/mayer/images/random/petrov_1.gif All n numbers , ending in 3 or 7, are primes, if a condition is executed: http://hogranch.com/mayer/images/random/petrov_n1.gif Among numbers, not exceedings 50000, only 11 composites, which this test determines as primes: 4181=37*113 5777=53*109 6479=11*19*31 6721=11*13*47 10877=73*149 13201=43*307 15251=101*151 27071=11*23*107 34561=17*19*107 44099=11*19*211 47519=19*41*61 Did you know this method? Best regards, Alexey Petrov =============== My take on this: The author seems wellmeaning, he appears to just have come up with some kind of pseudoprime test. The only real question is whether it's a known one in disguise, or a new one. The fact that the lefthand sides are == +1 (mod n), respectively is reminiscent of an Euler pseudoprime test, but it's a weird mix of that, add a pinch of "base10 expansion ends in [1,3,7,9]"ness and sprinkle in a dash of Fibonacci/Lucassequence terms. His combinations of a = (1+sqrt(5))/2 and b = (1sqrt(5))/2 of form (a^{n}b^{n})/(ab) (n odd, n > 0) are just the oddindex Fibonacci numbers F(n) = 1,2,5,13,34,89,..., n = 1,3,5,7,... . I'm not 100% sure what he means by "MOD", since F(n)/n generally has a fractional remainder, but it seems he really means "truncate to nextsmaller integer," i.e. his "MOD" is really a "Floor". Rewritten that way, his formulae reduce to Code:
1 = F(n)  ( Floor( F(n)/n ) )*n, n == 1 or 9 (mod 10) and n1 = F(n)  ( Floor( F(n)/n ) )*n, n == 3 or 7 (mod 10) n = 3: F(n) = 2, F(n)/n = 2/ 3, Floor(F(n)/n) = 0, result = 2  0 = 2 = n1. n = 5: F(n) = 5, F(n)/n = 5/ 5, Floor(F(n)/n) = 1, result = 5  5 = 0, his formulae don't account for this. n = 7: F(n) = 13, F(n)/n = 13/ 7, Floor(F(n)/n) = 1, result = 13  7 = 6 = n1. n = 9: F(n) = 34, F(n)/n = 34/ 9, Floor(F(n)/n) = 3, result = 34  27 = 7 != 1. n = 11: F(n) = 89, F(n)/n = 89/11, Floor(F(n)/n) = 8, result = 89  88 = 1. n = 13: F(n) = 233, F(n)/n = 233/13, Floor(F(n)/n) = 17, result = 233  221 = 12 = n1. n = 15: F(n) = 610, F(n)/n = 610/15, Floor(F(n)/n) = 40, result = 610  600 = 10 != 1 or n1 (again, his formulae don't cover) n = 17: F(n) =1597, F(n)/n =1597/17, Floor(F(n)/n) = 93, result =1597 1581 = 16 = n1. So it appears to work as he claims, and he at least went to the trouble of testing up to (at least) n = 50000 and pointing out that there are some numbers falsely flagged as prime by this criterion. Based on the clunkiness of the "test" and the relatively high failure rate he himself cites I'm fairly sure there's nothing of practical interest to be had here, but nonetheless, comments would be appreciated  I'd like to give him at least a polite and hopefully semiauthoritative answer. Last fiddled with by ewmayer on 20070418 at 22:27 
20070418, 18:53  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
and suggest that he contact Mr. Harris for an opinion. 

20070418, 19:23  #3  
∂^{2}ω=0
Sep 2002
República de California
10110111010000_{2} Posts 
Quote:
Edit: ah, just had another "gah!" moment  when I first worked to understand the formulae in the aforementioned email and I realized they were just based on Fibonacci numbers in disguise, I simply gave the resulting simplified form: Quote:
For any odd prime n != 5, and the n^{th} Fibonacci number F(n): If n == 1 or 9 (mod 10), then F(n) == +1 (mod n) If n == 3 or 7 (mod 10), then F(n) == 1 (mod n). (Clearly the converse does not always hold  hence the atbest probableprime nature of the ensuing test.) Is this a known property of the Fibonacci numbers, or an obvious consequence of such? Last fiddled with by ewmayer on 20070418 at 20:50 

20070418, 21:05  #4 
Jan 2005
Transdniestr
503 Posts 
Ich don't think so
F(9) = 34 = 7 (mod 9)
Thru n=40, the relations also fail for n=1 (if that counts), 21,27,33,39 Not a very good batting average 
20070418, 21:10  #5  
∂^{2}ω=0
Sep 2002
República de California
2^{4}·733 Posts 
Quote:
For n = 9, the requirement for n prime is F(9) == +1 (mod 9), the result is 2==7 (mod 9), hence 9 not prime. Try it again  here's a simple Pari/bc commandline, you just look for results that are == +1 or 1 (mod n) and n = (1 or 9) or (3 or 7) mod 10, respectively, and see if for such cases n is in fact prime: n=1;a=0;b=1; (init  do just once) Then repeat the following: n+=2;f=a+b;a=b;b=f;f=a+b;a=b;b=f;f%n Last fiddled with by ewmayer on 20070418 at 21:18 

20070418, 21:34  #6 
Jan 2005
Transdniestr
503 Posts 
You're right. Sorry

20070419, 08:31  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Looks like a variant of the Fibonacci/Lucas prp test, described for example in C&P, 3.6.1.
Alex 
20070419, 13:28  #8 
Feb 2007
2^{4}·3^{3} Posts 
PARI allows to check quickly that no prime < 2*10^5 fails this test:
Code:
gp > forprime(p=1,99999,if((fibonacci(p)+abs(p10*round(p/10))2)%p, print(p))) 2 5 time = 3,933 ms. gp > forprime(p=1,199999,if((fibonacci(p)+abs(p10*round(p/10))2)%p, print(p))) 2 5 time = 21,913 ms. gp > Now, what's the complexity of calculating F(Mp) mod Mp for current primenet exponents p ? Last fiddled with by m_f_h on 20070419 at 13:33 
20070419, 19:35  #9 
Feb 2007
2^{4}×3^{3} Posts 
These seem to be strongly related: A049062 Composite n coprime to 5 such that Fibonacci(n) == Legendre(n,5) (mod n) 4181, 5474, 5777, 6479, 6721, 10877, 12958, 13201, 15251, 17302, 27071, 34561, 40948, 41998, 44099, 47519, 51841, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 75077, 78089, 88198, 90061, 95038, 96049, 97921 COMMENT If n is a prime, not 5, then Fibonacci(n) == Legendre(n,5) (mod n) (see for example G. H. Hardy and E. M. Wright, Theory of Numbers). REFERENCES Yorinaga, Masataka; On a congruencial property of Fibonacci numbersconsiderations and remarks. Math. J. Okayama Univ. 19 (1976/77), no. 1, 1117. Yorinaga, Masataka; On a congruencial property of Fibonacci numbersnumerical experiments. Math. J. Okayama Univ. 19 (1976/77), no. 1, 510. CROSSREFS Cf. A090820. A094401 Composite n such that n divides both Fibonacci(n1) and Fibonacci(n) 2737, 4181, 6721, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 90061, 96049, 97921, 118441, 146611, 163081, 179697, 186961, 194833, 197209, 219781, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 327313, 330929 CROSSREFS Cf. A005845, A069106, A094394, A094400. A091982 Nonprimes n such that Mod(n,4) == 1 and denominator(Fibonacci((n1)/4)/n) = 1. 1, 4181, 6721, 13201, 34561, 51841, 64681, 90061, 96049, 97921, 163081, 186961, 197209, 268801, 283361 (list; graph; listen) A094394 Odd composite n such that n divides Fibonacci(n)1. +20 5 323, 2737, 4181, 6479, 6721, 7743, 11663, 13201, 15251, 18407, 19043, 23407, 27071, 34561, 34943, 35207, 39203, 44099, 47519, 51841, 51983, 53663, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 78089, 79547, 82983, 86063, 90061, 94667 CROSSREFS Cf. A094395, A094400. A094395 Odd composite n such that n divides Fibonacci(n) + 1. 5777, 10877, 17261, 75077, 80189, 100127, 113573, 120581, 161027, 162133, 163059, 231703, 300847, 430127, 618449, 635627, 667589, 851927, 1033997, 1106327, 1256293, 1388903, 1697183, 1842581, 2263127, 2435423, 2512889, 2662277 A094063 Composite n such that Fibonacci(n) == Legendre(n,5) == 1 (mod n). 5777, 10877, 12958, 17302, 40948, 41998, 75077, 88198, 95038, 100127, 113573, 130942, 133742, 156178, 160378, 161027, 162133, 163438, 168838, 203942, 219742, 231703, 300847, 314158, 336598, 390598, 393118, 430127, 467038, 480478, 534508 (list; graph; listen) CROSSREFS Cf. A049062, A090820, A093372. A094411 Composite n such that n divides both Fibonacci(n+1) and Fibonacci(n) + 1. 5777, 10877, 75077, 80189, 100127, 113573, 161027, 162133, 231703, 430127, 618449, 635627, 667589, 851927, 1033997, 1106327, 1256293, 1388903, 1697183, 2263127, 2435423, 2512889, 2662277, 3175883, 3399527, 3452147, 3774377 (list; graph; listen) Last fiddled with by m_f_h on 20070419 at 19:57 
20070423, 16:18  #10  
∂^{2}ω=0
Sep 2002
República de California
2^{4}×733 Posts 
Quote:
Thanks for the reference  I was at work when I got and worked through the original email last week, and didn't have my copy of C&P handy. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2760  20220515 00:00 
"New" primality test/check  gophne  gophne  272  20180424 13:16 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 