mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-04-19, 12:35   #1
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

1218 Posts
Default Extended Proth Theorem

I am writing a Proth prime generator (yet another... ;-)
The Proth theorem says:

"Let n > 1, k < 2^n and N = k*2^n + 1 be a quadratic non-residue (mod a) for some odd prime a. Then the necessary and sufficient condition for N to be a prime is that:
a^((N-1)/2) = (N/a) = -1 (mod N) "

Why the hell a small witness "a" must be obligatory prime?
I believe that every odd number is suit. And I could not find
any quadratic non-residue which gives 1 instead -1 being powered.
Cyclamen Persicum is offline   Reply With Quote
Old 2004-04-20, 04:54   #2
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

Sorry, I have noticed a pun...
JacobiSymbol = -1 does not mean "quadratic non-residue".
But I'm right, there is a super-extended Proth theorem:
for integer _a_ with Jacobi(a,N)=-1 (or for odd _a_ with Jacobi(N mod a,a)=-1) N=k*2^n+1 (k<2^n) to be prime if and only if a^[(N-1)/2]=-1 (mod N).

So I take a small odd _a_ rather then a small prime _a_ which Ylos Gallot takes in his Proth.exe
Cyclamen Persicum is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extended Cunningham or so rekcahx Factoring 6 2011-08-19 12:45
Proth's Theorem ATH Math 9 2011-02-15 19:09
Proth theorem extended Bill Bouris Conjectures 'R Us 4 2009-04-07 13:25
Extended Cunningham tables Zeta-Flux Factoring 2 2008-03-03 18:34
Converse of Proth's Theorem Dougy Math 15 2008-01-30 21:17

All times are UTC. The time now is 01:36.

Wed Dec 2 01:36:36 UTC 2020 up 82 days, 22:47, 1 user, load averages: 1.39, 1.86, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.