My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
  • 1 Post By SylviaElse
Reply
 
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;
}
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 07:47 PM.
Sebastian Garth is offline  
 
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...
Joppy is online now  
August 22nd, 2018, 07:59 PM   #3
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by Joppy View Post
Java and Javascript are different things btw...
Yep, this is Javascript though (note the var keyword).
Sebastian Garth is offline  
August 22nd, 2018, 10:11 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,082
Thanks: 595

Quote:
Originally Posted by Sebastian Garth View Post
Long story...
How about a verbal explanation and an example or two?
Maschke is online now  
August 23rd, 2018, 10:15 AM   #5
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by Maschke View Post
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.
Sebastian Garth is offline  
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.
Thanks from Sebastian Garth
SylviaElse is offline  
August 24th, 2018, 01:08 AM   #7
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by SylviaElse View Post
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.
Sebastian Garth is offline  
August 24th, 2018, 03:00 AM   #8
Newbie
 
Joined: Aug 2018
From: Sydney

Posts: 6
Thanks: 1

Quote:
Originally Posted by Sebastian Garth View Post
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.
SylviaElse is offline  
August 24th, 2018, 03:51 AM   #9
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by SylviaElse View Post
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...
Sebastian Garth is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.