# Pseudo Random Permutation Generator

Original Publication Date: 1972-May-01

Included in the Prior Art Database: 2005-Feb-24

## Publishing Venue

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...