mersenneforum.org > Math Extended Proth Theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2004-04-19, 12:35 #1 Cyclamen Persicum     Mar 2003 1218 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 Cyclamen Persicum     Mar 2003 34 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

 Similar Threads Thread Thread Starter Forum Replies Last Post rekcahx Factoring 6 2011-08-19 12:45 ATH Math 9 2011-02-15 19:09 Bill Bouris Conjectures 'R Us 4 2009-04-07 13:25 Zeta-Flux Factoring 2 2008-03-03 18:34 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