Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2019-04-08, 08:34   #1
wpolly's Avatar
Sep 2002
Vienna, Austria

3338 Posts
Default 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?
wpolly is offline   Reply With Quote

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

All times are UTC. The time now is 01:57.

Sat Oct 16 01:57:05 UTC 2021 up 84 days, 20:26, 0 users, load averages: 0.57, 0.85, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.