mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

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

21910 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
Reply

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 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

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.