20170919, 21:26  #1 
Aug 2006
3·1,987 Posts 
Checking that there are no prime factors up to x
Suppose that I have a number N and I want to verify that it has no prime factors less than x. What is the fastest practical method to do this? In my application N has around 100 to 1000 digits and x might be from 10^20 to 10^30.
At this size it's easy to convince yourself with ECM that there are no divisors but I'd like to prove this. I know Strassen's method [1] has complexity sqrt(x) or so which is much better than trial division, but is there a good implementation of this somewhere? I know Bostan, Gaudry, & Schost [2] and Costa & Harvey [3] have improvements, and I know using a decent remainder tree method [4] is a key part of a practical program, but has anyone turned these into code (even the basic version)?  [1] V. Strassen, Einige Resultate über Berechnungskomplexität, Jahresbericht der Deutschen MathematikerVereinigung, (1976/77), pp. 18. [2] A. Bostan, P. Gaudry, and É. Schost, Linear recurrences with polynomial coefficients and application to integer factorization and CartierManin operator, SIAM Journal on Computing 36:6 (2007), pp.17771806. [3] E. Costa and D. Harvey, Faster deterministic integer factorization, Mathematics of Computation 83 (2014), pp. 339345. arXiv:1201.2116 [math.NT] [4] D. J. Bernstein, Factoring into coprimes in essentially linear time, Journal of Algorithms 54 (2005), pp. 130. [5] Markus Hittmeir, Deterministic factorization of sums and differences of powers, arXiv:1512.06401 [math.NT]. 
20170920, 16:07  #2 
Sep 2009
2·991 Posts 
Look at http://mersenneforum.org/showthread....trassen&page=7 posts 7584. That's one way to do it that's available now.
Chris 
20170920, 16:38  #3 
Aug 2006
3·1,987 Posts 
Neat method! But it doesn't seem to work for me:
Code:
> ecm v pm1 2 1152921504606846975 < 9089.txt GMPECM 7.0.4dev [configured with MPIR 2.7.2, enableopenmp] [P1] Tuned for x86_64/corei7/params.h Input number is 1140192872...2567985537 (2645 digits) Using special division for factor of 2^90891 Error: cannot choose suitable P value for your stage 2 parameters. Try a shorter B2min,B2 interval. Please report internal errors at <ecmdiscuss@lists.gforge.inria.fr>. Last fiddled with by CRGreathouse on 20170920 at 17:48 
20170920, 16:50  #4  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
For all remaining p factors 9089(p1), (use 2p1 also) this gives a not that terrible hard task. 

20170920, 18:27  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
38A_{16} Posts 
I have a GMP implementation of a remainder tree method, which is significantly faster for large inputs than mpz_divisible_ui_p through successive primes. It was based on Jens K Andersen's clear writeup of "treesieve". I have no doubt his private implementation is more efficient.
Besides being limited to 64bits for 'x', it doesn't seem remotely fast enough for your task. I am interested in what you find. Faster trial division would be quite useful. 
20170920, 20:56  #6  
Aug 2006
3·1,987 Posts 
Quote:
Last fiddled with by CRGreathouse on 20170920 at 20:59 

20170920, 20:58  #7  
Aug 2006
1749_{16} Posts 
Quote:
Quote:


20170920, 22:20  #8  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
Just a real example: Code:
? factor(polcyclo(100,2)) %8 = [ 5 1] [ 101 1] [ 8101 1] [268501 1] (and here 5 doesn't break the rule, because it is a divisor of 2^41). Or do you think that we have only luck here?? 

20170921, 13:36  #9 
Aug 2006
3×1,987 Posts 
You're suggesting that I use trial division with numbers of the form 18178n + 1 (or of course a remainder tree using only those values, as I hinted in #6). That's my fallback if I don't find anything better, but I wanted to explore the P1 angle suggested by chris2be8 first.

20170921, 13:56  #10  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:


20170921, 14:10  #11  
Aug 2006
3·1,987 Posts 
Quote:
You mean that if the exponent is odd the divisors are 1 or 7 mod 8, and if it's 2 or 4 mod 8 I the divisors are 1 or 3 mod 8 (and of course I have an Aurifeuillian factorization)? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Round Off Checking and Sum (Inputs) Error Checking  Forceman  Software  2  20130130 17:32 
Prime factors of googolplex  10.  Arkadiusz  Factoring  6  20111210 15:16 
Are all factors prime?  kurtulmehtap  Math  4  20100902 19:51 
Speeding up double checking when first test returns "prime"  Unregistered  PrimeNet  16  20060228 02:00 
Double Checking Factors  eepiccolo  Software  6  20030310 05:01 