mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-06-09, 12:57   #1
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

11010011112 Posts
Talking 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
ValerieVonck is offline   Reply With Quote
Old 2005-06-09, 13:24   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

746410 Posts
Thumbs down

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
of about 220.

Is there some point to this exercise????
R.D. Silverman is offline   Reply With Quote
Old 2005-06-09, 14:50   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

262458 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-06-09, 15:07   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101001010002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-06-09, 15:44   #5
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

7·112 Posts
Default

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
ValerieVonck is offline   Reply With Quote
Old 2005-06-09, 16:44   #6
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2005-06-09, 17:07   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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/
akruppa is offline   Reply With Quote
Old 2005-06-09, 17:25   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-06-09, 18:35   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

2DDB16 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-06-09, 18:47   #10
VJS
 
VJS's Avatar
 
Dec 2004

1001010112 Posts
Default

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.
VJS is offline   Reply With Quote
Old 2005-06-09, 18:48   #11
VJS
 
VJS's Avatar
 
Dec 2004

13×23 Posts
Default

Also why don't you have a look at this site...

http://www.frenchfries.net/paul/factoring/theory/
VJS is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Challenge on the net devarajkandadai Miscellaneous Math 0 2012-05-31 05:17
When I was your age.....CHALLENGE petrw1 Lounge 14 2009-11-23 02:18
Challenge science_man_88 Miscellaneous Math 229 2009-09-07 08:08
Another challenge R.D. Silverman Programming 24 2005-07-27 21:08
Who is Challenge? 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

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”