
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 22nd, 2018, 07: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; } That said I know there are much better (well I mean PROVEN!) tests such as MillerRabin 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 07:47 PM. 
August 22nd, 2018, 07:44 PM  #2 
Senior Member Joined: Feb 2016 From: Australia Posts: 1,734 Thanks: 605 Math Focus: Yet to find out. 
Java and Javascript are different things btw...

August 22nd, 2018, 07:59 PM  #3 
Member Joined: Jul 2010 Posts: 83 Thanks: 2  
August 22nd, 2018, 10:11 PM  #4 
Senior Member Joined: Aug 2012 Posts: 2,082 Thanks: 595  
August 23rd, 2018, 10:15 AM  #5 
Member Joined: Jul 2010 Posts: 83 Thanks: 2  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, 10: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.

August 24th, 2018, 01:08 AM  #7  
Member Joined: Jul 2010 Posts: 83 Thanks: 2  Quote:
 
August 24th, 2018, 03:00 AM  #8 
Newbie Joined: Aug 2018 From: Sydney Posts: 6 Thanks: 1  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, 03:51 AM  #9  
Member Joined: Jul 2010 Posts: 83 Thanks: 2  Quote:
 

Tags 
curious, primality, test 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New primality test  mobel  Number Theory  29  October 10th, 2015 10:24 PM 
Help to disprove a primality test  Tylerman  Number Theory  4  June 15th, 2012 09:07 PM 
Primality test Ąż!?  mathbalarka  Number Theory  1  June 2nd, 2012 04:59 PM 
New primality test?  Bogauss  Number Theory  19  May 24th, 2012 10:26 AM 
New primality test  momo  Number Theory  21  May 2nd, 2009 02:44 PM 