- Dec 30, 2003Guys,

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 primenumbers@yahoogroups.com, mikeoakes2@a... wrote:

> 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/

Yahoo! Groups SponsorADVERTISEMENT

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

Yahoo! Groups Links

To visit your group on the web, go to:

http://groups.yahoo.com/group/primenumbers/

To unsubscribe from this group, send an email to:

primenumbers-unsubscribe@yahoogroups.com

Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

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

Do you Yahoo!?

Free Pop-Up Blocker - Get it now

[Non-text portions of this message have been removed] - << Previous post in topic Next post in topic >>