Accelerating Okamoto-Uchiyama public-key cryptosystem
In Eurocrypt'98, Okamoto and Uchiyama presented a public-key cryptosystem as secure as factoring n = p2q; in terms of decryption complexity, the scheme is basically equivalent to RSA and requires O(log3n) bit operations. The authors point out a slight morphological modification in the scheme's structure that lowers the decryption complexity to O(log2n) while preserving equivalence to factoring.