3 ms·
It is funny, but AFAIK there is no established lower bound on the complexity of factoring problem. Even in the realm of classic computation. Anecdotally - Ron R
by dchichkov 14y ago
It is funny, but AFAIK there is no established lower bound on the complexity of factoring problem. Even in the realm of classic computation. Anecdotally - Ron Rivest estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years. RSA-129 was solved in 1994. RSA-768 in 2009.