My Math Forum A most curious primality test...

 Number Theory Number Theory Math Forum

 August 22nd, 2018, 06:42 PM #1 Member   Joined: Jul 2010 Posts: 83 Thanks: 2 A most curious primality test... Long story, but when I came up with this test it was just supposed to be a placeholder of sorts for the actual test I was to be working on. Here it is, written in Javascript (I know, lousy choice for number theory): Code: /* Constraint: N = -1 mod 12 (must be odd N > 3) */ function maybe_prime(N) { var value = big_integer(N); /* Start with base equal to (N - 1) / 2 */ var base = value.shiftRight(1); var previous = value.minus(1); for(;;) { if(base.lesser(2)) break; /* Fermat test */ if(!base.modPow(previous, value).equals(1)) return false; /* Divide base in half, discarding any remainder obviously */ base = base.shiftRight(1); } return true; } Strange thing is it just seems to work. I've tested all N < 7x10^8 and millions of random samples ranging from 10^9 to 10^400 and not a single false positive. That said I know there are much better (well I mean PROVEN!) tests such as Miller-Rabin which perform in more than acceptable running time, but I'd just like to know if there is any theoretical basis at all for this? Most likely just a fluke that will eventually produce a counterexample but... Last edited by Sebastian Garth; August 22nd, 2018 at 06:47 PM.
 August 22nd, 2018, 06:44 PM #2 Senior Member   Joined: Feb 2016 From: Australia Posts: 1,790 Thanks: 629 Math Focus: Yet to find out. Java and Javascript are different things btw...
August 22nd, 2018, 06:59 PM   #3
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
 Originally Posted by Joppy Java and Javascript are different things btw...
Yep, this is Javascript though (note the var keyword).

August 22nd, 2018, 09:11 PM   #4
Senior Member

Joined: Aug 2012

Posts: 2,255
Thanks: 681

Quote:
 Originally Posted by Sebastian Garth Long story...
How about a verbal explanation and an example or two?

August 23rd, 2018, 09:15 AM   #5
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
 Originally Posted by Maschke How about a verbal explanation and an example or two?
Oh I just meant the whole backstory of what lead up to me choosing N = -1 mod 12 and so forth. Not really important at this point.

But the more I think about it the less faith I have in this test anyhow. I just can't see any number theoretic basis whatsoever for what's going on here. Eventually the law of large numbers will probably prove this to be false. Interesting anomaly though.

 August 23rd, 2018, 09:10 PM #6 Newbie   Joined: Aug 2018 From: Sydney Posts: 6 Thanks: 1 You're doing the Fermat test repeatedly with different values. On each occasion, the chance of getting 1 by chance if N isn't prime is about 1/N. For largish N the probablity that you'll get 1 by chance is about (1/N) ^ (log2(N) - 2), so the function has an exceedingly low probability of wrongly concluding that N is prime. Thanks from Sebastian Garth
August 24th, 2018, 12:08 AM   #7
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
 Originally Posted by SylviaElse You're doing the Fermat test repeatedly with different values. On each occasion, the chance of getting 1 by chance if N isn't prime is about 1/N. For largish N the probablity that you'll get 1 by chance is about (1/N) ^ (log2(N) - 2), so the function has an exceedingly low probability of wrongly concluding that N is prime.
That is true, but one thing I did notice is that it doesn't seem to work out so well for numbers that aren't congruent to -1 mod 12. A good thing of course if you're testing potential "safe primes" since they always satisfy that congruence, but nonetheless still pretty perplexing.

August 24th, 2018, 02:00 AM   #8
Newbie

Joined: Aug 2018
From: Sydney

Posts: 6
Thanks: 1

Quote:
 Originally Posted by Sebastian Garth That is true, but one thing I did notice is that it doesn't seem to work out so well for numbers that aren't congruent to -1 mod 12.
For smaller numbers you're not doing many tests, which increases the chances of a false positive. Requiring that the number be congruent to -1 mod 12 excludes the possibility that it's a multiple of 2 or 3, which eliminates a large number of candidates that are definitely not prime whatever the primality test might say.

August 24th, 2018, 02:51 AM   #9
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
 Originally Posted by SylviaElse For smaller numbers you're not doing many tests, which increases the chances of a false positive. Requiring that the number be congruent to -1 mod 12 excludes the possibility that it's a multiple of 2 or 3, which eliminates a large number of candidates that are definitely not prime whatever the primality test might say.
No, that that's not it. Replace 12 with 22 for example and false positives are fairly abundant. There's some other principle at work here...

 Tags curious, primality, test

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mobel Number Theory 29 October 10th, 2015 09:24 PM Tylerman Number Theory 4 June 15th, 2012 08:07 PM mathbalarka Number Theory 1 June 2nd, 2012 03:59 PM Bogauss Number Theory 19 May 24th, 2012 09:26 AM momo Number Theory 21 May 2nd, 2009 01:44 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top