- Jean,

Thank you for the new version in almost no time!

I tried to test Kynea numbers. It's working but it's slower

than pfgw. Two examples are given below. Now I'm testing k*2^n+1.

(2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :

929.038 sec. [LLR 3.3, 2.4 GHz P4]

(2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]

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

(2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:

A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]

(2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)

[pfgw, 2.4GHz P4]

Regards,

Predrag - --- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...> wrote:
>

The way to speed up searching Carol/Kynea numbers is through modular

> Jean,

> Thank you for the new version in almost no time!

>

> I tried to test Kynea numbers. It's working but it's slower

> than pfgw. Two examples are given below. Now I'm testing k*2^n+1.

>

> (2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :

> 929.038 sec. [LLR 3.3, 2.4 GHz P4]

>

> (2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]

>

> --------------------

> (2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:

> A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]

>

> (2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)

> [pfgw, 2.4GHz P4]

>

reduction. When reducing over 2^n+-2^k-1 ( k<70% of n ingeneral ) we

can use additions and shifts only; There is no need for general

modular reduction. Maybe we need a new library from George Woltman...

Paul - Thank you for your tests !

I am not surprised if LLPP4 deterministic test is slower than pfgw PRP

one, because the "Computing U0" loop is more time consuming than the

LL loop... Is the deterministic pfgw test also faster ?

Second question : with composite candidates, you found different

residues with pfgw and with LLRP4, it may be normal, or it may be

still an LLR bug...

Regards,

Jean

--- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...> wrote:

>

> Jean,

> Thank you for the new version in almost no time!

>

> I tried to test Kynea numbers. It's working but it's slower

> than pfgw. Two examples are given below. Now I'm testing k*2^n+1.

>

> (2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :

> 929.038 sec. [LLR 3.3, 2.4 GHz P4]

>

> (2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]

>

> --------------------

> (2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:

> A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]

>

> (2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)

> [pfgw, 2.4GHz P4]

>

> Regards,

> Predrag > I am not surprised if LLPP4 deterministic test is slower than pfgw

PRP

> one, because the "Computing U0" loop is more time consuming than the

This is true, it takes about 50 minutes to compute U0, I'll

> LL loop...

append the lresults.txt file tomorrow.

> Is the deterministic pfgw test also faster ?

No! To prove primality of a PRP using "pfgw -tp" is very slow.

Again I don't have exact timings handy but I think at least an

hour in comparison to less than 18 minutes to find that

(2^110615+1)^2-2 is 3-PRP.

> Second question : with composite candidates, you found different

The input is different too, n=240068 and n=240065. The survival

> residues with pfgw and with LLRP4, it may be normal, or it may be

> still an LLR bug...

rate of Kynea (and Carol) is high and there are so many

candidates to test that I simply cannot afford to process the

same number twice :-)) Will try the same number later using

smaller exponents.

BTW, testing k*2^n+1, n~180,000, both the new LLR and PRP3

could process one number in almost exactly the same time, about

66 sec on 2.4GHz P-4.

Regards,

Predrag- The following is posted on behalf of "Jean Penne" who sent his reply

to "primenumbers-owner" instead of "primenumbers" by mistake.

Cheers

Ken

--- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...>

wrote:>

pfgw

> > I am not surprised if LLPP4 deterministic test is slower than

> PRP

the

> > one, because the "Computing U0" loop is more time consuming than

> > LL loop...

Thanks by advance !

>

> This is true, it takes about 50 minutes to compute U0, I'll

> append the lresults.txt file tomorrow.

>

> > Is the deterministic pfgw test also faster ?

I am also not surprised : Deterministic pfgw pays for its more

>

> No! To prove primality of a PRP using "pfgw -tp" is very slow.

> Again I don't have exact timings handy but I think at least an

> hour in comparison to less than 18 minutes to find that

> (2^110615+1)^2-2 is 3-PRP.

>

general algorithms than those of LLR.

> > Second question : with composite candidates, you found different

My fault ! I did'nt see the inputs were different...

> > residues with pfgw and with LLRP4, it may be normal, or it may be

> > still an LLR bug...

>

> The input is different too, n=240068 and n=240065. The survival

> rate of Kynea (and Carol) is high and there are so many

> candidates to test that I simply cannot afford to process the

> same number twice :-)) Will try the same number later using

> smaller exponents.

>

> BTW, testing k*2^n+1, n~180,000, both the new LLR and PRP3

Again, I am not surprised, PRP3 and LLRP4 use exactly the same code

> could process one number in almost exactly the same time, about

> 66 sec on 2.4GHz P-4.

>

to do squarings, the only difference is that, for Proth deterministic

tests, LLR computes the base "a" for each number, although PRP3 sets

always "a" = 3, but all that is done outside the loops.

Regards,

Jean