mersenneforum.org rsa-640 challenge
 Register FAQ Search Today's Posts Mark Forums Read

 2005-06-09, 12:57 #1 ValerieVonck     Mar 2004 Belgium 11010011112 Posts rsa-640 challenge Hi everyone! This is a code snippet of the program I have written in hope to crack this number: Code:  BigInteger p = new BigInteger(SIZE, 10, new Random()); // BigInteger q = new BigInteger(SIZE, 10, new Random()); // BigInteger N = p.multiply(q); BigInteger z = challenge_number.remainder(p); if (z.equals(new String("0"))) { System.out.println(p); BigInteger q = challenge_number.divide(p); System.out.println(q); First question, is the logic above correct? if challenge_number modulo random number == 0 then random number is a factor Second Question: For the SIZE, I set this equal to 320. Is this correct? Because the challenge number itself is a mere 193 bits long? Wich SIZE should I choose? Third question: Is it possible to use this Java Class in a distributed approach? Fourth question: Can I make other optimisations to the code? (better checks on the numbers)? Thnx & Regards, Cedric Last fiddled with by ValerieVonck on 2005-06-09 at 12:57
2005-06-09, 13:24   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746410 Posts

Quote:
 Originally Posted by CedricVonck Hi everyone! This is a code snippet of the program I have written in hope to crack this number: Code:  BigInteger p = new BigInteger(SIZE, 10, new Random()); // BigInteger q = new BigInteger(SIZE, 10, new Random()); // BigInteger N = p.multiply(q); BigInteger z = challenge_number.remainder(p); if (z.equals(new String("0"))) { System.out.println(p); BigInteger q = challenge_number.divide(p); System.out.println(q); First question, is the logic above correct? if challenge_number modulo random number == 0 then random number is a factor Second Question: For the SIZE, I set this equal to 320. Is this correct? Because the challenge number itself is a mere 193 bits long? Wich SIZE should I choose? Third question: Is it possible to use this Java Class in a distributed approach? Fourth question: Can I make other optimisations to the code? (better checks on the numbers)? Thnx & Regards, Cedric

Among all the ways of trying to crack RSA-640, you have chosen one of
the worst. You will NEVER succeed in breaking it using trial division by
random integers.

The number itself is 640 bits. The factors are 320 bits. There are
approximately 10^94 primes less than 2^320. How long do you think
it will take you to try them? If you do trial division by all odd numbers,
rather than just primes, the number of trial divisors increases by a factor

Is there some point to this exercise????

2005-06-09, 14:50   #3
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

262458 Posts

Quote:
 Originally Posted by R.D. Silverman Is there some point to this exercise????
I think the point is to see whether anyone will answer the questions as asked.

The approach is correct (from a quick glance at the code), it can be distributed over many machines and it can most certainly be optimized. For instance, we know that both factors of RSA-640 have the same number of bits and both are odd, so we should ensure that (by an extremely rapid single-bit setting operation) before embarking on a relatively expensive division. I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320.

There is one minor error in the interpretation of the challenge but not in the proposed method of solution. RSA-640 is only 193 digits long but it is 640 bits.

OTOH, Bob is correct in pointing out that the approach is essentially useless in practice.

Paul

2005-06-09, 15:07   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001010002 Posts

Quote:
 Originally Posted by xilman I think the point is to see whether anyone will answer the questions as asked. The approach is correct (from a quick glance at the code), it can be distributed over many machines and it can most certainly be optimized. For instance, we know that both factors of RSA-640 have the same number of bits and both are odd, so we should ensure that (by an extremely rapid single-bit setting operation) before embarking on a relatively expensive division. I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320. There is one minor error in the interpretation of the challenge but not in the proposed method of solution. RSA-640 is only 193 digits long but it is 640 bits. OTOH, Bob is correct in pointing out that the approach is essentially useless in practice. Paul
Allow me to also point out that once one has done about 10^48 such
trial divisions, one will start to repeat divisions already done. (i.e.
get collisions). The number of such collisions rises rapidly as the algorithm
progresses until almost all divisions performed are repeats of earlier divisions.
There are (2^320 - 2^319)/2 odd 320 bit numbers. (~ 5 x 10^95)
Even if you do this number of divisions, you will miss out on testing
about 1/e ~ 36% of the numbers.

2005-06-09, 15:44   #5
ValerieVonck

Mar 2004
Belgium

7·112 Posts

Quote:
 Originally Posted by R.D. Silverman The number itself is 640 bits. The factors are 320 bits. There are approximately 10^94 primes less than 2^320. How long do you think it will take you to try them? If you do trial division by all odd numbers, rather than just primes, the number of trial divisors increases by a factor of about 220. Is there some point to this exercise????
Imho, yes

1) See that I can program a "decent" java program
2)

I'm assuming, possibly incorrectly, that the library routine generates a random number < 2^320.

You assumed incorrectly. Random(SIZE,10,new Random()) generates an unique random number based on the timestamp (wich it takes as seed) with a certaintity of 100% that the number will of SIZE n (or n +/- 1)

3) What I have noticed when I generating factors, Java spits out only Integers that end in 1,3,7,9 ( I think also 5)

BTW, BigInteger is a Java class found in the (default) Math Package:
import java.lang.Math; (probably not needed (the import)).

Mr Silverman, maybe I am lucky in the first run, maybe never.. I will see

Regards & Tx.

Last fiddled with by ValerieVonck on 2005-06-09 at 15:45

 2005-06-09, 16:44 #6 grandpascorpion     Jan 2005 Transdniestr 503 Posts You can be virtually certain you won't find it in your lifetime. It's a big waste of electricity. You have a better chance of winning the lottery 5 times over.
 2005-06-09, 17:07 #7 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts CedricVonck, you will definitely never be lucky with a program like that. First off, what is the period of the Random() function? It is entirely possible that values start repeating after, say, 2^64 calls, so it is highly probable that the required divisor will not be among them. Second, please compute the cost of one trial division attempt (electricity and computer devaluation) and the average gain (prize money times probability per candidate divisor). How do they compare? How does this ratio compare to, say, playing the lottery? Alex Last fiddled with by akruppa on 2005-06-12 at 12:23 Reason: s/over/times/
2005-06-09, 17:25   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Quote:
 Originally Posted by CedricVonck Imho, yes You assumed incorrectly. Random(SIZE,10,new Random()) generates an unique random number based on the timestamp (wich it takes as seed) with a certaintity of 100% that the number will of SIZE n (or n +/- 1) Regards & Tx.
If you are simply learning Java, then go ahead. However, as a
computational exercise it is a total waste of time, your stubborn
refusal to accept this notwithstanding.

Why not do something that has a chance of succeeding? For example,
find integers a,b, x,y with x,y > 1 such that a^x - b^y = 6. or 14 or 50??
(there are no known solutions)

I assumed nothing incorrectly. Count the number of odd 320 bit integers.
I also suggest that you investigate both the period of the RNG, as well
as the *number of different seeds*. "Unique random number" is meaningless
gibberish. The seed will have some finite length. Given a clock resolution
of (say) 10^9/sec, and starting at 0, you have approximately 6 x 10^19
(2005 x 31 million sec/yr x 10^9) different seeds. This is a mere 76
orders of magnitude short of what you need.

I ask the more general audience:

(1) Why can't people do simple arithmetic?
(2) Why do people stubbornly persist with something that is unlikely to
succeed in the lifetime of the universe? Especially when an expert suggests
simple alternatives with far greater chance of success.

You are beginning to sound like a crank, Mr. Vonck.

 2005-06-09, 18:35 #9 ewmayer ∂2ω=0     Sep 2002 República de California 2DDB16 Posts Baby steps, baby steps... Cedric, why don't you try factoring a really small number using your code first? Say this one, which is roughly one-tenth the size: 46346456565690422177 Tell us how long your code takes for that. Then, once you're warmed up, try these: 128-bit: 100932962400917909775165520235579282579 192-bit: 1269978474870826099469200719269667649673577514427443201007 256-bit: 57947655096138611771015791829549915741168624880634687983385128259250717742871 320-bit: 332510945314407585369353816108066418700825249657921338102510381124554301151561291698818402774601 Once you've finished the 320-bit composite, we can talk about optimizing your Java applet to tackle the 640-bit.
 2005-06-09, 18:47 #10 VJS     Dec 2004 1001010112 Posts Well I wouldn't be so hard on CedricVonck, People do things not nessarily b/c they understand them, especially when it comes to us internet geeks and number theory. People do things especially DC, b/c they don't understand and both hope to learn something in the process and get the warm fuzzy feelings. Silverman you have to understand that this isn't anyones job nor does solving a mathematical theory help them in their daily lives. Question for you: what % of people participating in Math projects do you think ... Understand the mod function? How about taken an into number theory course? do multi-variable calc? Single Variable calc? Lets go even further and say "define composite"? I do agree with you however that the RSA challenges are a waste of computing power. Most of these challenges can be solved with simple stats. I.e. It would take x computers y years to compute z itterations with program ??? to crack the key. Who really cares what the two factors are in the long run, but this could be said about alot of the projects we are doing. CedricVonck, really, don't start please. I'd also agree with akruppa, if you simply shut off the machine instead of running RSA you would "win" more money. Now if someone spent their time working on a code or ??? which would complete the RSA-640 in <1 month on one machine. That would be something, not by luck but 100% postive solution within a month. Cedric you have a ways to go with your code according to the experts here.
 2005-06-09, 18:48 #11 VJS     Dec 2004 13×23 Posts Also why don't you have a look at this site... http://www.frenchfries.net/paul/factoring/theory/

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Miscellaneous Math 0 2012-05-31 05:17 petrw1 Lounge 14 2009-11-23 02:18 science_man_88 Miscellaneous Math 229 2009-09-07 08:08 R.D. Silverman Programming 24 2005-07-27 21:08 JuanTutors PrimeNet 2 2004-07-22 12:56

All times are UTC. The time now is 16:00.

Wed Aug 17 16:00:16 UTC 2022 up 41 days, 10:47, 1 user, load averages: 1.65, 1.59, 1.50