20050609, 12:57  #1 
Mar 2004
Belgium
1101001111_{2} Posts 
rsa640 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); 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 20050609 at 12:57 
20050609, 13:24  #2  
"Bob Silverman"
Nov 2003
North of Boston
7464_{10} Posts 
Quote:
Among all the ways of trying to crack RSA640, 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 of about 220. Is there some point to this exercise???? 

20050609, 14:50  #3  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
26245_{8} Posts 
Quote:
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 RSA640 have the same number of bits and both are odd, so we should ensure that (by an extremely rapid singlebit 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. RSA640 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 

20050609, 15:07  #4  
"Bob Silverman"
Nov 2003
North of Boston
1110100101000_{2} Posts 
Quote:
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. 

20050609, 15:44  #5  
Mar 2004
Belgium
7·11^{2} Posts 
Quote:
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 20050609 at 15:45 

20050609, 16:44  #6 
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.

20050609, 17:07  #7 
"Nancy"
Aug 2002
Alexandria
4643_{8} 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 20050612 at 12:23 Reason: s/over/times/ 
20050609, 17:25  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
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. 

20050609, 18:35  #9 
∂^{2}ω=0
Sep 2002
Repรบblica de California
2DDB_{16} 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 onetenth the size: 46346456565690422177 Tell us how long your code takes for that. Then, once you're warmed up, try these: 128bit: 100932962400917909775165520235579282579 192bit: 1269978474870826099469200719269667649673577514427443201007 256bit: 57947655096138611771015791829549915741168624880634687983385128259250717742871 320bit: 332510945314407585369353816108066418700825249657921338102510381124554301151561291698818402774601 Once you've finished the 320bit composite, we can talk about optimizing your Java applet to tackle the 640bit. 
20050609, 18:47  #10 
Dec 2004
100101011_{2} 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 multivariable 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 RSA640 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. 
20050609, 18:48  #11 
Dec 2004
13×23 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Challenge on the net  devarajkandadai  Miscellaneous Math  0  20120531 05:17 
When I was your age.....CHALLENGE  petrw1  Lounge  14  20091123 02:18 
Challenge  science_man_88  Miscellaneous Math  229  20090907 08:08 
Another challenge  R.D. Silverman  Programming  24  20050727 21:08 
Who is Challenge?  JuanTutors  PrimeNet  2  20040722 12:56 