Converse of Proth's Theorem

[R.D. Silverman]

Originally Posted by Retep

It wasn't to difficult to program the check of the condition "(N/a) is a quadratic non-residue". I want to know why this is enough, this means I'm looking for a proof of this "extended version" of Proth's theorem:

a^((N-1)/2) = (N/a) = -1 (mod N) [a prime, N=k*2^n+1,k<2^n]

which is a necessary and sufficient condition for N to be prime.


Does anyone know where to find this proof? I have not found it in Crandall and Pomerance: Prime numbers.

You can find it in the Cunningham book. When k < 2^n, it means that
you know the factorization of N-1 up to sqrt(N). You can then use
theorems of Lehmer, Selfridge and Brillhart as described in the Cunningham
book.

[Retep]

Originally Posted by R.D. Silverman

You can find it in the Cunningham book. When k < 2^n, it means that
you know the factorization of N-1 up to sqrt(N). You can then use
theorems of Lehmer, Selfridge and Brillhart as described in the Cunningham
book.

Could you tell me the title or ISBN of this book?
Many thanks in advance.

[bsquared]

Originally Posted by Retep

Could you tell me the title or ISBN of this book?
Many thanks in advance.

It is available online here:
http://www.ams.org/online_bks/conm22/

[Retep]

Originally Posted by bsquared

It is available online here:
http://www.ams.org/online_bks/conm22/

Is this paper the same that R.D. Silverman meant? It is not by Cunningham. Perhaps I am missing something, but I only found the "usual" version of Proth's theorem in it.

[bsquared]

Originally Posted by Retep

Is this paper the same that R.D. Silverman meant? It is not by Cunningham. Perhaps I am missing something, but I only found the "usual" version of Proth's theorem in it.

It is a book *about* Cunningham numbers. If I remember right, Cunningham's work took place in the early 20th century, and this book incorporates that information, plus a great deal more that has occured since then. I can't help you about the theorems.