Alternate means of primality testing - Page 2

R.D. Silverman · 2006-08-17, 10:41

Quote:

Originally Posted by Dougy

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 APRT-CL is a good example, it looks fundamentally different.

It really isn't. APRCL replaces a single PRP prime test in Z/NZ with a bunch
of PRP tests in cyclotomic rings.

If one knows enough factors note only of n-1 and n+1, but also of
n^2 + 1, n^2 +/- n + 1, n^3 + n + 1 etc. (All cyclotomic polynomials)
one can extend the method of finding a primitive root to take advantage
of the additional known factors. This is classical and is due to Lucas,
Lehmer, Selfridge, Brillhart, H. Williams etc. [see the Cunningham book]

APRCL basically looks at a LOT of different cyclotomic polynomials
(of higher degree) more or less simultaneously. It is just an extension
of the classical techniques.

Dougy · 2006-08-17, 23:39

I see. Anyway, the reason I ask is that my work on Latin rectangles yielded a primality test that, on the surface, seems to have no relation to the two catagories listed. This is just a sideline of the work - and it's a completely impractical primality test, but certainly one can input n and it will output if n is prime or not within a finite amount of time. At the moment I don't think it should be discussed more than "Amusingly, this results in a primality test."

Dougy · 2009-01-02, 23:00

Sorry for being a bit vague before. But I feel I can post this now without any real problems. It's been presented at conferences a number of times and has been submitted for some time now. I think this is quite a cute result.

A Latin square of order $n$ is a $n \times n$ matrix of $n$ symbols such that every symbol occurs exactly once in every row and every column. I'll use the symbols $\mathbb{Z}_n=\{0,1,\dots,n-1\}$ . A Latin square is called reduced if its first row is $(0,1,\dots,n-1)$ and first column is $(0,1,\dots,n-1)^T$ . Let $R_n$ be the number of reduced Latin squares.

Theorem: $R_n \pmod n$ is an indicator variable for primality. That is, $R_n \equiv 1 \pmod n$ if $n$ is prime and $R_n \equiv 0 \pmod n$ if $n$ is composite.

Smetaniuk showed that $R_{n-1} \geq (n-1)!R_n$ for all n. So this is a rather silly primality test. We only know $R_n$ upto $n=11$ (McKay and Wanless).

R.D. Silverman · 2009-01-02, 23:09

Quote:

Originally Posted by Dougy

Sorry for being a bit vague before. But I feel I can post this now without any real problems. It's been presented at conferences a number of times and has been submitted for some time now. I think this is quite a cute result.

A Latin square of order $n$ is a $n \times n$ matrix of $n$ symbols such that every symbol occurs exactly once in every row and every column. I'll use the symbols $\mathbb{Z}_n=\{0,1,\dots,n-1\}$ . A Latin square is called reduced if its first row is $(0,1,\dots,n-1)$ and first column is $(0,1,\dots,n-1)^T$ . Let $R_n$ be the number of reduced Latin squares.

Theorem: $R_n \pmod n$ is an indicator variable for primality. That is, $R_n \equiv 1 \pmod n$ if $n$ is prime and $R_n \equiv 0 \pmod n$ if $n$ is composite.

Smetaniuk showed that $R_{n-1} \geq (n-1)!R_n$ for all n. So this is a rather silly primality test. We only know $R_n$ upto $n=11$ (McKay and Wanless).

$R_{n-1} \geq (n-1)!R_n$ for all n

This makes R_n a decreasing function.... e.g. R_6 = 720 R_7......Unless
you mean R_{n+1} on the left????

It is an interesting result.... Sort of similar to using Wilson's Thm.

Dougy · 2009-01-03, 00:10

Quote:

Originally Posted by R.D. Silverman

$R_{n-1} \geq (n-1)!R_n$ for all n

This makes R_n a decreasing function.... e.g. R_6 = 720 R_7......Unless
you mean R_{n+1} on the left????

Indeed it is R_{n+1}... oops!

Dougy · 2009-01-08, 05:24

By the way, if there's anyone who's interested in doing a PhD or similar in combinatorics (eg. combinatorial number theory) my supervisor is looking for students (here is his webpage). Some possible topics are here.

Dougy · 2009-04-30, 06:30

Anyway, this paper has now been accepted, which is quite exciting for me as it's my first paper (Erdos number 3). I'll post a link when it becomes available.

Quote:

Originally Posted by Dougy

Theorem: $R_n \pmod n$ is an indicator variable for primality. That is, $R_n \equiv 1 \pmod n$ if $n$ is prime and $R_n \equiv 0 \pmod n$ if $n$ is composite.

Dougy · 2009-05-29, 22:57

It's published online (if anyone is interested): D.S. Stones, I.M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A (2009), doi:10.1016/j.jcta.2009.03.019

CRGreathouse · 2009-05-30, 04:35

Congrats!

I'll look it up come Monday.

Dougy · 2009-09-01, 01:48

On this theme: we just submitted a paper that shows $R_{n+1} \pmod n$ is $-2$ is $n$ is prime and $0$ if $n$ is composite.

D.S. Stones, I.M. Wanless, Compound orthomorphisms of the cyclic group, submitted.

Actually, this was just a minor sideline of our study of a special class of orthomorphisms of $\mathbb{Z}_n$ (permutations $\sigma$ such that $i \mapsto \sigma(i)-i$ is also a permutation).

Dougy · 2009-09-12, 04:13

Hmm... I just realised that I didn't state that the above remark is false when n=2. (yes, we did spot that in the paper)

2009-09-01, 01:48	#21
Dougy Aug 2004 Melbourne, Australia 2³×19 Posts	On this theme: we just submitted a paper that shows $R_{n+1} \pmod n$ is $-2$ is $n$ is prime and $0$ if $n$ is composite. D.S. Stones, I.M. Wanless, Compound orthomorphisms of the cyclic group, submitted. Actually, this was just a minor sideline of our study of a special class of orthomorphisms of $\mathbb{Z}_n$ (permutations $\sigma$ such that $i \mapsto \sigma(i)-i$ is also a permutation). Last fiddled with by Dougy on 2009-09-01 at 01:48

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primality testing non-Mersennes	lukerichards	Software	8	2018-01-24 22:30
Testing an expression for primality	1260	Software	17	2015-08-28 01:35
a new Deterministic primality testing	wsc812	Computer Science & Computational Number Theory	36	2013-03-04 06:25
Automated primality testing with LLRnet	mdettweiler	Conjectures 'R Us	18	2008-03-04 00:06
a new primality testing method	jasong	Math	1	2007-11-06 21:46

2006-08-17, 23:39	#13
Dougy Aug 2004 Melbourne, Australia 2³·19 Posts	I see. Anyway, the reason I ask is that my work on Latin rectangles yielded a primality test that, on the surface, seems to have no relation to the two catagories listed. This is just a sideline of the work - and it's a completely impractical primality test, but certainly one can input n and it will output if n is prime or not within a finite amount of time. At the moment I don't think it should be discussed more than "Amusingly, this results in a primality test."

2009-01-02, 23:00	#14
Dougy Aug 2004 Melbourne, Australia 152₁₀ Posts	Sorry for being a bit vague before. But I feel I can post this now without any real problems. It's been presented at conferences a number of times and has been submitted for some time now. I think this is quite a cute result. A Latin square of order $n$ is a $n \times n$ matrix of $n$ symbols such that every symbol occurs exactly once in every row and every column. I'll use the symbols $\mathbb{Z}_n=\{0,1,\dots,n-1\}$ . A Latin square is called reduced if its first row is $(0,1,\dots,n-1)$ and first column is $(0,1,\dots,n-1)^T$ . Let $R_n$ be the number of reduced Latin squares. Theorem: $R_n \pmod n$ is an indicator variable for primality. That is, $R_n \equiv 1 \pmod n$ if $n$ is prime and $R_n \equiv 0 \pmod n$ if $n$ is composite. Smetaniuk showed that $R_{n-1} \geq (n-1)!R_n$ for all n. So this is a rather silly primality test. We only know $R_n$ upto $n=11$ (McKay and Wanless).

2009-01-08, 05:24	#17
Dougy Aug 2004 Melbourne, Australia 2³·19 Posts	By the way, if there's anyone who's interested in doing a PhD or similar in combinatorics (eg. combinatorial number theory) my supervisor is looking for students (here is his webpage). Some possible topics are here.

2009-05-29, 22:57	#19
Dougy Aug 2004 Melbourne, Australia 10011000₂ Posts	It's published online (if anyone is interested): D.S. Stones, I.M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A (2009), doi:10.1016/j.jcta.2009.03.019

2009-05-30, 04:35	#20
CRGreathouse Aug 2006 3·1,993 Posts	Congrats! I'll look it up come Monday.

2009-09-12, 04:13	#22
Dougy Aug 2004 Melbourne, Australia 2³·19 Posts	Hmm... I just realised that I didn't state that the above remark is false when n=2. (yes, we did spot that in the paper)