Links to factoring programs

[henryzz]

Originally Posted by R.D. Silverman

What is "trial factorization"?

As for specific numbers, I like to avoid that sort.

Trial division

[xilman]

Originally Posted by henryzz

Trial division

Follow-up: what kind of specific numbers. Your answer makes a big difference to what I may answer.

[R. Gerbicz]

Originally Posted by henryzz

Trial division

http://cr.yp.to/papers/sf.pdf
If you have non-special numbers then see section 6.
If you have lots of numbers then see section 7, I had a direct implementation of this in gmp.

[henryzz]

Originally Posted by xilman

Follow-up: what kind of specific numbers. Your answer makes a big difference to what I may answer.

The numbers I was thinking of are encountered as roadblocks in the odd perfect number factorization tree. This means that they are 100-2000 digits. This tree relies on knowing that the roadblocks are trial factored upto a certain level. There could be multiple numbers that can be factored together, however, I would love to be able to factor numbers separately as well.


The paper Robert linked to made a valid point about ecm being potentially faster.
Could a similar study be done with fixed curves/bounds of ecm be done similar to https://miller-rabin.appspot.com/ finding small sets of curves that will find all factors < y. For what size y would this become faster than trial division?
With B1=1e4 B2=1e4 it seems to take only ~8-9 curves to find all the factors of 1000000#/2

[xilman]

Originally Posted by henryzz

The numbers I was thinking of are encountered as roadblocks in the odd perfect number factorization tree. This means that they are 100-2000 digits. This tree relies on knowing that the roadblocks are trial factored upto a certain level. There could be multiple numbers that can be factored together, however, I would love to be able to factor numbers separately as well.


The paper Robert linked to made a valid point about ecm being potentially faster.
Could a similar study be done with fixed curves/bounds of ecm be done similar to https://miller-rabin.appspot.com/ finding small sets of curves that will find all factors < y. For what size y would this become faster than trial division?
With B1=1e4 B2=1e4 it seems to take only ~8-9 curves to find all the factors of 1000000#/2

I'm missing something. A 100-digit number can be completely factored with ease by at least two different methods other than TF. Given a complete factorization, why is it necessary to know that trial division has been performed up to a known limit?

More productively: if you can prove that all factors must have a specific algebraic form, as do factors of Mersenne numbers for instance, that can surely be exploited to speed up trial division. Another simple, but still only linear speed-up, is to use a wheel of a size which fits a SIMD machine such as a GPU. Note that phi(11#) = 480 which may well match a GPU quite well.

[henryzz]

Originally Posted by xilman

I'm missing something. A 100-digit number can be completely factored with ease by at least two different methods other than TF. Given a complete factorization, why is it necessary to know that trial division has been performed up to a known limit?

More productively: if you can prove that all factors must have a specific algebraic form, as do factors of Mersenne numbers for instance, that can surely be exploited to speed up trial division. Another simple, but still only linear speed-up, is to use a wheel of a size which fits a SIMD machine such as a GPU. Note that phi(11#) = 480 which may well match a GPU quite well.

100 was a mistake. Assume that the number is large enough to be out of range of nfs.

In addition to methods I was looking for code programs. This seems a bit of a hole in the available programs.

Something like the method starting at the bottom of page 159 could be interesting. The problem being finding the small quadratic residues.
https://books.google.com/books?id=4-...0gauss&f=false

[R.D. Silverman]

Originally Posted by henryzz

100 was a mistake. Assume that the number is large enough to be out of range of nfs.

In addition to methods I was looking for code programs. This seems a bit of a hole in the available programs.

Pari works quite well. So do Maple and Mathematica.

Of course you might actually learn something by writing one for yourself. GMP is readily available
for the arithmetic. Trial division is simple.

Or are you just too lazy?

[henryzz]

Originally Posted by R.D. Silverman

Pari works quite well. So do Maple and Mathematica.

Of course you might actually learn something by writing one for yourself. GMP is readily available
for the arithmetic. Trial division is simple.

Or are you just too lazy?

I have coded several factorization methods such as SIQS and primality tests such as ECPP.
However, I don't have the time or experience to fully optimise them.
My aim really is to fully understand the methods.
I am hoping that someone has already worked on a version that is well optimized. Maybe later I will go back and create my own version.

[R.D. Silverman]

Originally Posted by henryzz

I have coded several factorization methods such as SIQS and primality tests such as ECPP.
However, I don't have the time or experience to fully optimise them.
My aim really is to fully understand the methods.
I am hoping that someone has already worked on a version that is well optimized. Maybe later I will go back and create my own version.

??

Trial division is simple. And the optimizations are mostly done for you via GMP.

[chris2be8]

Odd perfect related roadblocks are of the form (p^q-1)/(p-1) where p and q are odd primes.

I assume you are looking for a way to prove a given roadblock has no factors below a certain bound. I can remember a discussion where I suggested running P-1 with B1=1e6 and B2=1e12 should find all factors below 1e12. Someone (possibly Batalov) said that could miss factors where P-1 has a prime power greater than B1 and gave a way to get round that. But I can't remember when it was or find it by searching the forum. I hope this jogs someone's memory.

Chris

[danaj]

Originally Posted by henryzz

I have coded several factorization methods such as SIQS and primality tests such as ECPP.
However, I don't have the time or experience to fully optimise them.
My aim really is to fully understand the methods.
I am hoping that someone has already worked on a version that is well optimized. Maybe later I will go back and create my own version.

The code here: Math-Prime-Util-GMP contains various factoring and primality tests, including ECPP. The P-1 and ECM are faster in some cases than GMP-ECM, but not for deep factoring. The QS is very rudimentary, being a cleanup and speedup of William Hart's SIMPQS version 1. The ECPP is much faster than the old GMP-ECPP project, and faster than Primo for very small inputs (under 500 digits), but Primo leaves it in the dust at larger sizes. Using Enge's GNU CM would open up a lot of options.