mersenneforum.org > Math Checking that there are no prime factors up to x
 Register FAQ Search Today's Posts Mark Forums Read

 2017-09-19, 21:26 #1 CRGreathouse     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 Mathematiker-Vereinigung, (1976/77), pp. 1-8. [2] A. Bostan, P. Gaudry, and É. Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM Journal on Computing 36:6 (2007), pp.1777-1806. [3] E. Costa and D. Harvey, Faster deterministic integer factorization, Mathematics of Computation 83 (2014), pp. 339-345. arXiv:1201.2116 [math.NT] [4] D. J. Bernstein, Factoring into coprimes in essentially linear time, Journal of Algorithms 54 (2005), pp. 1-30. [5] Markus Hittmeir, Deterministic factorization of sums and differences of powers, arXiv:1512.06401 [math.NT].
 2017-09-20, 16:07 #2 chris2be8     Sep 2009 2·991 Posts Look at http://mersenneforum.org/showthread....trassen&page=7 posts 75-84. That's one way to do it that's available now. Chris
 2017-09-20, 16:38 #3 CRGreathouse     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 GMP-ECM 7.0.4-dev [configured with MPIR 2.7.2, --enable-openmp] [P-1] Tuned for x86_64/corei7/params.h Input number is 1140192872...2567985537 (2645 digits) Using special division for factor of 2^9089-1 Error: cannot choose suitable P value for your stage 2 parameters. Try a shorter B2min,B2 interval. Please report internal errors at . The number I gave it was the C2645 cofactor of 2^9089 - 1, in an attempt to prove that 2305843009213693951 is the least prime factor of 2^9089 - 1. Last fiddled with by CRGreathouse on 2017-09-20 at 17:48
2017-09-20, 16:50   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts

Quote:
 Originally Posted by CRGreathouse Neat method! But it doesn't seem to work for me: Code: > ecm -v -pm1 2 1152921504606846975 < 9089.txt GMP-ECM 7.0.4-dev [configured with MPIR 2.7.2, --enable-openmp] [P-1] Tuned for x86_64/corei7/params.h Input number is 1140192872...2567985537 (2645 digits) Using special division for factor of 2^9089-1 Error: cannot choose suitable P value for your stage 2 parameters. Try a shorter B2min,B2 interval. Please report internal errors at . The number I gave it was the C2645 cofactor of 2^9089 - 1, in an attempt to prove that 2305843009213693951 is its least prime factor.
For all remaining p factors 9089|(p-1), (use 2|p-1 also) this gives a not that terrible hard task.

 2017-09-20, 18:27 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38A16 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 64-bits 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.
2017-09-20, 20:56   #6
CRGreathouse

Aug 2006

3·1,987 Posts

Quote:
 Originally Posted by danaj 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 64-bits for 'x', it doesn't seem remotely fast enough for your task.
How long does it take to check the full 64-bit range? Is it flexible enough to check only numbers/primes of a given form?

Last fiddled with by CRGreathouse on 2017-09-20 at 20:59

2017-09-20, 20:58   #7
CRGreathouse

Aug 2006

174916 Posts

Quote:
 Originally Posted by R. Gerbicz Don't you read your other forum? For all remaining p factors 9089|(p-1), (use 2|p-1 also) this gives a not that terrible hard task.
I guess I didn't understand. I was trying to follow arbooker's instructions here:

Quote:
 Originally Posted by arbooker Once you know the value of P from above, this is straightforward to do with the -go option. Here are the steps that need to be performed: 1) Run Code: ecm -v -pm1 2 B2 < number with your favorite value of B2. 2) Interrupt it and take note of the P value. 3) Run Code: ecm -pm1 -go '(2*P)^100' 2 B2 < number replacing P by the actual number from step 2. Also, 100 can be replaced by any number at least floor(log(B2)/log(2)). If gmp-ecm reports no factors then the number is guaranteed to have no prime factors below 2*B2. Note that this is not the same as saying that it will necessarily find all such prime factors, since there is still the (remote) chance that it will find multiple factors and be unable to separate them.

2017-09-20, 22:20   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts

Quote:
 Originally Posted by CRGreathouse I guess I didn't understand. I was trying to follow arbooker's instructions here:
Don't know what is your background, but this is still elementary math.
Just a real example:
Code:
? factor(polcyclo(100,2))
%8 =
[     5 1]

[   101 1]

[  8101 1]

[268501 1]
It is very clear that for all prime factors 100 | p-1
(and here 5 doesn't break the rule, because it is a divisor of 2^4-1).
Or do you think that we have only luck here??

 2017-09-21, 13:36 #9 CRGreathouse     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 P-1 angle suggested by chris2be8 first.
2017-09-21, 13:56   #10
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts

Quote:
 Originally Posted by CRGreathouse 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 P-1 angle suggested by chris2be8 first.
I'd use powermod, as for Mersenne numbers. It is amazing that how amateur people finds the slowest methods. Also check out your other thread to save an additional factor of two.

2017-09-21, 14:10   #11
CRGreathouse

Aug 2006

3·1,987 Posts

Quote:
 Originally Posted by R. Gerbicz I'd use powermod, as for Mersenne numbers. It is amazing that how amateur people finds the slowest methods.
Yes, when I did this with some other numbers (where I didn't have to search so far) I used powermod, it's definitely better than a literal division (especially when one operand is a bignum).

Quote:
 Originally Posted by R. Gerbicz Also check out your other thread to save an additional factor of two.
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)?

 Similar Threads Thread Thread Starter Forum Replies Last Post Forceman Software 2 2013-01-30 17:32 Arkadiusz Factoring 6 2011-12-10 15:16 kurtulmehtap Math 4 2010-09-02 19:51 Unregistered PrimeNet 16 2006-02-28 02:00 eepiccolo Software 6 2003-03-10 05:01

All times are UTC. The time now is 10:54.

Sat Jan 23 10:54:14 UTC 2021 up 51 days, 7:05, 0 users, load averages: 2.47, 1.81, 1.67