US5499299A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Modular arithmetic operation system
Assignee: Fujitsu Ltd
•
Filing: 1994-06-30
•
Granted: 1996-03-12
•
Expires: 2014-06-30
Abstract
Abstract A modular arithmetic unit comprises an input register, a multiple computing section, an adder, and a correcting section. There is provided a multiple table in which multiples of a modulo N are stored to correspond with low-order some bits of an input number T in the input register. The low-order some bits of the input number T are used to look up its corresponding multiple of the modulo N in the multiple table. The adder adds the multiple of the modulo N retrieved from the multiple table and the contents of the input register. This addition is performed n times. The contents of the input register are updated with high-order predetermined bits of the sum in the adder each time addition is performed in the adder. The correcting section makes a correction on the result t of addition by the adder after n additions have been performed.
Inventors
- 👤 Masahiko Takenaka
- 👤 Naoya Torii
- 👤 Takayuki Hasebe
- 👤 Ryota Akiyama
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 19:43
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/728; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; H04L2209/00; H04L2209/12
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
135 words
A modular arithmetic unit comprising: an input register for holding an input number; multiple computing means for obtaining a multiple of a modulus corresponding to a low-order predetermined bits of said input number in said input register by table lookup using a table in which arithmetic data have been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times; and correcting means for making a correction on the result of addition by said adder means.
Claim 2
Dependent Claim
135 words
A modular arithmetic unit comprising: an input register for holding an input number; multiple computing means for obtaining a multiple of a modulus corresponding to a low-order predetermined bits of said input number in said input register by table lookup using a table in which arithmetic data have been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times; and correcting means for making a correction on the result of addition by said adder means.
Claim 3
Dependent Claim
59 words
The arithmetic unit according to claim 1, in which said multiple computing means has a multiple table in which multiples of said modulus are stored to correspond with said low-order predetermined bits of said input number, said low-order predetermined bits of said input number being used to directly retrieve a corresponding multiple of said modulus from said multiple table.
Claim 4
Dependent Claim
102 words
The arithmetic unit according to claim 1, in which said multiple computing means comprises multiple information computing means for using said low-order predetermined bits of said input number to retrieve the corresponding multiple information from a multiple information table in which multiple information is stored to correspond to low-order predetermined bits of said input number, a modulo register for storing a modulus, and a multiplier means for multiplying said multiple information obtained by said multiple information computing means and said modulus from said modulo register, thereby obtaining a multiple of said modulus corresponding to said low-order predetermined bits of said input number.
Claim 5
Dependent Claim
89 words
A table setup device comprising: repeated addition means for adding a modulus to itself repeatedly; complement computing means for computing the two's complement of low-order k bits of each sum obtained by said repeated addition means; and table writing means for writing each sum into a table address corresponding the two's complement of that sum obtained by said complement computing means, thereby setting up on a storage device a multiple table in which multiples of said modulus are stored to correspond with low-order predetermined bits of an input number.
Claim 6
Dependent Claim
89 words
A table setup device comprising: repeated addition means for adding a modulus to itself repeatedly; complement computing means for computing the two's complement of low-order k bits of each sum obtained by said repeated addition means; and table writing means for writing each sum into a table address corresponding the two's complement of that sum obtained by said complement computing means, thereby setting up on a storage device a multiple table in which multiples of said modulus are stored to correspond with low-order predetermined bits of an input number.
Claim 7
Dependent Claim
173 words
The device according to claim 4, in which said multiple table is used in multiple computing means of a modular arithmetic unit comprising: an input register for holding an input number; multiple computing means for obtaining a multiple of said modulus corresponding to said low-order predetermined bits of said input number in said input register by having a multiple table in which multiples of said modulus are stored to correspond with said low-order predetermined bits of said input number and using said low-order predetermined bits of said input number to directly retrieve its corresponding multiple of said modulus from said multiple table; adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times; and correcting means for making a correction on the result of addition by said adder means.
Claim 8
Dependent Claim
182 words
A modular multiplication arithmetic unit comprising: a split multiplication section for multiplying a multiplier and each of blocks of a predetermined number of bits in a multiplicand and adding a residue to the result of multiplication, said block being taken from said multiplicand in sequence from its low-order side; an input register for holding an input number output from said split multiplication section; multiple computing means for obtaining a multiple of a modulus corresponding to a low-order predetermined bits of said input number in said input register by table lookup using a table in which arithmetic data has been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register, the result of said addition being applied to said split multiplication section as said residue for each addition until said addition is performed a predetermined number of times; and correcting means for making a correction on the result of addition by said adder means.
Claim 9
Dependent Claim
182 words
A modular multiplication arithmetic unit comprising: a split multiplication section for multiplying a multiplier and each of blocks of a predetermined number of bits in a multiplicand and adding a residue to the result of multiplication, said block being taken from said multiplicand in sequence from its low-order side; an input register for holding an input number output from said split multiplication section; multiple computing means for obtaining a multiple of a modulus corresponding to a low-order predetermined bits of said input number in said input register by table lookup using a table in which arithmetic data has been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register, the result of said addition being applied to said split multiplication section as said residue for each addition until said addition is performed a predetermined number of times; and correcting means for making a correction on the result of addition by said adder means.
Claim 10
Dependent Claim
59 words
The arithmetic unit according to claim 6, in which said multiple computing means has a multiple table in which multiples of said modulus are stored to correspond with said low-order predetermined bits of said input number, said low-order predetermined bits of said input number being used to directly retrieve a corresponding multiple of said modulus from said multiple table.
Claim 11
Dependent Claim
102 words
The arithmetic unit according to claim 6, in which said multiple computing means comprises multiple information computing means for using said low-order predetermined bits of said input number to retrieve the corresponding multiple information from a multiple information table in which multiple information is stored to correspond to low-order predetermined bits of said input number, a modulo register for storing a modulus, and a multiplier means for multiplying said multiple information obtained by said multiple information computing means and said modulus from said modulo register, thereby obtaining a multiple of said modulus corresponding to said low-order predetermined bits of said input number.
Claim 12
Dependent Claim
200 words
A modular arithmetic unit for computing TR -1 mod N=REDC(T) to obtain T mod N=REDC(T*(R 2 mod N)), the residue of the division of integer T by integer N, comprising: an input register for holding an input number T; multiple computing means for obtaining a multiple m'N (where m'=(T mod b) N' mod b, N'=integer, R (integer)=b n , b=2 k ) of a modulo N corresponding to a low-order predetermined bits of said input number T in said input register by table lookup using a table in which arithmetic data have been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple m'N of said modulo N obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times, thereby outputting t=(T+mN)/R; and correcting means for making a correction on the result t of addition by said adder means such that if t<N, t=REDC(T), and if t≧N, t-N=REDC(T), thereby obtaining TR -1 mod N.
Claim 13
Dependent Claim
200 words
A modular arithmetic unit for computing TR -1 mod N=REDC(T) to obtain T mod N=REDC(T*(R 2 mod N)), the residue of the division of integer T by integer N, comprising: an input register for holding an input number T; multiple computing means for obtaining a multiple m'N (where m'=(T mod b) N' mod b, N'=integer, R (integer)=b n , b=2 k ) of a modulo N corresponding to a low-order predetermined bits of said input number T in said input register by table lookup using a table in which arithmetic data have been stored in advance on the basis of said low-order predetermined bits of said input number; adder means for performing addition of said multiple m'N of said modulo N obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times, thereby outputting t=(T+mN)/R; and correcting means for making a correction on the result t of addition by said adder means such that if t<N, t=REDC(T), and if t≧N, t-N=REDC(T), thereby obtaining TR -1 mod N.
Claim 14
Dependent Claim
65 words
The arithmetic unit according to claim 9, in which said multiple computing means has a multiple table in which multiples m'N of said modulo N are stored to correspond with said low-order predetermined bits of said input number T, said low-order predetermined bits of said input number T being used to directly retrieve a corresponding multiple m'N of said modulo N from said multiple table.
Claim 15
Dependent Claim
108 words
The arithmetic unit according to claim 9, in which said multiple computing means comprises multiple information computing means for using said low-order predetermined bits of said input number to retrieve the corresponding multiple information m' from a multiple information table in which multiple information is stored to correspond to low-order predetermined bits of said input number, a modulo register for storing a modulo N, and a multiplier means for multiplying said multiple information m' obtained by said multiple information computing means and said modulo N from said modulo register, thereby obtaining a multiple m'N of said modulo N corresponding to said low-order predetermined bits of said input number.
References Cited (Backward Citations)
US3980874A
Cited
US4037093A
Cited
JPS6034131A
Cited
US4658094A
Cited
US4870681A
Cited
JPS6329784A
Cited
JPS6350883A
Cited
JPS63200233A
Cited
JPS63200183A
Cited
US4949293A
Cited
US4994994A
Cited
US5010573A
Cited
US5166978A
Cited
JPH03250314A
Cited
US5121431A
Cited
US5414651A
Cited
US5289397A
Cited
US5321752A
Cited
US5274707A
Cited
US5373560A
Cited
US5349551A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-12 | 1999-09-11 | 2000-03-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-12 | 2003-09-11 | 2004-03-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-12 | 2007-09-11 | 2008-03-12 | $7700.00 | Window Closed / Lapsed |