2019-04-08, 08:34 | #1 |
Sep 2002
Vienna, Austria
219_{10} Posts |
On the final divisor test in APR-CL
So I'm planning to run an hybrid N-1/APRCL test on a 21k digit PRP (specifically, Phi(32481,10) where N-1 has been factored to ~20%). I have several question regarding the choice of parameters and the implementation of the final trial-division step, where we look for divisors of N congruent to N^i (mod s) for i=2,3,...,t.
1. Asymptotically, going with s>N^{1/3} with Lenstra "divisors in residue class" gains a factor of O((log log N)^C) in the number of tests needed, but loses a factor of O(log N) in the cost of each divisor test, both compared to the usual approach of s>N^{1/2} and simple division; thus it is never a good idea. Is this observation correct? 2. It appears that the size of the modulus (roughly N^{1/2}, ~500 64-bit limbs or 10000 digits) is well below the GMP Toom8/FFT crossover point (MUL_FFT_THRESHOLD is usually 3000-6000 limbs). In this regime, would gwnum "generic mod" multiplication (the modulus s does not have any k*b^n+-c form) be faster than GMP? 3. Do I need to compile the gwnum library from scratch, or would a PFGW script suffice for this task without much loss of performance? |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Probability that N is prime given each divisor of N has the form 2*k*p+1 | carpetpool | Miscellaneous Math | 6 | 2017-09-01 13:59 |
LLR final 3.8.4 Version is available! | Jean PennĂ© | Software | 5 | 2011-02-10 06:35 |
Small prime test divisor efficiency strategy | fenderbender | Math | 5 | 2007-07-18 18:39 |
Relation between divisor functions | Crook | Math | 5 | 2005-11-16 15:58 |
New Fermat number divisor! | ET_ | Factoring | 1 | 2004-10-08 03:34 |