A method to break rsa cryptosystem by factoring very large integers in near real time.

摘要

The invention is related to decrypting data encrypted by the RSA or RSA-like public-key cryptosystem without the knowledge of the private key required for decrypting the encrypted messages. At present, a generic method to decrypt encrypted messages without the private key is not possible due to the difficulty of factoring very large unknown integers on present day computers. This invention makes it possible to factor any unknown integer, large or small, of varying types and hence, also to decide the primality of an integer (whether a number is prime or not) in polynomial time proportional to the, number of digits in the base-4 representation of the number to be factorized.