mersenneforum.org > Math On the final divisor test in APR-CL
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-08, 08:34 #1 wpolly     Sep 2002 Vienna, Austria 21910 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 6 2017-09-01 13:59 Jean PennĂ© Software 5 2011-02-10 06:35 fenderbender Math 5 2007-07-18 18:39 Crook Math 5 2005-11-16 15:58 ET_ Factoring 1 2004-10-08 03:34

All times are UTC. The time now is 05:26.

Mon Apr 19 05:26:20 UTC 2021 up 11 days, 7 mins, 0 users, load averages: 1.16, 1.54, 1.62