# RSA-200 Factored

1. May 10, 2005

### Zurtex

Last edited: May 10, 2005
2. May 10, 2005

### neurocomp2003

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

3. May 10, 2005

### gazzo

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

4. May 10, 2005

### 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.

5. May 10, 2005

### Zurtex

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

6. May 10, 2005

### saltydog

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.

7. May 10, 2005

### Zurtex

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.

8. May 10, 2005

### saltydog

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

9. May 10, 2005

### Zurtex

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.

10. May 10, 2005

### saltydog

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$

11. May 14, 2005

### 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'

12. Jul 11, 2005

### aravindsomething

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

13. Jul 11, 2005

### TenaliRaman

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

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

-- AI

Last edited by a moderator: May 2, 2017
14. Jul 12, 2005

### aravindsubramanian

RSA200 is factoring using GNFS.Why not SNFS?