mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-09-19, 21:26   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,987 Posts
Default 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].
CRGreathouse is online now   Reply With Quote
Old 2017-09-20, 16:07   #2
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·32·5·11 Posts
Default

Look at http://mersenneforum.org/showthread....trassen&page=7 posts 75-84. That's one way to do it that's available now.

Chris
chris2be8 is offline   Reply With Quote
Old 2017-09-20, 16:38   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

174916 Posts
Default

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 <ecm-discuss@lists.gforge.inria.fr>.
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
CRGreathouse is online now   Reply With Quote
Old 2017-09-20, 16:50   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101100101012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 <ecm-discuss@lists.gforge.inria.fr>.
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.
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-09-20, 18:27   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-09-20, 20:56   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,987 Posts
Default

Quote:
Originally Posted by danaj View Post
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
CRGreathouse is online now   Reply With Quote
Old 2017-09-20, 20:58   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,987 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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 View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2017-09-20, 22:20   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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??
R. Gerbicz is offline   Reply With Quote
Old 2017-09-21, 13:36   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,987 Posts
Default

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.
CRGreathouse is online now   Reply With Quote
Old 2017-09-21, 13:56   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-09-21, 14:10   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

596110 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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 View Post
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)?
CRGreathouse is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Round Off Checking and Sum (Inputs) Error Checking Forceman Software 2 2013-01-30 17:32
Prime factors of googolplex - 10. Arkadiusz Factoring 6 2011-12-10 15:16
Are all factors prime? kurtulmehtap Math 4 2010-09-02 19:51
Speeding up double checking when first test returns "prime" Unregistered PrimeNet 16 2006-02-28 02:00
Double Checking Factors eepiccolo Software 6 2003-03-10 05:01

All times are UTC. The time now is 17:38.

Thu Jan 21 17:38:41 UTC 2021 up 49 days, 13:50, 0 users, load averages: 1.97, 1.98, 2.21

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.