System and method for performing operation using linear-integer-programing for RSA factorization

A system for reducing computer processing time during private key decryption during digital communication, the system performing operations using linear integer programming for RSA factorization, comprising:

• an n/e extractor configured to extract a modulus and a public key exponent from a public key;
• a prime factorization calculator electrically coupled with the n/e extractor and configured to:
• determine a semi-prime number of the modulus according to the modulus;
• use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, wherein the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number;
• and
• a private key determiner electrically coupled with the prime factorization calculator and configured to determine a private key using the public key exponent and the two prime numbers;
• and
• a decryptor electrically coupled with the private key determiner and configured to decrypt an encrypted message using the private key, so as to generate a decrypted message;
• wherein the prime factorization calculator is further configured to determine if the semi-prime number is in a form of 4k+1, k being a positive integer, wherein the decomposition and factorization is performed via the first mode as the semi-prime number is in the form of 4k+1, and the decomposition and factorization is performed via the third mode as the semi-prime number is not in the form of 4k+1;
• wherein the prime factorization calculator performs the decomposition by creating subproblems that are structured as linear integer programming problems, using the tail digit and the head digit set of the semi-prime number as decimal digit information, and performs the factorization by solving corresponding linear binary programs derived from the decomposition, such that, during execution of the private key decryption on a computer, the system solves the subproblems using linear integer programming techniques to reduce computer processing time and power consumption.