# Factoring RSA-200: A Wolfram MathWorld Record

• Zurtex
In summary, Zurtex has achieved a record in factoring semiprimes with a time of only 3 months. The factors of the semiprimes were found with the help of the Lucas-Lehmer test and other properties of the numbers.
damn they one the \$100k prize? ah nvm only 30k

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

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.

gazzo said:
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

gazzo said:
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.

saltydog said:
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.

Zurtex said:
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.

saltydog said:
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.

Zurtex said:
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$

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'

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

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

Last edited by a moderator:
RSA200 is factoring using GNFS.Why not SNFS?

## 1. What is RSA-200 and why is it important?

RSA-200 is a number with 200 decimal digits that is the product of two large prime numbers. It is important because it is used as a benchmark for testing the efficiency of factoring algorithms, which are crucial for cryptography and data security.

## 2. How long did it take to factor RSA-200?

The factoring of RSA-200 was accomplished in 17 days using a combination of distributed computing and specialized factoring algorithms.

## 3. Who was involved in factoring RSA-200?

The factoring of RSA-200 was a collaborative effort involving mathematicians and computer scientists from various institutions, including the University of Bonn, the University of California Berkeley, and the University of Michigan.

## 4. What was the previous record for factoring large numbers?

The previous record for factoring large numbers was the factoring of RSA-180, which had 180 decimal digits and was achieved in 1999 using the Number Field Sieve algorithm.

## 5. Why is the factoring of RSA-200 considered a significant achievement?

The factoring of RSA-200 is considered a significant achievement because it demonstrates the continuous progress in factoring algorithms and highlights the importance of constantly updating and improving methods for securing data and information.

Replies
13
Views
3K
Replies
5
Views
2K
Replies
4
Views
6K
Replies
1
Views
11K
Replies
10
Views
5K
Replies
37
Views
3K
Replies
1
Views
2K
Replies
12
Views
3K
Replies
1
Views
5K
Replies
18
Views
3K