Re: RSA encryption/decryption

From: Pubkeybreaker (Robert_silverman_at_raytheon.com)
Date: 09/19/05 

Date: 19 Sep 2005 11:00:18 -0700

"Was I've said is one bit means about 2 times the work, or less with a
better algorithm, but still somewhat close to that.
So factoring a 4096 bit number takes 2^(4096-512) times [the time to
factor a 512 bit number]. "

Bzzt. False. Please go study before making further cretinous
pronouncements.

4096 bits takes about L(2^4096)/L(2^512) times as much work,
where
L(n) = exp( (c +o(1)) ( (log n)^1/3 (loglog n)^2/3)) and c ~ 1.9
is the time
complexity function for NFS.

4096 bits is about 3.4 x 10^27 times as hard as 512 bits, not
2^3584 ~ 7.8 x 10^1078 times as hard.

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: Factoring program
    ... > I have read with much interest your posts, and now I know a bit more how NFS ... they are incapable of factoring integers anywhere near the bleeding ... Even if we provided you with a complete set of executables, ... which we are interested --- SNFS on around 200 to 300 digit ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)