RSA Weak?

Alexander W. Janssen yalla at
Fri Nov 2 21:35:36 CET 2007

On 11/2/07, Sven Radde <email at> wrote:
> As mentioned above, the difficulty does not scale exponentially: The
> 663-bit number took 55 CPU-years on a 2,2GHz Opteron, the 640-bit number
>  30 CPU-years. The actual computations were apparrently carried out by a
> cluster with 80 machines.
> In fact, some mathematician has proven that factoring is a polynomial
> problem, IIRC.

A P-problem? Really?! Factoring primes is a polynomal problem nowadays?
Are you SURE about that?

Or do you just mean that the current development in CPU-power
compensates the exponential nature to a linear one (in history)
because CPU-power became cheap and parallelization became more common,
reducing the complexity a bit? (although you can't reduce exponential
complexity to linear or even polynomal just *as is*)

That'd put RSA into deep trouble. And not only RSA.


I'm just realizing that I missed a lot in the last years. Must watch
the development more closely...

> cu, Sven


"I am tired of all this sort of thing called science here... We have spent
millions in that sort of thing for the last few years, and it is time it
should be stopped."
 -- Simon Cameron, U.S. Senator, on the Smithsonian Institution, 1901.


More information about the Gnupg-users mailing list