 mersenneforum.org Factoring 463 digit
 Register FAQ Search Today's Posts Mark Forums Read  2009-07-06, 07:24 #1 script kiddie   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!   2009-07-06, 07:25 #2 script kiddie   Jul 2009 1D16 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!   2009-07-06, 09:02   #3
10metreh

Nov 2008

2·33·43 Posts Quote:
 Originally Posted by CodeX 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!
Are you using GMP-ECM? If not, do so. It has many more options than programs like the one you are using. BTW, what exactly is it?

This code cannot factor a 463 digit number unless it has small factors. You currently seem to be searching for 40-digit 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.   2009-07-06, 09:12 #4 akruppa   "Nancy" Aug 2002 Alexandria 1001101000112 Posts GMP-ECM 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 2009-07-06, 09:35   #5
10metreh

Nov 2008

2·33·43 Posts Quote:
 Originally Posted by akruppa 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.
His username makes it even more likely that this is the case.   2009-07-06, 13:16   #6
bsquared

"Ben"
Feb 2007

22·859 Posts Quote:
 Originally Posted by CodeX Hi This code can factor 463 or 633 digit number? How long it takes?
Quote:
 Originally Posted by akruppa 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
633 digits is 2101 bits... not a common RSA key size, but of course even more impossible if it is a hard number.   2009-07-06, 14:00   #7
Andi47

Oct 2004
Austria

1001101100102 Posts Quote:
 Originally Posted by bsquared 633 digits is 2101 bits... not a common RSA key size, but of course even more impossible if it is a hard number.
Hmmmm....

1.) Run an umptillion curves at B1 = 1 gadzillion, B2 = 100 gadzillions.
2.) check back in 10^14 years to collect the factors.     2009-07-07, 05:08 #8 script kiddie   Jul 2009 29 Posts Why Impossible? I'm using GMP-ECM 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 4-5 hours with same program... What's wrong if I make it 463? Thanks from now!   2009-07-07, 06:33   #9
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts Quote:
 Originally Posted by Andi47 Hmmmm.... 1.) Run an umptillion curves at B1 = 1 gadzillion, B2 = 100 gadzillions. 2.) check back in 10^14 years to collect the factors.  i think that you will find that the max possible ecm b1 value is 9007199254740996 with gmp ecm
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 2009-07-07 at 06:34   2009-07-07, 09:52   #10
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts Quote:
 Originally Posted by CodeX It's really impossible to find them?
With current algorithms and technology: yes.

Quote:
 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?
Estimate roughly how long that would take if you could test one factor per nanosecond.

Quote:
 Why you all say it's impossible? I was able to factor 120 digit factor in 4-5 hours with same program... What's wrong if I make it 463? Thanks from now!
Because a 231 digit factor is 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than a 60 digit factor. Ok, decent factoring algorithms aren't in Θ(p); with ECM it's "only" about 28888111056731212816 times harder to find (ignoring the cost of arithmetic), but still quite impossible.

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 GMP-ECM takes to factor it 10 times over. Plot the result.

Alex   2009-07-07, 11:07   #11
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Because a 231 digit factor is 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than a 60 digit factor.
No, it is not. It is (231/60) times larger. SIZE (for complexity purposes)
is measured by the number of bits or number of digits.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post swistak Factoring 6 2010-11-17 23:49 Lorenzo Math 17 2010-08-26 16:54 jasong Factoring 5 2007-11-19 17:49 AntonVrba Factoring 7 2005-12-06 22:02 Shakaru Factoring 2 2005-02-23 19:22

All times are UTC. The time now is 09:07.

Mon May 10 09:07:22 UTC 2021 up 32 days, 3:48, 0 users, load averages: 1.68, 2.11, 2.03