Mixed Radix Number Generator with Chosen Statistical Artifacts

• US 20080307024A1
• Filed: 06/07/2007
• Published: 12/11/2008
• Est. Priority Date: 06/07/2007
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Michaels, Alan J., Chester, David B.
• Granted Patent: US 7,962,540 B2
• Time in Patent Office: Days
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A method is provided for masking a process used in generating a number sequence. The method includes generating a first sequence of numbers contained within a Galois field GF[M]. The method also includes performing a first modification to a first number in the first sequence of numbers. The first modification includes summing the first number with a result of a modulo P operation performed on a second number of the first sequence that proceeds the first number. M is relatively prime with respect to P. The method further includes performing a second modification to the first random number. The second modification is comprised of a modulo P operation. This second modification is performed subsequent to the first modification. The method includes repeating the first and second modification for a plurality of numbers comprising the first sequence of numbers to generate a second sequence of numbers.

Claims

1. A method for masking a process used in generating a number sequence, comprising:

generating a first sequence of numbers contained within a Galois field GF[M];

performing a first modification to a first number in said first sequence of numbers comprising summing said first number with a result of a modulo P operation performed on a second number of said first sequence that proceeds said first number, where M is relatively prime with respect to P;

subsequent to said first modification, performing a second modification to said first random number comprising a modulo P operation;

repeating said first and second modification for a plurality of numbers comprising said first sequence of numbers to generate a second sequence of numbers.

2. The method according to claim 1, further comprising modifying a digital data stream with said second sequence of numbers.

3. The method according to claim 1, wherein said generating step further comprises generating a pseudo-random sequence of numbers containing chosen statistical artifacts relating to said generating step, and wherein said statistical artifact are chosen to create a uniformly distributed sequence of random numbers on GF[P] by said first and second modification step.

4. The method according to claim 1, wherein said generating step further comprises exhaustively producing said first sequence of numbers by using a mapping which is periodically repeated.

5. The method according to claim 4, further comprising selecting said mapping to include a combination of an additive mapping and a multiplicative mapping.

6. The method according to claim 5, further comprising selecting said additive mapping and said multiplicative mapping in combination to include repeated computations of an irreducible polynomial over a Galois field GF[M].

7. The method according to claim 1, further comprising selecting a value of M that is larger than P.

8. The method according to claim 1, further comprising selecting a value of M that is mutually prime with P and all of a plurality of prime factors of P including p₁, p₂, p₃, . . . p_k.

9. The method according to claim 8, further comprising performing a third modification step on said second sequence of numbers, said third modification step comprising generating a plurality of output number sequences from said second sequence of numbers.

10. The method according to claim 9, wherein said third modification step comprises a modulo p operation performed upon each number in said second sequence of numbers to generate said plurality of output number sequences, where p includes a plurality of values selected from the group comprising p₁, p₂, p₃, . . . p_k.

11. The method according to claim 1, wherein said second number is immediately preceding said first number.

12. The method according to claim 1, wherein said second number precedes said first number by H positions, where N is greater than 1.

13. The method according to claim 1 wherein said second sequence of numbers has statistical artifacts that are evenly distributed over a plurality of equivalence classes of said Galois field GF[P], and said plurality of equivalence classes include an equivalence class for each integer 0, 1, . . . , P−

1.

14. A mixed radix number generator, comprising:

a number generator configured for generating a first sequence of numbers contained within a Galois field GF[M];

a mixed radix accumulator configured for (1) performing a first modification to a first number in said first sequence of numbers comprising summing said first number with a result of a modulo P operation performed on a second number of said first sequence that proceeds said first number, where M is relatively prime with respect to P, (2) subsequent to said first modification, performing a second modification to said first random number comprising a modulo P operation; and

(3) repeating said first and second modification for a plurality of numbers comprising said first sequence of numbers to generate a second sequence of numbers.

15. The system according to claim 14, further comprising means configured for using said second sequence of numbers to modify a digital data stream.

16. The system according to claim 14, wherein said number generator comprises a pseudo-random number generator for generating a pseudo-random sequence of numbers containing statistical artifacts relating to said generation of said first sequence of numbers, and wherein said statistical artifact is eliminated by said mixed radix accumulator.

17. The system according to claim 14, wherein said number generator is configured for exhaustively producing said first sequence of numbers by using a mapping which is periodically repeated.

18. The system according to claim 17, wherein said mapping includes a combination of an additive mapping and a multiplicative mapping.

19. The system according to claim 18, wherein said additive mapping and said multiplicative mapping in combination include repeated computations of an irreducible polynomial over a Galois field GF[M].

20. The system according to claim 14, wherein M is larger than P.

21. The system according to claim 14, further wherein a value of U is mutually prime with respect to a value of P and all of a plurality of prime factors of P including p₁, p₂, p₃, . . . p_k.

22. The system according to claim 21, further comprising a plurality of arithmetic operator units each configured for performing a third modification on said second sequence of numbers said plurality of arithmetic operator units generating a plurality of output number sequences from said second sequence of numbers.

23. The system according to claim 22, wherein said third modification comprises a modulo p operation performed upon each number in said second sequence of numbers to generate said plurality of output number sequences, where p includes a plurality of values selected from the group comprising p₁, p₂, p₃, . . . , p_k.

24. The system according to claim 14, wherein said second number precedes said first number by one position.

25. The system according to claim 14, wherein said second number precedes said first number by H positions, where N is greater than 1.

26. The system according to claim 14, wherein said first sequence of numbers is limited to a finite number of elements M defined by a Galois field GF[M], said second sequence of numbers has statistical artifacts that, are evenly distributed over a plurality of equivalence classes of said Galois field GF[P], and wherein said plurality of equivalence classes include an equivalence class for each integer 0, 1, . . . , P−

1.

27. The system according to claim 14, wherein said first sequence is operated upon by a filter structure configured to perform calculations inside a Galois field of equal size to the second sequence.