14288Re: [PrimeNumbers] Re: Modification of PFGW

Expand Messages
• Dec 30, 2003
Guys,
Again I say, I am not as smart as some of you guys, but I do understand a PRP of primality test. After all, I am a mathematician. All I am saying is that I don't know the process that PFGW is taking in checking for PRP's. I do know that if we want to check for b^(N-1)%N, we let N-1 = d*2^t, where d is odd. Then do b^d%N and squaring from there.
Now, a Carol number, because of it form C = [4^k - 2^(k+1) - 1] can easily be tested. If we define E = (C-1)/2 and let b = 2, from Euler we get 2^E == 1 mod C if C is prime. Because E is always odd for a Carol number we would calculate 2^E and then do one squaring. I don't know of any other faster way of getting there. We can quickly calculate (N+1)/2 = 2^k[2^(k-1) - 1]. There are more squaring, and I think that calculating 2^E will be a lot faster. As a matter of FACT, it will take 2k loops to calculate 2^E.

Here is the full test (be forewarned...this is Programming in Basic codes)...
---------------------------------------------
d=2
for i = 2 to k
d = d^2==Ck; read C sub k, where Ck = (2^k-1)^2 - 2
Next i
If odd(d) then d = d+Ck
d = d/2
For J = 1 to k
d = d^2==Ck
Next j
if d = 2 then Ck is 2-EPRP
-------------------------------------------------------------
I am going further to conjecture that if d = 2 in the last line of the test then Ck is prime. In short, I am saying that Ck is prime iff Ck divides C(k+E).

I may still be wrong about everything above in terms of making PFGW more efficient, but guys show me the way, don't knock me down. I have always thought of this group as a group that I can learn a lot from. In any event, if there is anyone that can implement this into PFGW please let me know ASAP. I know that i am saying, think that I just can't explain it fully. If I can prove my conjecture, then finding a new worlds largest prime will be as easy as testing for 2-EPRP, which in the case of Carol or Kynea numbers would take about 2*k steps....

Just a little note: Carol and Kynea primes are more densely populated than Mersenne in a given range from 1 to 'n'. So far, there are 32 Carol and 40 Kynea for k-values <= 100,000.
grostoon <grostoon@...> wrote:
Hi all,

I agree with you that for huge N, computing b^((N-1)/2)%N instead of
b^(N-1)%N result in a negligible time gain.

But what if you consider the accuracy of the test itself rather than
the time it takes : why just doing a basic fermat prp test ?
Maybe I'm missing something but I believed that a strong probable
prime test (rabin-miller's prp test) was more accurate than the
simple fermat's test (and not much difficult to implement). Am I
wrong ?

Jean-Louis.

> In a message dated 23/12/03 22:00:27 GMT Standard Time,
cemmanu@y...
> writes:
>
>
> > I've been asking of Chris Nash ( I presume that he is very busy)
to modify
> > PFGW to check for Carol/Kynea numbers for a while now....Can
anyone modify
> > PFGW to do b^((N-1)/2)%N rather than b^(N-1)%N? There is even a
faster way (I
> > think) I can let it calculate b^((N-1)/2)%N (with a basic for
loop)....
> >
>
>
> You do realize, do you, that for N = 2^1000000-1 (for example), "to
do
> b^((N-1)/2)%N rather than b^(N-1)%N" takes 999999 rather than
1000000 FFTs; in other
> words, there is a negligible difference in execution time.
>
> PFGW is already a highly optimized and efficient program; so if you
think
> simple ideas involving "a basic for loop" are going to make it
faster, you are
> probably mistaken.
>
> The proper forum for this discussion is really the primeform group,
or, for
> implementation issues, openpfgw.
>
> -Mike Oakes
>
>
> [Non-text portions of this message have been removed]

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/

---------------------------------

To visit your group on the web, go to:

To unsubscribe from this group, send an email to: