Go Back > Great Internet Mersenne Prime Search > Math

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

10100012 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

8110 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
Cyclamen Persicum is offline   Reply With Quote

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 06:10.

Thu Feb 25 06:10:15 UTC 2021 up 84 days, 2:21, 0 users, load averages: 2.02, 2.16, 2.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.