In 2010 I generated two RSA keys (and certs) of size above 100000 bits: [Full-disclosure] nonsense fun: 100 000 bit rsa key http://archives.neohapsis.com/archives/fulldisclosure/2010-08/0384.html The keys/certs: http://archives.neohapsis.com/archives/fulldisclosure/2010-08/att-0384/gir.t... (the certs might have expired but this doesn't matter). The private keys are included too. According to my mail they were generated in "about 30 hours on 1 core" and I used state of the art primality checking "pfgw". n is the size of the modulus in bits. Assume the much loved NSA has factoring algorithms of complexity O(n^6) or O(n^12) running on classical computers. Can the NSA break n=100000 without using owning/torture? Some computations suggest NO, especially for the second: sage: k=100000 sage: RR(k^6).log(2) 99.6578428466209 sage: RR(k^12).log(2) 199.315685693242 Comments about quantum computer that can break them are welcome too.