[QUOTE=Retep;124330]It wasn't to difficult to program the check of the condition "([I]N[/I]/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.[/QUOTE]

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.

.
 

[quote=R.D. Silverman;124336]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.[/quote]

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

[quote=Retep;124343]Could you tell me the title or ISBN of this book?
Many thanks in advance.[/quote]

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

.
 

[quote=bsquared;124344]It is available online here:
[URL]http://www.ams.org/online_bks/conm22/[/URL][/quote]

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.

[quote=Retep;124368]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.[/quote]

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.