Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Is factorization of big primeproducts a solved problem YET?
Replies: 19   Last Post: Jan 30, 2013 5:05 AM

 Messages: [ Previous | Next ]
 Pubkeybreaker Posts: 1,683 Registered: 2/12/07
Re: Is factorization of big primeproducts a solved problem YET?
Posted: Jan 8, 2013 10:22 AM

On Jan 8, 8:46 am, mstem...@walkabout.empros.com (Michael Stemper)
wrote:
> In article <kc6gg1\$au...@dont-email.me>, David Bernier <david...@videotron.ca> writes:
> >On 01/04/2013 12:01 AM, JT wrote:
> >> Does the RSA challenges have a given time complexity of factoring the
> >> primeproduct, or did they have one that  changed during resent years?

>
> >The RSA challenge numbers are still available somewhere.
> >The contests for prize money has been discontinued.

>
> >I think many remain unfactored, as far as the general
> >public knows, i.e. outside cryptologic agencies and
> >government cipher schools.

>
> >They would deliberately choose n = p*q, p, q odd primes
> >with the digit length of p and q being about half that
> >of the composite number `n'.

>

> I'm surpised. I would have expected them to pick p and q with significantly
> different lengths. Doesn't a simplistic attack like Fermat's method get
> much easier when p and q are close in magnitude?
>

I suggest that you compute the effort needed for a Fermat attack for N
= pq,
N is 1024 bits, and p and q are identical in (say) the first 3
digits.

Date Subject Author
1/4/13 JT
1/4/13 David Bernier
1/8/13 Michael Stemper
1/8/13 Pubkeybreaker
1/10/13 Phil Carmody
1/10/13 Pubkeybreaker
1/10/13 Richard Tobin
1/11/13 Pubkeybreaker
1/11/13 Phil Carmody
1/11/13 Phil Carmody
1/11/13 Phil Carmody
1/4/13 Pubkeybreaker
1/4/13 JT
1/4/13 Pubkeybreaker
1/4/13 amzoti
1/4/13 Pubkeybreaker
1/4/13 amzoti
1/10/13 Graham Cooper
1/11/13 David Bernier
1/30/13 Rosario1903