US2013198253A1PendingUtilityA1
Methods of calculating negative inverse of modulus
Est. expiryDec 2, 2028(~2.3 yrs left)· nominal 20-yr term from priority
G06F 7/721G06F 7/728G06F 7/52G06F 9/4494G06F 7/72
50
PatentIndex Score
0
Cited by
0
References
0
Claims
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.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1 . A method of calculating a negative inverse of a modulus M 0 , the method comprising:
setting a modulus M 0 ; defining P obtained by converting the modulus M 0 to a negative number, and defining S obtained by subtracting 1 from P; and calculating a negative inverse V 0 of the modulus M 0 by using P and S, wherein the calculating of the negative inverse comprises:
dividing S by 2;
assigning a value of a least significant bit (LSB) of S divided by 2 as a value of the LSB that is not determined among the bits forming the negative inverse V 0 of the modulus M 0 ; and
replacing S by a value obtained by adding a value obtained by dividing S by 2 to a value obtained by multiplying P by the value of the LSB of the divided S,
wherein the setting, defining, and calculating steps are performed by at least one processor.
2 . The method of claim 1 , wherein k bits are equally assigned to the modulus M 0 and the negative inverse V 0 of the modulus M 0 , wherein k is equal to or below a number of bits assigned to the entire modulus.
3 . The method of claim 2 , wherein in the calculating of the negative inverse V 0 , a least significant bit (LSB) of the negative inverse V 0 through a most significant bit (MSB) of the negative inverse V 0 are sequentially calculated.
4 . The method of claim 1 , further comprising repeating the dividing, the assigning, and the replacing until the MSB of the negative inverse V 0 of the modulus M 0 is obtained.
5 . The method of claim 1 , wherein when M 0 =(m k-1 , m k-2 , . . . , m 1 , 1) 2 , k is an integer, and
V
0
=
-
1
M
0
mod
2
k
=
(
v
k
-
1
,
v
k
-
2
,
…
,
v
1
,
1
)
2
,
wherein M 0 is the modulus, V 0 is the negative inverse of the modulus, and k is 8,
v 0 =1
v 1 =1− m 1
v 2 =1− m 2
C 3 +v 3b =m 3 +m 2 +m 1
C 4 +v 4b =m 4 +m 3 +C 3
C 5 +v 5b =m 5 +m 4 +m 3 +m 1 +C 4
C 6 +v 6b =m 6 +m 5 +m 4 +m 2 +m 3 +m 2 +m 3 m 1 +m 2 m 1 +C 5
v 7b =m 7 +m 6 +m 5 +m 4 +m 3 m 2 m 1 +( m 4 +m 3 +1)( m 2 +m 1 )+ C 6 .
6 . The method of claim 1 , further comprising storing the negative inverse V 0 of the modulus M 0 in a memory device.
7 . 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, comprising:
defining P obtained by converting each of the L modulus groups into a negative number, and defining S obtained by subtracting 1 from P; and
calculating a negative inverse of each of the L modulus groups by using P and S;
wherein the calculating of the negative inverse comprises:
dividing S by 2;
assigning a value of the LSB of S divided by 2 as a value of the LSB that is not determined among the bits forming a negative inverse of each of the L modulus groups; and
replacing S by a value obtained by adding a value obtained by dividing S by 2 to a value obtained by multiplying P by the value of the LSB of the divided S,
wherein the classifying and sequentially calculating steps are performed by at least one processor.
8 . The method of claim 7 , wherein in the calculating, the LSB of the negative inverse of each of the L modulus groups through the MSB of the negative inverse of each of the L modulus groups are sequentially calculated.
9 . A computer program product for calculating a negative inverse of a modulus M 0 , comprising a non-transitory computer readable storage medium having encoded thereon instructions that, when executed on a computer, cause the computer to:
set a modulus M 0 ; define P obtained by converting the modulus M 0 to a negative number, and defining S obtained by subtracting 1 from P; and calculate a negative inverse V 0 of the modulus M 0 by using P and S, wherein the calculating of the negative inverse comprises:
dividing S by 2;
assigning a value of the LSB of S divided by 2 as a value of the LSB that is not determined among the bits forming the negative inverse V 0 of the modulus M 0 ; and
replacing S by a value obtained by adding a value obtained by dividing S by 2 to a value obtained by multiplying P by the value of the LSB of the divided S.
10 . An apparatus for generating a negative inverse V of a modulus M, the apparatus comprising:
a calculator configured to calculate a negative inverse V 0 of a modulus M 0 ; and a processor configured to read the modulus M 0 and input the modulus M 0 into the calculator; wherein when M 0 =(m k-1 , m k-2 , . . . , m 1 , 1) 2 , k is an integer, and
V
0
=
-
1
M
0
mod
2
k
=
(
v
k
-
1
,
v
k
-
2
,
…
,
v
1
,
1
)
2
,
wherein M 0 is the modulus, V 0 is the negative inverse of the modulus, and k is 8,
v 0 =1
v 1 =1− m 1
v 2 =1− m 2
C 3 +v 3b =m 3 +m 2 +m 1
C 4 +v 4b =m 4 +m 3 +C 3
C 5 +v 5b =m 5 +m 4 +m 3 +m 1 +C 4
C 6 +v 6b =m 6 +m 5 +m 4 +m 2 +m 3 m 2 +m 3 m 1 +m 2 m 1 +C 5
v 7b =m 7 +m 6 +m 5 +m 4 +m 3 m 2 m 1 +( m 4 +m 3 +1)( m 2 +m 1 )+ C 6 .
11 . The apparatus of claim 10 , wherein the processor classifies the modulus M into L modulus groups and inputs each of the L modulus groups into the calculator sequentially, and
wherein L is an integer of at least 1.
12 . The apparatus of claim 11 , wherein the calculator calculates a negative inverse of one of the L modulus groups while the processor reads another of the L modulus groups simultaneously.Join the waitlist — get patent alerts
Track US2013198253A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.