2004-04-19, 12:35 | #1 |
Mar 2003
3^{4} Posts |
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. |
2004-04-20, 04:54 | #2 |
Mar 2003
51_{16} Posts |
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 |
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 |