Factoring RSA-200

[Zurtex]

http://mathworld.wolfram.com/news/2005-05-10/rsa-200/

Damn, my record stands at factoring a semiprimes of about 95 digits lol.

 

[neurocomp2003]

damn they one the $100k prize? ah nvm only 30k

 

[gazzo]

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

 

[neurocomp2003]

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.

 

[Zurtex]

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

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

 

[saltydog]

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

I believe 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.

 

[Zurtex]

I believe 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.

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

$$(pq)^{\frac{1}{3}} < p < q$$

Also it is highly likely that:

$$\alpha p < q < \beta p \quad \text{where} \quad \alpha \approx 2 \, \, \text{and} \, \, \beta \approx 10$$

These are 2 properties I found highly useful to reduce chance of factorization, or at least when I studied factoring such numbers.

 

[saltydog]

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

$$(pq)^{\frac{1}{3}} < p < q$$

Also it is highly likely that:

$$\alpha p < q < \beta p \quad \text{where} \quad \alpha \approx 2 \, \, \text{and} \, \, \beta \approx 10$$

These are 2 properties I found highly useful to reduce chance of factorization, or at least when I studied factoring such numbers.

Very nice Zurtex. Think I'll check your properties out with RSA-200. Thanks.

 

[Zurtex]

Very nice Zurtex. Think I'll check your properties out with RSA-200. Thanks.

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.

 

[saltydog]

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

$$(pq)^{\frac{1}{3}} < p < q$$

Also it is highly likely that:

$$\alpha p < q < \beta p \quad \text{where} \quad \alpha \approx 2 \, \, \text{and} \, \, \beta \approx 10$$

These are 2 properties I found highly useful to reduce chance of factorization, or at least when I studied factoring such numbers.

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:

$$(pq)^{1/3}<p<q$$

Since:

$$q\approx 2.224p$$

The second relation is satisfied with $\alpha=2$ and $\beta=10$

 

[AntonVrba]

RSA200 is factored - a lot of number crunching

Let $${RSA200}=pq$$ p and q both primes
let p' and q' be the adjacent prime numbers
hence $${RSA200'}={p'}{q'}$$

The relevance of the achievement can be judged that it will take the algorithms as long again to factorise RSA200'

 

[aravindsomething]

how the rsa200 is written like this

how rsa200 is written 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

 

[TenaliRaman]

Some info on the relative time in terms of years here,
http://www.rsasecurity.com/rsalabs/node.asp?id=2879

Some info on the actual factorisation method implemented,
http://www.loria.fr/~zimmerma/records/rsa200

-- AI

 

[aravindsubramanian]

RSA200 is factoring using GNFS.Why not SNFS?