mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-08-13, 19:30   #34
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

163C16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What is "trial factorization"?

As for specific numbers, I like to avoid that sort.
Trial division
henryzz is offline   Reply With Quote
Old 2015-08-13, 20:00   #35
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

24·5·127 Posts
Default

Quote:
Originally Posted by henryzz View Post
Trial division
Follow-up: what kind of specific numbers. Your answer makes a big difference to what I may answer.
xilman is online now   Reply With Quote
Old 2015-08-13, 20:30   #36
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101010110102 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2015-08-13, 22:14   #37
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

22·1,423 Posts
Default

Quote:
Originally Posted by xilman View Post
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

Last fiddled with by henryzz on 2015-08-13 at 22:24
henryzz is offline   Reply With Quote
Old 2015-08-14, 09:46   #38
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

1016010 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
xilman is online now   Reply With Quote
Old 2015-08-14, 10:14   #39
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

22×1,423 Posts
Default

Quote:
Originally Posted by xilman View Post
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

Last fiddled with by henryzz on 2015-08-14 at 10:19
henryzz is offline   Reply With Quote
Old 2015-08-14, 14:02   #40
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by henryzz View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2015-08-14, 15:05   #41
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

22×1,423 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
henryzz is offline   Reply With Quote
Old 2015-08-14, 15:33   #42
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-08-14, 15:54   #43
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·3·5·31 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2015-08-14, 18:08   #44
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to Factoring Projects rogue Factoring 20 2014-11-19 01:08
Links to Factoring Programs rogue Factoring 32 2009-09-17 11:40
factoring programs henryzz Factoring 6 2007-09-19 13:47
looking for Fermat factoring programs ixfd64 Factoring 1 2005-09-08 12:13
any good GNFS factoring programs? ixfd64 Factoring 1 2004-04-27 09:41

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

Wed Aug 5 20:03:12 UTC 2020 up 19 days, 15:49, 2 users, load averages: 1.89, 1.62, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.