mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-04-18, 17:20   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2D9A16 Posts
Default "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" <alexey-petrov-job@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_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
ewmayer is offline   Reply With Quote
Old 2007-04-18, 18:53   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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 -

<snip>

I must say, I've been called many things, but "the known specialist in the theory of numbers..."


<snip>

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.
R.D. Silverman is offline   Reply With Quote
Old 2007-04-18, 19:23   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·13·449 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
ewmayer is offline   Reply With Quote
Old 2007-04-18, 21:05   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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
grandpascorpion is offline   Reply With Quote
Old 2007-04-18, 21:10   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2D9A16 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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
ewmayer is offline   Reply With Quote
Old 2007-04-18, 21:34   #6
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

You're right. Sorry
grandpascorpion is offline   Reply With Quote
Old 2007-04-19, 08:31   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Looks like a variant of the Fibonacci/Lucas prp test, described for example in C&P, 3.6.1.

Alex
akruppa is offline   Reply With Quote
Old 2007-04-19, 13:28   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1B016 Posts
Default

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
m_f_h is offline   Reply With Quote
Old 2007-04-19, 19:35   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

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
m_f_h is offline   Reply With Quote
Old 2007-04-23, 16:18   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×13×449 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
ewmayer is offline   Reply With Quote
Old 2007-04-23, 17:48   #11
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1101100002 Posts
Default

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.)
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2734 2021-11-14 05:33
"New" primality test/check gophne gophne 272 2018-04-24 13:16
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 15:50.


Mon Nov 29 15:50:18 UTC 2021 up 129 days, 10:19, 0 users, load averages: 1.25, 1.35, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.