LLR / Gwnums version

[Cruelty]

So testing k*2^n-b for k=736320585 is not the optimal way to use LLR?

[Jean Penné]

Originally Posted by Cruelty

So testing k*2^n-b for k=736320585 is not the optimal way to use LLR?

If b != 1, LLR will do a PRP test...
If b == 1, LLR will do a proving test ; k being large, gwnum will work in generic mode in both cases, so you will not get the IBDWT performances, but I don't know if a faster program is presently available (try Openpfgw, but it also uses the gwnum code...).

Jean

[Citrix]

Jean,

which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21?

Citrix

[Jean Penné]

Originally Posted by Citrix

Jean,

which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21?

Citrix

It is rather more complicated... and it requires to give precisions about how the gwnum code proceeds to do multiplications modulo N = k*2^n+-b numbers (surely, George Woltman would do that better than me...).
1) The speed is determined by the FFT length necessary to process a number N of given bit length.
2) According to the k size, the gwnum code uses three different algorithms to do multiplications : pure IBDWT, Zero paded IBDWT, generic mode.
3) The pure IBDWT algorithm can only be used with k values from 1 to around 2^20 ; it is the most efficient, because it requires the smallest FFT length, and makes the modular reduction totally free. Nevertheless, the FFT length for a given size of N increases smoothly by a factor of 2 when k goes from 1 to 2^20, then, the Zero padded algorithm becomes the better.
4) The Zero padded IBDWT can be used for k values up to around 2^48, and the performances continue to decrease smoothly.
5) For higher k values, the generic mode is used, and the speed for given size of N is around three times smaller than the IBDWT one.

I hope this rather involved explanation will satisfy you.

Jean

[Citrix]

The smaller the k the faster it will be? Did I get it right?

Citrix

[Jean Penné]

Originally Posted by Citrix

The smaller the k the faster it will be? Did I get it right?

Citrix

Yes, for a given bit length of the number to test !

[Ken_g6]

I've been trying to find a generic top-5000 prime with LLR 4.62 recently. I chose Proth tests with n=409600, k increasing from 600 to 1000000, since 2^20 is 1048576.

But around k=65487, running on a P4 2.8GHz non-hyperthreaded, I noticed that LLR said I was using a zero-padded FFT. Which according to the thread above shouldn't happen, right?

Looking through the log, there seems to have been a big jump in time taken between 60000 and 62000. While I can't completely rule out other processes for this jump, considering the size of the k, that zero-padded message is weird.