Methods of calculating negative inverse of modulus
AssigneeSamsung Electronics Co., Ltd.
InventorsYoung-sik Kim, Mi-jung Noh, Kyoung-moon Ahn, Sun-soo Shin
Life of this patent
Estimating the term…
Abstract
Provided is a method of calculating a negative inverse of a modulus, wherein the negative inverse, which is an essential element in Montgomery multiplication, is quickly obtained. The method includes setting a modulus, defining P obtained by converting the modulus to a negative number, and defining S obtained by subtracting 1 from P, and calculating a negative inverse of the modulus by using P and S.
Claims12
A method of calculating a negative inverse of a modulus M0, the method comprising:
- setting a modulus M0;
- defining P obtained by converting the modulus M0 to a negative number, and defining S obtained by subtracting 1 from P;
- and
- calculating a negative inverse V0 of the modulus M0 by using P and S.
A method of calculating a negative inverse of a modulus, the method comprising:
- classifying a main modulus into L modulus groups, wherein L is an integer of at least 1;
- and
- sequentially calculating negative inverses of L modulus groups from a modulus group including an LSB of the main modulus through a modulus group including an MSB of the main modulus.
A computer program product for calculating a negative inverse of a modulus M0, comprising a computer readable storage medium having encoded thereon instructions that, when executed on a computer, cause the computer to:
- set a modulus M0;
- define P obtained by converting the modulus M0 to a negative number, and defining S obtained by subtracting 1 from P;
- and
- calculate a negative inverse V0 of the modulus M0 by using P and S.
A computer program product for calculating a negative inverse of a modulus, comprising a computer readable storage medium having encoded thereon instructions that, when executed on a computer, cause the computer to:
- classify a main modulus into L modulus groups, wherein L is an integer of at least 1;
- and
- sequentially calculate negative inverses of L modulus groups from a modulus group including an LSB of the main modulus through a modulus group including an MSB of the main modulus.
Dependencies are inferred from the claim text.