EP0350278A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Digital signal processing
Assignee: HATFIELD POLYTECHNIC
•
Filing: 1989-07-04
•
Granted: —
•
Expires: 2009-07-04
Abstract
Abstract For more convenient mechanisation, the modulo m reduction of a binary number P can be carried out by conditionally summing the modulo m reductions of a power series of two and then modulo m reducing the sum. The modulo m reductions of the series, called the 'residues' of the series, can be pre-calculated and stored but this may be inconvenient if they are long in terms of numbers of bits. Herein, the residues are calculated in sequence by a recursive process, each residue being calculated from the next preceeding one, this leading to a 'serial' arrangement for generating the residues which can be incorporated into a serial modulo m reduction unit. Such a serial modulo m reduction unit is convenient for implementation as an integrated circuit especially as part of an overall circuit for encryption and decryption of digital signals.
Inventors
- 👤 John R. Guppy
- 👤 Paul A. Findlay
- 👤 Brian A. Johnson
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 07:03
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/722; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; G06F7/38; G06F7/48; G06F7/499; G06F7/49931; G06F7/723; H04L2209/00; H04L2209/12; H04L2209/122; H04L2209/125
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
83 words
A method of performing a modulo m reduction of a binary number, in which method a series of residue values comprising the modulo m reductions of ascending powers of two are calculated in sequence, each being calculated from the value of the next preceding calculation in a recursive process, and said residue values are conditionally summed in dependence upon the bit values of said binary number to give a sum of residues value indicative of said modulo m reduction of said binary number.
Claim 2
Independent Claim
83 words
A method of performing a modulo m reduction of a binary number, in which method a series of residue values comprising the modulo m reductions of ascending powers of two are calculated in sequence, each being calculated from the value of the next preceding calculation in a recursive process, and said residue values are conditionally summed in dependence upon the bit values of said binary number to give a sum of residues value indicative of said modulo m reduction of said binary number.
Claim 3
Dependent Claim
98 words
A method according to claim 1, wherein for each bit p i of said binary number there is formed an associated residue value r i equal to 2r i - l if (2r i-l - m) is less than zero or to (2r i-l - m) if (2r i-l - m) is greater than zero, said residue values being formed in sequence and r i-l being the value formed next previously in the sequence, and wherein the residue values associated with the binary number bits having logic one values are summed to form said sum of residues value.
Claim 4
Dependent Claim
95 words
A method for the encryption or decryption of a digital signal comprising: making the bits of said signal available in sequence; for each bit of a chosen multiple bit digital exponent using bit serial multiplier means to square said signal and, in dependence upon the respective bit values of said chosen multiple bit digital exponent, conditionally multiplying the result of the squaring operation by the original signal, and carrying out a modulo m reduction of the result of each operation carried out by the multiplier means using the reduction method of claim 1 or 2.
Claim 5
Dependent Claim
80 words
A method according to claim 3, wherein each intermediate sum of residues value ie. other than the final sum of residues indicative of the fully encrypted or decrypted signal, is returned without further reduction to said multiplier means and only the final sum of residues is subjected to a modulo m reduction operation, said multiplier means having a bit capacity greater than the number of bits of the modulus m by an amount sufficient to handle properly said intermediate values.
Claim 6
Dependent Claim
71 words
Apparatus for performing modulo m reduction of a binary number comprising calculating means for calculating a series of residue values comprising the modulo m reductions of ascending powers of two, the calculating means being operable for calculating each residue value from the value of the next preceding calculation in a recursive process, and summing means for conditionally summing said residue values in dependence upon the bit values of said binary number.
Claim 7
Dependent Claim
71 words
Apparatus for performing modulo m reduction of a binary number comprising calculating means for calculating a series of residue values comprising the modulo m reductions of ascending powers of two, the calculating means being operable for calculating each residue value from the value of the next preceding calculation in a recursive process, and summing means for conditionally summing said residue values in dependence upon the bit values of said binary number.
Claim 8
Dependent Claim
96 words
Apparatus for the encryption/decryption of a digital signal comprising:- means for presenting the bits of said signal in sequence; means for presenting the bits of a chosen multiple bit digital exponent in sequence; bit serial multiplier means operable, for each bit of said exponent, to square said signal and, in dependence upon the respective bit value of the exponent, conditionally multiplying the result of the squaring operation by the original signal; and modulo m reduction means according to claim 5 for performing a modulo m reduction on the result of each operation by the multiplier means.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.