"New primality proving test from Alex Petrov"

[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 - 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 (aⁿ-bⁿ)/(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

  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.

[R.D. Silverman]

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 -

<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.

[ewmayer]

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:

Originally Posted by ewmayer

Rewritten that way, his formulae reduce to

  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 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 at-best probable-prime nature of the ensuing test.)

Is this a known property of the Fibonacci numbers, or an obvious consequence of such?

[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

[ewmayer]

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

[grandpascorpion]

You're right. Sorry

[akruppa]

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

Alex

[m_f_h]

PARI allows to check quickly that no prime < 2*10^5 fails this test:

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 ?

[m_f_h]

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)

[ewmayer]

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.

[m_f_h]

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