- #1

- 1,120

- 1

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

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

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

Last edited:

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Zurtex
- Start date

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.

- #1

- 1,120

- 1

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

Last edited:

Physics news on Phys.org

- #2

neurocomp2003

- 1,366

- 4

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

- #3

gazzo

- 175

- 0

How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

What makes them so much harder? :S

- #4

neurocomp2003

- 1,366

- 4

- #5

- 1,120

- 1

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.htmlgazzo said:How much different are these to factoring mersenne numbers?

What makes them so much harder? :S

- #6

saltydog

Science Advisor

Homework Helper

- 1,591

- 3

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.

- #7

- 1,120

- 1

The factors p and q will have the probably have the properties: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.

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

- #8

saltydog

Science Advisor

Homework Helper

- 1,591

- 3

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

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

- #9

- 1,120

- 1

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 said:Very nice Zurtex. Think I'll check your properties out with RSA-200. Thanks.

- #10

saltydog

Science Advisor

Homework Helper

- 1,591

- 3

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

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]

- #11

AntonVrba

- 92

- 0

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'

- #12

aravindsomething

- 1

- 0

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

- #13

TenaliRaman

- 644

- 1

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

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:

- #14

aravindsubramanian

- 23

- 0

RSA200 is factoring using GNFS.Why not SNFS?

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.

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

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.

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.

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
- 1

- Views
- 11K

- Replies
- 10

- Views
- 5K

- Replies
- 37

- Views
- 3K

- Replies
- 1

- Views
- 2K

- Replies
- 12

- Views
- 3K

- Replies
- 18

- Views
- 3K

Share: