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

Using LLR with big k's
[QUOTE=Cruelty]So testing k*2^nb for k=736320585 is not the optimal way to use LLR?[/QUOTE]
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 
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 
[QUOTE=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[/QUOTE] 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 
The smaller the k the faster it will be? Did I get it right?
Citrix 
[QUOTE=Citrix]The smaller the k the faster it will be? Did I get it right?
Citrix[/QUOTE] Yes, for a given bit length of the number to test ! 
I've been trying to find a generic top5000 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 nonhyperthreaded, I noticed that LLR said I was using a zeropadded FFT. Which according to the thread above shouldn't happen, right? :surrender 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 zeropadded message is weird. :question: 
All times are UTC. The time now is 09:03. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.