Patent US4890252A successfully refreshed from Google Patents.
US4890252A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Long period pseudo random number sequence generator
Assignee: California Institute of Technology
•
Filing: 1987-10-29
•
Granted: 1989-12-26
•
Expires: 2007-10-29
Abstract
Abstract A circuit for generating a sequence of pseudo random numbers, {A k }. There is an exponentiator (30') in GF(2 m ) for the normal basis representation of elements in a finite field GF(2 m ) each represented by m binary digits and having two inputs and an output from which the sequence {A k } of pseudo random numbers is taken. One of the two inputs is connected to receive the outputs {E k } of maximal length shift register of n stages. There is a switch (32) having a pair of inputs and an output. The switch (32) output is connected to the other of the two inputs of the exponentiator (30'). One of the switch (32) inputs is connected for initially receiving a primitive element A 0 in GF(2 m ). Finally, there is a delay circuit (34) having an input and an output. The delay circuit (34) output is connected to the other of the switch (32) inputs and the delay circuit (34) input is connected to the output of the exponentiator (30') whereby after the exponentiator (30') initially receives the primitive element A 0 in GF(2 m ) through the switch (32), the switch (32) can be switched to cause the exponentiator (30') to receive as its input a delayed output A k-1 from the exponentiator (30') thereby generating {A k } continuously at the output of the exponentiator (30'). The exponentiator (30') in GF(2 m ) is novel and comprises a cyclic-shift circuit; a Massey-Omura multiplier; and, a control logic circuit all operably connected together to perform the function U i =.sub.α 2 i (for n i =1) or 1 (for n i =0).
Inventors
- 👤 Charles C. Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:40
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/58; G06F7/582; G06F7/584; G06F7/60; G06F7/72; G06F7/724; H; H04; H04L; H04L9/00; H04L9/06; H04L9/065; H04L9/0656; H04L9/0662; G06F2207/00; G06F2207/58; G06F2207/581; G06F2207/582; H04L2209/00; H04L2209/12; H04L2209/125
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
224 words
A circuit for generating a sequence of pseudo random numbers, {A k }, comprising: (a) an exponentiator in GF(2 m ) for the normal basis representation of elements in a finite field GF(2 m ) each represented by m binary digits and having two inputs and an output from which the sequence {A k ] of pseudo random numbers is taken, one of said two inputs being connected to receive the outputs {E k } of a maximal length shift register of n stages; (b) a switch having a pair of inputs and an output, said output of said switch being connected to the other of said two inputs of said exponentiator, one of said inputs of said switch being connected for initially receiving a primitive element A 0 in GF(2 m ); and (c) a delay circuit having an input and an output, said output of said delay circuit being connected to the other of said switch inputs, said input of said delay circuit being connected to said output of said exponentiator whereby after said exponentiator initially receives said primitive element A 0 in GF(2 m ) through said switch, said switch is switched to make said exponentiator receive as an input thereto a delayed output A k-1 from said exponentiator thereby generating {A k } continuously at said output of said exponentiator.
Claim 2
Dependent Claim
224 words
A circuit for generating a sequence of pseudo random numbers, {A k }, comprising: (a) an exponentiator in GF(2 m ) for the normal basis representation of elements in a finite field GF(2 m ) each represented by m binary digits and having two inputs and an output from which the sequence {A k ] of pseudo random numbers is taken, one of said two inputs being connected to receive the outputs {E k } of a maximal length shift register of n stages; (b) a switch having a pair of inputs and an output, said output of said switch being connected to the other of said two inputs of said exponentiator, one of said inputs of said switch being connected for initially receiving a primitive element A 0 in GF(2 m ); and (c) a delay circuit having an input and an output, said output of said delay circuit being connected to the other of said switch inputs, said input of said delay circuit being connected to said output of said exponentiator whereby after said exponentiator initially receives said primitive element A 0 in GF(2 m ) through said switch, said switch is switched to make said exponentiator receive as an input thereto a delayed output A k-1 from said exponentiator thereby generating {A k } continuously at said output of said exponentiator.
Claim 3
Dependent Claim
74 words
The circuit for generating a sequence of pseudo random numbers, {A k }, of claim 1 wherein said exponentiator in GF(2 m ) comprises: (a) a cyclic-shift circuit; (b) a Massey-Omura multiplier; and (c) a control logic circuit connected to said cyclic-shift circuit and said Massey-Omura multiplier to perform the function U i =.sub.α 2 i (for n i =1) or 1 (for n i =0), where i is an integer greater than zero.
Claim 4
Independent Claim
230 words
A method of generating a sequence of pseudo random numbers, {A k }, comprising the steps of: (a) providing an exponentiator in GF(2 m ) for the normal basis representation of elements in a finite field GF(2 m ) each represented by m binary digits and having two inputs and an output from which the sequence {A k } of pseudo random numbers is taken; (b) connecting one of the two inputs to receive the outputs {E k } of a maximal length shift register of n stages; (c) providing a switch having a pair of inputs and an output; (d) connecting the output of the switch to the other of the two inputs of the exponentiator; (e) connecting one of the inputs of the switch to a source of a primitive element A 0 in GF(2 m ); (f) providing a delay circuit having an input and an output; (g) connecting the output of the delay circuit to the other of the switch inputs; (h) connecting the input of the delay circuit to the output of the exponentiator; (i) initially positioning the switch to receive the primitive element A 0 in GF(2 m ); and (j) thereafter positioning the switch to make the exponentiator receive as an input thereto a delayed output A k-1 from the exponentiator thereby generating {A k } continuously at the output of the exponentiator.
Claim 5
Independent Claim
230 words
A method of generating a sequence of pseudo random numbers, {A k }, comprising the steps of: (a) providing an exponentiator in GF(2 m ) for the normal basis representation of elements in a finite field GF(2 m ) each represented by m binary digits and having two inputs and an output from which the sequence {A k } of pseudo random numbers is taken; (b) connecting one of the two inputs to receive the outputs {E k } of a maximal length shift register of n stages; (c) providing a switch having a pair of inputs and an output; (d) connecting the output of the switch to the other of the two inputs of the exponentiator; (e) connecting one of the inputs of the switch to a source of a primitive element A 0 in GF(2 m ); (f) providing a delay circuit having an input and an output; (g) connecting the output of the delay circuit to the other of the switch inputs; (h) connecting the input of the delay circuit to the output of the exponentiator; (i) initially positioning the switch to receive the primitive element A 0 in GF(2 m ); and (j) thereafter positioning the switch to make the exponentiator receive as an input thereto a delayed output A k-1 from the exponentiator thereby generating {A k } continuously at the output of the exponentiator.
Claim 6
Dependent Claim
49 words
The method for generating a sequence of pseudo random numbers, {A k }, of claim 3 wherein: the exponentiator in GF(2 m ) performs the function U i =.sub.α 2 i (for n i =1) or 1 (for n i =0), where i is an integer greater than zero.
Claim 7
Dependent Claim
102 words
The method for generating a sequence of pseudo random numbers, {A k }, of claim 4 and additionally including the recursive steps of: (a) letting A=α(a point in the finite field GF(2 m )); (b) if n 0 =1, letting B=A otherwise, letting B=1; (c) letting C=1 and k=0; (d) multiplying B and C to obtain Z=BC; (e) setting k=k+1; (f) replacing A with the cyclic shift (CS) of A; (g) if k=m, Z=α N , (where 1≦N≦2 m -1) stopping; (h) if k<m, setting C=Z; and, setting B=A if n k =1, otherwise setting B=1; (i) going back to step (d).
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) | 1992-12-25 | 1993-06-26 | 1993-12-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-12-25 | 1997-06-26 | 1997-12-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-12-25 | 2001-06-26 | 2001-12-26 | $7700.00 | Window Closed / Lapsed |