Register FAQ Search Today's Posts Mark Forums Read

2015-08-13, 19:30   #34
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

10110010110002 Posts

Quote:
 Originally Posted by R.D. Silverman What is "trial factorization"? As for specific numbers, I like to avoid that sort.
Trial division

2015-08-13, 20:00   #35
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×32×569 Posts

Quote:
 Originally Posted by henryzz Trial division
Follow-up: what kind of specific numbers. Your answer makes a big difference to what I may answer.

2015-08-13, 20:30   #36
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

139310 Posts

Quote:
 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.

2015-08-13, 22:14   #37
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

23×5×11×13 Posts

Quote:
 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.

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

Last fiddled with by henryzz on 2015-08-13 at 22:24

2015-08-14, 09:46   #38
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×32×569 Posts

Quote:
 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.

2015-08-14, 10:14   #39
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

23·5·11·13 Posts

Quote:
 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.

Last fiddled with by henryzz on 2015-08-14 at 10:19

2015-08-14, 14:02   #40
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 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?

2015-08-14, 15:05   #41
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

23·5·11·13 Posts

Quote:
 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.

2015-08-14, 15:33   #42
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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.

 2015-08-14, 15:54 #43 chris2be8     Sep 2009 35428 Posts 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
2015-08-14, 18:08   #44
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

5×181 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Factoring 20 2014-11-19 01:08 rogue Factoring 32 2009-09-17 11:40 henryzz Factoring 6 2007-09-19 13:47 ixfd64 Factoring 1 2005-09-08 12:13 ixfd64 Factoring 1 2004-04-27 09:41

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

Fri Sep 18 20:38:46 UTC 2020 up 8 days, 17:49, 1 user, load averages: 2.10, 1.78, 1.81