Browse Prior Art Database

# Pseudo Random Permutation Generator

IP.com Disclosure Number: IPCOM000076953D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 25K

IBM

## Related People

Bard, Y: AUTHOR [+2]

## Abstract

This computer-implemented method generates efficiently and with a limited amount of main storage pseudo-random permutations of a very large number of elements (for example, a million lottery numbers).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 40% of the total text.

Page 1 of 4

Pseudo Random Permutation Generator

This computer-implemented method generates efficiently and with a limited amount of main storage pseudo-random permutations of a very large number of elements (for example, a million lottery numbers).

The generation of random number sequences for this purpose is required to meet the following conditions: 1) Lack of obvious patterns or easily detectable deviations from randomness 2) Generation process extremely difficult to decode
3) Reasonably even spread of "winning" numbers among different number groups (e.g., blocks of lottery tickets) 4) Program requires data inputs from several persons, none of whom is to be entrusted with knowledge of all the needed inputs for generating a number sequence

For the purpose of this description, the number of elements to be permuted is denoted by M. The method requires the following steps: 1. Label the elements 0, 1, ... , M-1. 2. Find the smallest number m such that M</-2/m/. 3. Considering the set of nonnegative integers from 0 to 2/m/-1, i.e., the set of nonnegative integers representable as m-bit binary numbers, assign each bit position to one of two or more classes, and designate the classes as A, B(1),
....B(j) (j>/-1). The assignment of bit positions to classes can be done by any rule or scheme whatever, provided that the low-order bit must not be assigned to class A. An example of possible classification of bits is shown above.

Let A denote the set of m-bit integers obtained by taking all possible combinations of values for the bit positions in class A, and the value 0 for the bit positions in all the other classes. For each i (1</-i</-j) let B(i) denote the set of m-bit integers obtained by taking all possible combinations of values for the bit positions in class B(i), and the value 0 for the bit positions in all the other classes.
4. For each i (1</-i</-j), choose an odd integer N(i) such that 1</-N(i)</-2/m/-1. These integers N(i) are called the multipliers, and can be chosen by any scheme or procedure whatever; in particular they can be chosen by using a pseudo- random number generator such as that described by Hutchinson. 5. Compute all the integers of the form

(Image Omitted)

The set of all these integers is called the candidate standard batch, and the number of elements in the set is denoted by C. 6. One or more tests for randomness are now applied to the candidate standard batch. In the first test, the elements of the batch are taken (mod 100) and the frequency of occurrence of each residue 0,1,..., 99 is computed, and denoted by x(k) (k=0,. . ., 99). If the candidate standard batch were a random sample from the population of integers 0 to 2/m/-1, the set {x(k)} would be approximately distributed as a sample of size 100 from a Poisson distribution with mean C/100. A chi-square test of goodness of fit is now applied to test this hypothesis. The number of classes and significance level for this test may be chosen at will. (In practice it was foun...