Patent ID: 7206799

Claim:
A method for deriving a solution of “A×BmodN” during encryption or decryption, said method comprising: a first step of setting a maximum bit number where “1” is assigned in N as n, deriving 2 n+1 modN and setting a solution thereof as b; a second step of deriving A×B and setting a solution thereof as X; a third step of transferring XmodN to (X/2 n+1 ×b+Xmod2 n+1 )modN; a fourth step of transferring (X/2 n+1 ×b+Xmod2 n+1 )modN to (X·n/2 n+1 ×b+X·nmod2 n+1 )modN and repeating calculations of X·n/2 n+1 ×b+X·nmod2 n+1 until a bit length of X·n becomes n+1; a fifth step of deriving X·n−N and setting a derived result as the solution of “A×BmodN”; and a sixth step of using the solution during encrption of a plaintext message into an encrypted message or during decryption of an encrypted message into a plaintext message.