 mersenneforum.org > Math "New primality proving test from Alex Petrov"
 Register FAQ Search Today's Posts Mark Forums Read  2007-04-18, 17:20 #1 ewmayer ∂2ω=0   Sep 2002 República de California 101101101010002 Posts "New primality proving test from Alex Petrov" Just got the following e-mail: 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 Fibonacci-sequence terms as I do below anyway, but in case you're interested, you can always save the image files locally (Right-click/"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 grown-up." On another point of verbiage, I believe by "n numbers" he means "positive integers." ================ From: "Alexey Petrov" To: 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_n-1.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 well-meaning, 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 left-hand 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 "base-10 expansion ends in [1,3,7,9]"-ness and sprinkle in a dash of Fibonacci/Lucas-sequence terms. His combinations of a = (1+sqrt(5))/2 and b = (1-sqrt(5))/2 of form (an-bn)/(a-b) (n odd, n > 0) are just the odd-index 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 next-smaller 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 n-1 = F(n) - ( Floor( F(n)/n ) )*n, n == 3 or 7 (mod 10) So let's try a couple: n = 3: F(n) = 2, F(n)/n = 2/ 3, Floor(F(n)/n) = 0, result = 2 - 0 = 2 = n-1. 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 = n-1. 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 = n-1. n = 15: F(n) = 610, F(n)/n = 610/15, Floor(F(n)/n) = 40, result = 610 - 600 = 10 != 1 or n-1 (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 = n-1. 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 semi-authoritative answer. Last fiddled with by ewmayer on 2007-04-18 at 22:27   2007-04-18, 18:53   #2
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Originally Posted by ewmayer Just got the following e-mail: I uploaded the 2 inline images to my ftp stash, but for some reason the GIFs won't display in my Firefox browser - I must say, I've been called many things, but "the known specialist in the theory of numbers..." 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 semi-authoritative answer.
Perhaps the best reply would be to give him James Harris' email address
and suggest that he contact Mr. Harris for an opinion.   2007-04-18, 19:23   #3
ewmayer
2ω=0

Sep 2002
República de California

23·3·487 Posts Quote:
 Originally Posted by R.D. Silverman Perhaps the best reply would be to give him James Harris' email address and suggest that he contact Mr. Harris for an opinion.
Well, to be fair, the present fellow at least isn't making any grandiose claims to have proved e.g. FLT by elementary means, as Mr. Harris does. Sure, the "new primality proving test" verbiage certainly trips the crank-o-meter, but the posters own work debunks the "proving test" aspect. In other words, it's at best a kind of PRP test, but in that sense seems to at least work as advertised. I thought I'd give Mr. Petrov the benefit of the "overexcited amateur" doubt on this one.

Edit: ah, just had another "gah!" moment - when I first worked to understand the formulae in the aforementioned e-mail and I realized they were just based on Fibonacci numbers in disguise, I simply gave the resulting simplified form:
Quote:
 Originally Posted by ewmayer Rewritten that way, his formulae reduce to Code: 1 = F(n) - ( Floor( F(n)/n ) )*n, n == 1 or 9 (mod 10) and n-1 = F(n) - ( Floor( F(n)/n ) )*n, n == 3 or 7 (mod 10)
but (this is the brainfart I just alluded to), for any real x and positive integer n, x - n*Floor(x/n) is just a fancy way of writing "x mod n". So Mr. Petrov's original ugly formulae reduce to the following simple claim:

For any odd prime n != 5, and the nth 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 at-best probable-prime 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 2007-04-18 at 20:50   2007-04-18, 21:05 #4 grandpascorpion   Jan 2005 Transdniestr 1F716 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   2007-04-18, 21:10   #5
ewmayer
2ω=0

Sep 2002
República de California

266508 Posts Quote:
 Originally Posted by grandpascorpion 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
No, you are misunderstanding the formula:

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 command-line, 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 2007-04-18 at 21:18   2007-04-18, 21:34 #6 grandpascorpion   Jan 2005 Transdniestr 503 Posts You're right. Sorry   2007-04-19, 08:31 #7 akruppa   "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   2007-04-19, 13:28 #8 m_f_h   Feb 2007 24×33 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(p-10*round(p/10))-2)%p, print(p))) 2 5 time = 3,933 ms. gp > forprime(p=1,199999,if((fibonacci(p)+abs(p-10*round(p/10))-2)%p, print(p))) 2 5 time = 21,913 ms. gp > (I rewrote the criterion as : F(n)+dist(n,10Z) == 2 (mod n).) Now, what's the complexity of calculating F(Mp) mod Mp for current primenet exponents p ? Last fiddled with by m_f_h on 2007-04-19 at 13:33   2007-04-19, 19:35 #9 m_f_h   Feb 2007 24×33 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 numbers-considerations and remarks. Math. J. Okayama Univ. 19 (1976/77), no. 1, 11-17. Yorinaga, Masataka; On a congruencial property of Fibonacci numbers-numerical experiments. Math. J. Okayama Univ. 19 (1976/77), no. 1, 5-10. CROSSREFS Cf. A090820. A094401 Composite n such that n divides both Fibonacci(n-1) 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((n-1)/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 2007-04-19 at 19:57   2007-04-23, 16:18   #10
ewmayer
2ω=0

Sep 2002
República de California

1168810 Posts Quote:
 Originally Posted by akruppa Looks like a variant of the Fibonacci/Lucas prp test, described for example in C&P, 3.6.1.
Yes, in fact it appears identical, except that Alexey's (1,9) and (3,7) mod 10 are described in terms of mod-5-ness in C&P, and the latter also includes the extra condition needed for 0 mod 5.

Thanks for the reference - I was at work when I got and worked through the original e-mail last week, and didn't have my copy of C&P handy.   2007-04-23, 17:48 #11 m_f_h   Feb 2007 24·33 Posts I think the sequence A049062 and the first comment to it explains everything, don't you agree ? (Odd terms of this sequence are exactly Petrov's exceptions.)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2751 2022-01-03 14:57 gophne gophne 272 2018-04-24 13:16 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 14:05.

Fri Jan 21 14:05:27 UTC 2022 up 182 days, 8:34, 0 users, load averages: 0.97, 1.26, 1.21