Checking that there are no prime factors up to x - Page 2

R. Gerbicz · 2017-09-21, 14:40

Quote:

Originally Posted by CRGreathouse

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

But for general numbers the mentioned remainder tree is faster.

Quote:

Originally Posted by CRGreathouse

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

The first part is good, the 2nd is false, it is even fail on the super small n=4. That is what I follow in general conjectures, we don't need to check thousand/million digits examples when in the first n value the test is totally broken.
I've written this:

Code:

And you can go further: if n=4*k+2, then for all remaining factors p==1 or 3 mod 8. (notice the difference in the condition).

And in this case there is no Aurifeuillian factorization.

rcv · 2017-09-21, 15:53

Much of what is being discussed in this thread (and the other thread) mirror the same discussions and pros/cons as for potential Mersenne primes (2^n-1, where n is prime.)

You haven't really made it clear whether you are also concerned about x^n-1, where x != 2. Or whether you are interested in numbers of the form x^n+1.

You might search for Chris Caldwell's prime pages and some of the proofs on his pages for some ideas that may also be applicable for non-prime values of n. (Especially odd values of n.)

Trial Factoring for the GIMPS project has asked (and answered) most of your questions for the case where x=2 and n is prime. Prime95 and the GPU-to-72 project have had several discussions in these fora. In particular, there are several threads in the Math forum that discuss these issues, especially near the inception of the GPU-to-72 project. (I know I contributed a few remarks related to sieving (in the context of trial factoring) in about 2011 or 2012.)

In fact, the math is so similar, you might be able to adapt some of the existing trial factoring programs for your purpose. Good luck!

There are also some faster algorithms, compared against old-fashioned long-division, to perform trial factoring. You mentioned dividing out the known factors. But, it might be faster to keep the unfactored dividend. (I.e., keep it as a string of binary 1's.)

Finally, this forum's own ewmayer has a recent paper, titled "Efficient long division via Montgomery multiply". The paper discusses some new algorithms and includes some references that are relevant to the questions you have been asking. Good luck!

CRGreathouse · 2017-09-21, 18:02

Quote:

Originally Posted by rcv

You haven't really made it clear whether you are also concerned about x^n-1, where x != 2. Or whether you are interested in numbers of the form x^n+1.

I'm most interested in general numbers rather than any of these special forms. The particular problem I'm working with deals with numbers of the form 2^n - 1 where n is composite and coprime to 2310, but the general case comes up often enough I'd like to deal with it properly (hence splitting this thread out separately from the other).

Quote:

Originally Posted by rcv

You might search for Chris Caldwell's prime pages and some of the proofs on his pages for some ideas that may also be applicable for non-prime values of n. (Especially odd values of n.)

Trial Factoring for the GIMPS project has asked (and answered) most of your questions for the case where x=2 and n is prime.

Insofar as I'm pursuing the special case my exponents are odd and composite.

Quote:

Originally Posted by rcv

Finally, this forum's own ewmayer has a recent paper, titled "Efficient long division via Montgomery multiply". The paper discusses some new algorithms and includes some references that are relevant to the questions you have been asking.

I'll look it up, thanks.

chris2be8 · 2017-09-22, 16:00

Quote:

Originally Posted by chris2be8

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

Chris

And post 73 http://mersenneforum.org/showpost.ph...6&postcount=73 refers to: "arbooker's Pollard-Strassen app".

Chris

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

2017-09-21, 15:53	#13
rcv Dec 2011 11×13 Posts	Much of what is being discussed in this thread (and the other thread) mirror the same discussions and pros/cons as for potential Mersenne primes (2^n-1, where n is prime.) You haven't really made it clear whether you are also concerned about x^n-1, where x != 2. Or whether you are interested in numbers of the form x^n+1. You might search for Chris Caldwell's prime pages and some of the proofs on his pages for some ideas that may also be applicable for non-prime values of n. (Especially odd values of n.) Trial Factoring for the GIMPS project has asked (and answered) most of your questions for the case where x=2 and n is prime. Prime95 and the GPU-to-72 project have had several discussions in these fora. In particular, there are several threads in the Math forum that discuss these issues, especially near the inception of the GPU-to-72 project. (I know I contributed a few remarks related to sieving (in the context of trial factoring) in about 2011 or 2012.) In fact, the math is so similar, you might be able to adapt some of the existing trial factoring programs for your purpose. Good luck! There are also some faster algorithms, compared against old-fashioned long-division, to perform trial factoring. You mentioned dividing out the known factors. But, it might be faster to keep the unfactored dividend. (I.e., keep it as a string of binary 1's.) Finally, this forum's own ewmayer has a recent paper, titled "Efficient long division via Montgomery multiply". The paper discusses some new algorithms and includes some references that are relevant to the questions you have been asking. Good luck!