20090706, 07:24  #1 
Jul 2009
29 Posts 
Factoring 463 digit
Hi
I have a 463 digit number and I want to factor it. I tried factor program which uses ecm and gmp. I tried factor program for smaller numbers to make sure it works... I worked! But now it's about a month I added 463 digit number but still I get something like this in factor.out.temp: Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=560460763 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=3555363627 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=2272258386 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=4260360504 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=2239415231 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=1010251361 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=3266493755 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=1921213857 Sometimes I see Step 1 took 384628ms And I see this also: Performing trial division to 577790542997741824 What does it means? It's working? This code can factor 463 or 633 digit number? How long it takes? And I have another question I have a computer with 8 CPUs. How can I make this factor program to use all 8 CPUs... Now it uses only one of them... Please advice! Thank you so much! 
20090706, 07:25  #2 
Jul 2009
1D_{16} Posts 
Factoring 463 digit
Hi
I have a 463 digit number and I want to factor it. I tried factor program which uses ecm and gmp. I tried factor program for smaller numbers to make sure it works... I worked! But now it's about a month I added 463 digit number but still I get something like this in factor.out.temp: Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=560460763 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=3555363627 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=2272258386 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=4260360504 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=2239415231 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=1010251361 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=3266493755 Using B1=3000000, B2=5299038372, polynomial Dickson(6), sigma=1921213857 Sometimes I see Step 1 took 384628ms And I see this also: Performing trial division to 577790542997741824 What does it means? It's working? This code can factor 463 or 633 digit number? How long it takes? And I have another question I have a computer with 8 CPUs. How can I make this factor program to use all 8 CPUs... Now it uses only one of them... Please advice! Thank you so much! 
20090706, 09:02  #3  
Nov 2008
2·3^{3}·43 Posts 
Quote:
This code cannot factor a 463 digit number unless it has small factors. You currently seem to be searching for 40digit factors. Finding a 232 digit factor is IMPOSSIBLE with current hardware. What is the number you are trying to factor? Why are you trying to factor it? If it is random, it is a waste of time. If you want to factor some "fairly random" numbers, have a look in here. To use all 8 cores, just start 8 instances of the program. This should work, but I am not a multicore expert. 

20090706, 09:12  #4 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
GMPECM uses the Elliptic Curve Method which is a probabilistic algorithm. It randomly tries different "curves" and finds a factor when the curve satisfies certain conditions (its order is has no prime factor >B1, except maybe for one >B1 but <B2). The probability that this happens drops rapidly with the size of the factor. Factors up to 50 digits can be found in reasonable time, up to 60 digits if you're determined or you get lucky, and larger than 60 if you're both determined and lucky. No one has ever found a factor greater than 70 digits with ECM so far.
Your number has 463 digits, so it's entirely possible that it has only prime factors greater than 70 (or even 200!) digits. In that case you simply won't find them in reasonable time with ECM. The number is too large for general factoring algorithms like NFS, too. If it's some "random" number, you can try ECM a while more and hope you get lucky. Use increasing B1 as listed in http://www.loria.fr/~zimmerma/records/ecm/params.html: do 2440 curves at B1=3000000, then 4590 at B1=11000000, then 7771 at B1=44000000 etc until you get either lucky or bored. To run the program on several cpus, simply run it several times in parallel: each program will try different curves. If you are trying to crack a 1536 bit RSA key which would have, surprise, 463 digits: simply not possible. That's why they are being used. Alex 
20090706, 09:35  #5 
Nov 2008
2·3^{3}·43 Posts 

20090706, 13:16  #6  
"Ben"
Feb 2007
2^{2}·859 Posts 
Quote:


20090706, 14:00  #7 
Oct 2004
Austria
100110110010_{2} Posts 

20090707, 05:08  #8 
Jul 2009
29 Posts 
Why Impossible?
I'm using GMPECM with factor program I got from this forum.
Why you say it's impossible? I know this number have 2 prime factors in range of about 231 or 232 digits. It's really impossible to find them? We can't go from 231 or 232 digit to end of 232 digits? like.. 1000000..........0 to 99999999.........9 to see if it's divisible by 463 digit number and if it's prime... Is it possible? Why you all say it's impossible? I was able to factor 120 digit factor in 45 hours with same program... What's wrong if I make it 463? Thanks from now! 
20090707, 06:33  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
Quote:
i am not aware of there being a limit to b2 except that after you get really high it cant set good parameters for the huge search space that b2 problem could be got around by using a save file Last fiddled with by henryzz on 20090707 at 06:34 

20090707, 09:52  #10  
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
With current algorithms and technology: yes.
Quote:
Quote:
Exercise: construct 20 numbers each of 100 digits. Each number should have two prime factors: one number with a prime factor of 20 digits, one number with a prime factor of with 21 digits, etc, up to 39 digits. For each number, measure the total time GMPECM takes to factor it 10 times over. Plot the result. Alex 

20090707, 11:07  #11  
Nov 2003
1110100100100_{2} Posts 
Quote:
is measured by the number of bits or number of digits. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring a 160 digit RSA key  swistak  Factoring  6  20101117 23:49 
How much digit in the M?  Lorenzo  Math  17  20100826 16:54 
Need a quick factoring for 21digit number  jasong  Factoring  5  20071119 17:49 
160 digit factor found of 366 digit (PRP1)  AntonVrba  Factoring  7  20051206 22:02 
Factoring a 617digit number?  Shakaru  Factoring  2  20050223 19:22 