System and method to optimize generation of coprime numbers in cryptographic applications

A method comprising:

• receiving a ciphertext that comprises a message encrypted with a public key associated with a key pair comprising the public key and a private key;
• identifying, by a processing device, a first set of mutually coprime numbers;
• obtaining, by the processing device, a second set of input numbers associated with the private key of the key pair, wherein each of the second set of input numbers is quadratic non-residue modulo a corresponding one of the first set of mutually coprime numbers;
• obtaining an output number, wherein the output number is a weighted sum of the second set of input numbers, each of the second set of input numbers taken with a weight comprising a square of a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers;
• using, by the processing device, the output number to generate a prime number;
• obtaining, by the processing device, the private key using the output number;
• and
• decrypting, by the processing device, the message using the ciphertext and the private key.

A system to perform a cryptographic operation, the system comprising:

• a memory device;
• and
• a processing device communicatively coupled to the memory device, the processing device to:
• receive a ciphertext that comprises a message encrypted with a public key associated with a key pair comprising the public key and a private key;
• identify a first set of mutually coprime numbers;
• obtain a second set of input numbers associated with the private key of the key pair, wherein each of the second set of input numbers is coprime with a corresponding one of the first set of mutually coprime numbers;
• obtain an output number, wherein the output number is a weighted sum of the second set of input numbers, each of the second set of input numbers taken with a weight comprising a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers;
• obtain the private key using the output number;
• and
• decrypt the message using the ciphertext and the private key.