Random number generators

• US 7,016,925 B2
• Filed: 01/16/2004
• Issued: 03/21/2006
• Est. Priority Date: 04/13/2001
• Status: Expired due to Term

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Sceince Application International Corporation
• Inventors: Schmidt, Douglas Charles
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US10/758,433
• Publication Number:
  US 20040153486A1
• Time in Patent Office: 795 Days
• Field of Search: 708250-256
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/586 using an integer algorithm, e.g. using linear congruential method
• CPC Class Codes: G06F 7/72 using residue arithmetic

Abstract

A method and apparatus are provided for generating a parameter value to be used as a parameter for a random number generator. A random value is generated and the random value is mapped to a prime number. The parameter value is generated by multiplying the prime number by previously selected prime numbers. Each parameter value is then used as one of a plurality of parameters for the random number generator.

Claims

1. A method of generating a parameter for a random-number generator, comprising:

(1) generating a value;

(2) using the value to select a prime number;

(3) generating the parameter based on the selected prime number and a second prime number; and

(4) outputting the parameter for use with the random-number generator.

2. The method of claim 1, wherein step 4 comprises:

using the parameter for a linear congruential random-number generator.

3. The method of claim 2, further comprising:

(5) passing an output of the linear congruential random-number generator through a block encryptor.

4. The method of claim 1, further comprising:

(5) using an output of the random number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

5. The method of claim 3, further comprising:

(6) using an output of the random number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

6. The method of claim 1, wherein the second prime number comprises a previously selected prime number.

7. The method of claim 6, wherein step (3) comprises generating the parameter by multiplying the selected prime number by the second prime number.

8. The method of claim 7, further comprising repeating steps (1) through (3) a plurality of times while the parameter is less than a predetermined value, wherein the parameter generated during each iteration of steps (1) through (3) is a product of a most recently selected one of the selected prime numbers and previously selected prime numbers.

9. The method of claim 1, wherein step (2) comprises mapping the generated value to the prime number based on a nonlinear distribution function.

10. The method of claim 1, wherein step 2 comprises:

searching through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the parameter and a corresponding one of the weights.

11. The method of claim 1, wherein step (1) comprises generating a random value.

12. The method of claim 1, further comprising repeating steps (1)–

(4) for a plurality of random number generators.

13. A method of generating a parameter for a random-number generator, comprising:

(1) generating a first value;

(2) using the first value to select a first prime number P;

(3) generating a second value;

(4) using the second value to select a number K such that PK is at most equal to a predetermined maximum number;

(5) generating the parameter as a function of PK; and

(6) outputting the parameter for use with the random-number generator.

14. The method of claim 13, further comprising:

(7) generating a third value;

(8) using the third value to select a second prime number;

(9) generating a second parameter by multiplying the selected second prime number by at least one previously selected prime number; and

(10) using the parameter and the second parameter as parameters for the random-number generator.

15. The method of claim 14, wherein the random-number generator is a linear-congruential random-number generator.

16. The method of claim 15, further comprising:

(11) passing an output of the linear congruential random-number generator through a block encryptor.

17. The method of claim 16, further comprising:

(12) using an output of the linear congruential random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

18. The method of claim 14, further comprising repeating acts (7) through (9) a plurality of times while the second parameter is less than a predetermined value, wherein the second parameter generated during each iteration of acts (7) through (9) is a product of a most recently selected one of the selected prime numbers and previously selected prime numbers.

19. The method of claim 14, wherein step (7) comprises generating a random value.

20. The method of claim 13, wherein act 6 comprises:

using the parameter for a linear congruential random-number generator.

21. The method of claim 20, further comprising:

(7) passing an output of the linear congruential random-number generator through a block encryptor.

22. The method of claim 21, further comprising:

(8) using an output of the linear congruential random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

23. The method of claim 13, wherein step 2 comprises:

searching through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the first parameter and a corresponding one of the weights.

24. The method of claim 13, wherein step (1) comprises generating a random value.

25. The method of claim 13, wherein step (3) comprises generating a random value.

26. An apparatus for generating a parameter for a random-number generator, the apparatus comprising:

means for mapping a random value to a prime number P; and

means for generating the parameter by multiplying the prime number P by at least one previously selected prime number.

27. The apparatus of claim 26, wherein the means for generating produces the parameter for a linear congruential random-number generator.

28. The apparatus of claim 27, further comprising:

a block encryptor, wherein an output of the linear congruential random-number generator is arranged to be passed through the block encryptor.

29. The apparatus of claim 26, wherein the prime number mapper is arranged to search through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the random value and a corresponding one of the weights.

30. An apparatus for generating a parameter for a random-number generator, the apparatus comprising:

first means for mapping a random value to a prime number P;

second means for mapping a second random value to a number K such that PK is at most equal to a predetermined maximum number; and

means for generating a parameter as a function of PK, wherein the second means for mapping is included within the means for generating.

31. The apparatus of claim 30, wherein the means for generating produces the parameter for a linear congruential random-number generator.

32. The apparatus of claim 30, further comprising:

a block encryptor, wherein an output of the linear congruential random-number generator is arranged to be passed through the block encryptor.

33. The apparatus of claim 30, wherein the prime number mapper is arranged to search through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the random value and a corresponding one of the weights.

34. A machine-readable medium having information including instructions for a processor recorded thereon, the instructions comprising:

(1) generating a random value;

(2) using the random value to select a prime number;

(3) generating a parameter based on the selected prime number and a second prime number; and

(4) outputting the parameter for use as a parameter for a random number generator.

35. The machine-readable medium of claim 34, wherein step 4 comprises:

using the parameter for a linear congruential random-number generator.

36. The machine-readable medium of claim 35, further having instructions comprising:

(5) passing an output of the linear congruential random-number generator through a block encryptor.

37. The machine-readable medium of claim 36, further having instructions comprising:

(6) using an output of the linear congruential random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

38. The machine-readable medium of claim 34 further having instructions comprising:

(5) using an output of the random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

39. The machine-readable medium of claim 38, further having instructions comprising repeating steps (1) through (3) a plurality of times while the parameter is less than a predetermined value, wherein the parameter generated during each iteration of steps (1) through (3) is a product of a most recently selected one of the selected prime numbers and previously selected prime numbers.

40. The machine-readable medium of claim 34, wherein step 2 comprises:

searching through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the random value and a corresponding one of the weights.

41. The machine-readable medium of claim 34, wherein the second prime number comprises a previously selected prime number.

42. The machine-readable medium of claim 41, wherein step (3) comprises generating the parameter by multiplying the selected prime number by the second prime number.

43. A machine-readable medium having instructions recorded thereon for a processor to generate a parameter for a random-number generator, the instructions comprising:

(1) generating a first value;

(2) using the first value to select a first prime number P;

(3) generating a second value;

(4) using the second value to select a number K such that PK is at most equal to a predetermined maximum number; and

(5) generating the parameter as a function of PK.

44. The machine-readable medium of claim 43, further having instructions comprising:

(6) generating a third value;

(7) using the third value to select a second prime number; and

(8) generating a second parameter by multiplying the selected second prime number by at least one previously selected prime number.

45. The machine-readable medium of claim 44, further having instructions comprising:

(9) using the parameter and the second parameter as the parameter of a linear congruential random-number generator.

46. The machine-readable medium of claim 45, further having instructions comprising:

(10) passing an output of the linear congruential random-number generator through a block encryptor.

47. The machine-readable medium of claim 46, further having instructions comprising:

(11) using an output of the linear congruential random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

48. The machine-readable medium of claim 44, further having instructions comprising repeating acts (6) through (8) a plurality of times while the second parameter is less than a predetermined value, wherein the second parameter generated during each iteration of acts (6) through (8) is a product of a most recently selected one of the selected prime numbers and previously selected prime numbers.

49. The machine-readable medium of claim 43, further having instructions comprising:

(6) using the parameter as the parameter of a linear congruential random-number generator.

50. The machine-readable medium of claim 49, further having instructions comprising:

(7) passing an output of the linear congruential random-number generator through a block encryptor.

51. The machine-readable medium of claim 50, further having instructions comprising:

(8) using an output of the linear congruential random-number generator to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

52. The machine-readable medium of claim 43, further having instructions comprising:

using the parameter as the parameter for the random-number generator, wherein

an output of the random-number generator is used to establish a pseudo-randomly selected network address that is used to transmit a digital computer message.

53. The machine-readable medium of claim 43, wherein step 2 comprises:

searching through an ordered table of entries, each of the entries including a prime number and a weight, a respective prime number from one of the entries being selected based on the first value and a corresponding one of the weights.