Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

RSA-200 Factored

  1. May 10, 2005 #1

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Last edited: May 10, 2005
  2. jcsd
  3. May 10, 2005 #2
    damn they one the $100k prize? ah nvm only 30k
     
  4. May 10, 2005 #3
    How much different are these to factoring mersenne numbers?

    What makes them so much harder? :S
     
  5. May 10, 2005 #4
    well considering one of the prizes took was it either 2weeks or 3 months to solve...they are pretty intense, because the selected prime numbers are suppose to be "randomly" chosen to try to avoid patterns or classifications like the mersenne numbers.
     
  6. May 10, 2005 #5

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    You can factor Mersenne numbers from the formulae alone assume the exponent isn't prime. Also there is a specific test for testing the primality of Mersenne numbers: http://mathworld.wolfram.com/Lucas-LehmerTest.html
     
  7. May 10, 2005 #6

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    I belive also they're chosen to be as far apart as possible. Correct me if I'm wrong, but the closer they are together, the easier (relatively speaking), it is to factor the composite.
     
  8. May 10, 2005 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    The factors p and q will have the probably have the properties:

    [tex](pq)^{\frac{1}{3}} < p < q[/tex]

    Also it is highly likely that:

    [tex]\alpha p < q < \beta p \quad \text{where} \quad \alpha \approx 2 \, \, \text{and} \, \, \beta \approx 10[/tex]

    These are 2 properties I found highly useful to reduce chance of factorization, or at least when I studied factoring such numbers.
     
  9. May 10, 2005 #8

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    Very nice Zurtex. Think I'll check your properties out with RSA-200. Thanks.
     
  10. May 10, 2005 #9

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Well actually for large numbers the 2nd one implies the 1st one and a lot stronger conditions, however the 1st one is more logically important, the 2nd one makes sense when you try and think about how people might attack it. You will see that my inequalities hold for RSA-200.
     
  11. May 10, 2005 #10

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    Ok, I checked RSA-200 against these criteria. First I verified that I copied the numbers into Mathematica correctly by checking the difference of n-pq which was zero.

    The first relation is satisfied:

    [tex](pq)^{1/3}<p<q[/tex]

    Since:

    [tex]q\approx 2.224p[/tex]

    The second relation is satisfied with [itex]\alpha=2[/itex] and [itex]\beta=10[/itex]
     
  12. May 14, 2005 #11
    RSA200 is factored - a lot of number crunching

    Let [tex]{RSA200}=pq[/tex] p and q both primes
    let p' and q' be the adjacent prime numbers
    hence [tex]{RSA200'}={p'}{q'}[/tex]

    The relevance of the achievement can be judged that it will take the algorithms as long again to factorise RSA200'
     
  13. Jul 11, 2005 #12
    how the rsa200 is writen like this

    how rsa200 is writen in this way

    The RSA200 number is, by the way, 27,997,833,911,221,327,870,829,467,638,722,601,621,070,446,786,
    955,428,537,560,009,929,326,128,400,107,609,345,671,052,955,
    360,856,061,822,351,910,951,365,788,637,105,954,482,006, 576,775,098,580,557,613,579,098,734,950,144,178,863,178,946,295,
    187,237,869,221,823,983.

    source

    http://news.com.com/2061-10789_3-5702146.html
     
  14. Jul 11, 2005 #13
  15. Jul 12, 2005 #14
    RSA200 is factoring using GNFS.Why not SNFS?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: RSA-200 Factored
  1. RSA help please (Replies: 3)

Loading...