20060816, 02:30  #1 
Aug 2004
Melbourne, Australia
2^{3}×19 Posts 
Alternate means of primality testing
Sorry I haven't been around for a while  I've started a PhD in combinatorics and don't have much time to do things like this.
From my experience of primality proving, the tests that I have seen boil down to one of two things:  Trial division.  Proving that phi(n)=n1, by proving that the multiplicative group Z_n has order n1. Do there exist primality tests that are essentially different? If so, could you please provide an example? Note: I do not care about efficiency here. 
20060816, 04:51  #2 
Sep 2005
127 Posts 
Well, I suppose there's always Wilson's Theorem  you did say you weren't concerned with efficiency!
J 
20060816, 09:03  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,639 Posts 
Quote:
Ok, this is a cheeky answer, exploiting your overprecise specification. Here are a few more.  Sieve of Eratosthenes.  Find the positive values of a certain notorious polynomial in 26 variables.  MillerRabin to enough small bases. Exactly how many depends on whether anyone has proved ERH yet. Paul 

20060816, 10:27  #4 
Aug 2004
Melbourne, Australia
10011000_{2} Posts 
Thanks for your responses.
Wilson's theorem is an interesting example. Does it fit into a category I listed? I'm not sure. By multiplying 1, 2, ..., n1 together you're in effect trying to find two divisors of n in the list and get a zero congruence (or when n is prime, a nonzero congruence (ignoring the special case n=4)). So it's basically GCD(n,(n1)!)=n if and only if n is composite. Arguably, this could be considered trial division. I'm consider factorisation and the sieve method to be classed as trial division. Your notorious polynomial with 26 variables? http://mathworld.wolfram.com/PrimeDi...Equations.html I do not know what to think of this! Upon inspection of its proof (Jones et al. 1976) it has more perplexing ideas: Theorem 5: If p is a prime number, then there is a proof that p is prime consisting of only 87 additions and multiplications. This looks like a good example of a theorem that doesn't fit into one of the two categories I listed. I'd be interested if there are other theorems people can come up with. 
20060816, 11:14  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
large in (log p). 

20060816, 11:46  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
24617_{8} Posts 
Quote:
A much better phrase, IMO, would be something like "exhibit a divisor other than 1 and p", which covers all factorization methods and the SoE. Paul 

20060816, 11:50  #7 
Aug 2003
Snicker, AL
7·137 Posts 
Translating some of the above into useful language. There are several methods of proving a number prime but at a cost in time that is unacceptably large. I can show you a factoring method that is different from any of the above but using it to factor a 10 million digit number would take longer to run than the universe has been in existence.
Fusion 
20060816, 11:51  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,639 Posts 
Quote:
Paul 

20060816, 11:57  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Granted, it doesn't work in Z/ZN, and neither do P+1 primality proofs. But both fall into the class of "determine order of some finite group, and voila it's a prime," just like P1 proofs.
What about APRCL? I know little about it, but afaik it uses the theory of algebraic number fields rather than the structure of a finite group. Alex Last fiddled with by akruppa on 20090530 at 09:31 
20060816, 16:18  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10639_{10} Posts 
Quote:
Perhaps he's learning how to phrase his question. Paul 

20060817, 00:18  #11 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Yes, I agree that my two categories are rather loosely defined. Mostly where these theorems fit is a matter of opinion. I must admit my ignorance with elliptic curves, so I cannot make a valid comment on ECPP.
I think APRTCL is a good example, it looks fundamentally different. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
a new Deterministic primality testing  wsc812  Computer Science & Computational Number Theory  36  20130304 06:25 
Automated primality testing with LLRnet  mdettweiler  Conjectures 'R Us  18  20080304 00:06 
a new primality testing method  jasong  Math  1  20071106 21:46 