N. Ferguson (Microsoft), "Fast RSA signature verification," United States Patent 2008/0148055A1, Jun. 19, 2008.
Abstract: An RSA message signature can be verified by verifying that s.sup.e mod n=F(m, n). If a value K, defined as K=s.sup.e div n is computed in advance and provided as an input to the computing device verifying the signature, the signature verification can be significantly faster. To avoid transmission of, and mathematical operations on, large values of K, which can themselves be inefficient, the RSA public exponent e can be selected to be relatively small, such as e=2 or e=3. K is based on publicly available information and can be calculated by the computing device signing the message, or by an intermediate computing device, and transmitted to the device verifying the signature without impacting security.
Exemplary Claim: One or more computer-readable media comprising computer-executable instructions for verifying a signature, the computer-executable instructions directed to steps comprising:receiving a signed message comprising message data and the signature, the signed message having been signed using a private key comprising a modulo value, the private key being paired with a public key comprising a public exponent and the modulo value;receiving a pre-computed value corresponding to a quotient of the signature raised by the public exponent then divided by the modulo value; andusing the pre-computed value to verify the signature.