mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2009-07-06, 07:24   #1
script kiddie
 
script kiddie's Avatar
 
Jul 2009

29 Posts
Default 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!
script kiddie is offline   Reply With Quote
Old 2009-07-06, 07:25   #2
script kiddie
 
script kiddie's Avatar
 
Jul 2009

1D16 Posts
Default 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!
script kiddie is offline   Reply With Quote
Old 2009-07-06, 09:02   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by CodeX View Post
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.
10metreh is offline   Reply With Quote
Old 2009-07-06, 09:12   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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 <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
akruppa is offline   Reply With Quote
Old 2009-07-06, 09:35   #5
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
10metreh is offline   Reply With Quote
Old 2009-07-06, 13:16   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·859 Posts
Default

Quote:
Originally Posted by CodeX View Post
Hi
This code can factor 463 or 633 digit number? How long it takes?
Quote:
Originally Posted by akruppa View Post
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.
bsquared is offline   Reply With Quote
Old 2009-07-06, 14:00   #7
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

1001101100102 Posts
Default

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

Andi47 is offline   Reply With Quote
Old 2009-07-07, 05:08   #8
script kiddie
 
script kiddie's Avatar
 
Jul 2009

29 Posts
Default 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!
script kiddie is offline   Reply With Quote
Old 2009-07-07, 06:33   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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
henryzz is online now   Reply With Quote
Old 2009-07-07, 09:52   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Quote:
Originally Posted by CodeX View Post
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
akruppa is offline   Reply With Quote
Old 2009-07-07, 11:07   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring a 160 digit RSA key swistak Factoring 6 2010-11-17 23:49
How much digit in the M? Lorenzo Math 17 2010-08-26 16:54
Need a quick factoring for 21-digit number jasong Factoring 5 2007-11-19 17:49
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02
Factoring a 617-digit number? 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

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