Patent US5572454A successfully refreshed from Google Patents.
US5572454A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Modulo reduction method using a precomputed table
Assignee: KT Corp
•
Filing: 1994-12-05
•
Granted: 1996-11-05
•
Expires: 2014-12-05
Abstract
Abstract A modulo reduction method using a precomputed table to increase a reduction speed during the execution of ordinary operational processes using computers and comprises a first step which searches out with an index of an upper log 2 t (t≧1) bit number and adds the value stored in a table to a lower n(n≧512) bit number; a second step, which if the result, obtained from the addition of said lower n bit number to the number searched out from the table at said first step, produces an overflow (1 bit), eliminates said overflow and finishes the execution of an operation; and a third step, which if said overlow does not occur at said second step, adds N on a modulo N to the result obtained from said first step and finishes the execution of the operation.
Inventors
- 👤 Yun H. Lee
- 👤 Chung R. Jang
- 👤 Myung S. Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 00:44
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/60; G06F7/72
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
171 words
A computer implemented method for modulo reduction of a first integer having k bits, larger than a second integer having n bits, the computer storing a precomputed table of numbers in memory, the method comprising: (a) searching the precomputed table of values stored in memory with the computer for a stored upper k-n bits number of the first integer, and adding the stored upper k-n bits number of the first integer to a lower n bits number of the first integer with the computer; (b) if the addition of the stored upper k-n bits number of the first integer with the lower n bits number of the first integer in step (a) produces an overflow, eliminating the overflow with the computer; and (c) if the addition of the stored upper k-n bits number of the first integer with the lower n bits number of the first integer in step (a) does not produce an overflow, adding the second integer to the result of the addition in step (a) with the computer.
Claim 2
Dependent Claim
171 words
A computer implemented method for modulo reduction of a first integer having k bits, larger than a second integer having n bits, the computer storing a precomputed table of numbers in memory, the method comprising: (a) searching the precomputed table of values stored in memory with the computer for a stored upper k-n bits number of the first integer, and adding the stored upper k-n bits number of the first integer to a lower n bits number of the first integer with the computer; (b) if the addition of the stored upper k-n bits number of the first integer with the lower n bits number of the first integer in step (a) produces an overflow, eliminating the overflow with the computer; and (c) if the addition of the stored upper k-n bits number of the first integer with the lower n bits number of the first integer in step (a) does not produce an overflow, adding the second integer to the result of the addition in step (a) with the computer.
Claim 3
Dependent Claim
108 words
The computer implemented method for modulo reduction according to claim 1, wherein the precomputed table stored in memory is addressed by an address X -- O having k-n bits, the precomputed table being constructed with the computer using the following steps: (1) setting an initial value of X -- O to 1 with the computer; (2) setting the number stored in the table with an address of X -- O to RT[X -- O]=(X -- O+1)×2 n mode N with the computer; (3) incrementing X -- O by 1 with the computer; and (4) repeating steps (2) and (3) while X -- O≦2 k-n -1 with the computer.
Claim 4
Dependent Claim
40 words
The computer implemented method for modulo reduction according to claim 2, wherein in constructing the table, if RT[X -- O]+N<2 n , then using RT[X -- O]=((X -- O+1)×2 n mod N)+N for all X -- O with the computer.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-05 | 2000-05-06 | 2000-11-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-05 | 2004-05-06 | 2004-11-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-05 | 2008-05-06 | 2008-11-05 | $7700.00 | Window Closed / Lapsed |