ONE-TIME PAD GENERATION

Abstract

A computer-implemented method of generating a one-time pad for use in encryption, the method comprising: determining a seed sequence and an ordered set of initial values; and for each initial value, computing a sequence of terms, wherein each term of the sequence is computed by combining at least one other term of that sequence with at least one term of a previous one of the sequences using modular arithmetic, the previous sequence being the sequence generated for the previous initial value or, in the case of the first initial value, the seed sequence. Rather than using the final sequence as a direct basis for the one-time pad, one or more additional steps are taken to disrupt the final sequence, in order to improve the security of the method and the resulting one-time pad.

Claims

1. A computer-implemented method of generating a one-time pad for use in encryption, the method comprising: determining a seed sequence and an ordered set of initial values; for each initial value, computing a sequence of terms, wherein each term of the sequence is computed by combining at least one other term of that sequence with at least one term of a previous one of the sequences using modular arithmetic, the previous sequence being the sequence generated for the previous initial value or, in the case of the first initial value, the seed sequence; processing each term of a final one of the sequences, the final sequence being the sequence computed for the final initial value, to determine therefrom a reduced pseudorandom number having a smaller bit length than the processed term, thereby generating a sequence of reduced pseudorandom numbers; wherein the one-time pad comprises or is derived from the sequence of reduced pseudo random numbers for encrypting a sequence of symbols by transforming each symbol of the sequence of symbols with a corresponding element of the one-time pad. The method of claim 1, wherein each terms of the final sequence is processed by sampling therefrom a subset of bits.

3. The method of claim 2, wherein the subset of bits consists of a predetermined number of leading bits of the sampled-from term, the remaining trailing bits of that term being discarded,

4. The method of any of claims 1 to 3, wherein the sequence of reduced pseudorandom numbers is a reduced sequence, determined by selectively discarding any of the reduced pseudorandom numbers which do not match any element of a defined alphabet, the one-time pad comprising or derived from the reduced sequence of reduced pseudorandom numbers.

5. The method of claims 3 and 4, wherein the alphabet contains q elements, wherein only the p leading bits of each term of the final sequence are retained, where p=N+Int[log.sub.2 q] and N≥1.

6. A computer-implemented method of generating a one-time pad for use in encryption, the method comprising: determining a seed sequence and an ordered set of initial values; for each initial value, computing a sequence of terms, wherein each term of the sequence is computed by combining at least one other term of that sequence with at least one term of a previous one of the sequences using modular arithmetic, the previous sequence being the sequence generated for the previous initial value or, in the case of the first initial value, the seed sequence; and determining a reduced sequence of pseudorandom numbers by selectively discarding terms of a final one of the sequences outside of a predefined alphabet, the final sequence being the sequence computed for the final initial value; wherein the one-time pad comprises or is derived from the reduced sequence of pseudorandom numbers for encrypting a sequence of symbols by transforming each term of the sequence of symbols with a corresponding component of the one-time pad.

7. The method of claim 6, wherein each term of the final sequence is processed to determine therefrom a reduced pseudorandom number having a smaller bit length than the processed term, wherein the reduced sequence contains only reduced pseudorandom numbers within the alphabet, with terms of the final sequence whose reduced pseudorandom numbers are outside of the alphabet being discarded.

8. The method of any preceding claim, wherein at least nine initial values are used, and the modular arithmetic is performed with respect to a modulus of at least 2.sup.60, and preferably at least 2.sup.90, and more preferably at least 2.sup.120.

9. The method of any preceding claim wherein the modular arithmetic is performed with respect to a modulus that is a power of two or a power of a prime number other than two or a composite modulus which has two or more different prime factors each of which may be raised to a possibly different power.

10. The method according to claim 9, wherein the modulus is a power of two, and the seed sequence is defined by a seed value that is odd.

11. The method of any preceding claim, wherein the seed sequence is a repetition of a single seed value, and each term of each sequence for each initial value is computed as the modular sum of the previous term of the same sequence, and the corresponding term of the previous sequence.

12. The method of any preceding claim, comprising the step using the one-time pad to encrypt a piece of data in the form of a sequence of symbols.

13. The method of any preceding claim, comprising the step of using the one-time pad to decrypt a piece of data.

14. The method of claim 12 or 13, when dependent on claim 4 or 6, wherein the encryption or decryption is performed using modular arithmetic with respect to a modulus q, where q is the size of the alphabet, and is less than a modulus M with respect to which the sequences are computed.

15. The method of claim 12 or any claim dependent thereon, wherein different, non-overlapping parts of the one-time pad are used to encrypt different messages, wherein each encrypted message is rendered available to a recipient with a marker denoting the part of the one-time part used to encrypt it.

16. The method of any preceding claim, comprising the step of transmitting or otherwise communicating the one-time pad to a remote computer device for use in encryption or decryption performed at the remote device.

17. A computer system comprising one or more computers, programmed or otherwise-configured to carry out the method of any preceding claim.

18. A computer program configured to program a programmable computer system to carry out the method of any of claims 1 to 16.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0033] For a better understanding of the present invention and to show how the same may be carried into effect, reference will now be made by way of example to the following drawings.

[0034] FIG. 1 illustrates certain principles of an Additive Congruential Random Number (ACORN) generator;

[0035] FIG. 1A is a schematic block diagram of an ACORN generator function;

[0036] FIG. 2 shows a flowchart for a method of generating a one-time pad;

[0037] FIG. 2A schematically illustrates an iterative algorithm for generating a one-time pad once an initialization has been chosen, and FIG. 2B shows a flowchart for the algorithm; and

[0038] FIG. 3 shows a signalling diagram for a method of secure communication using a one-time pad.

DESCRIPTION

[0039] The described embodiments of the invention make use of the “ACORN” (Additive Congruential Random Number) generator. ACORN generators are a robust family of pseudorandom number generators (PRNGs) which have been applied in geostatistical, oil reservoir modelling, and probabilistic risk assessment applications. Further details of the ACORN family may be found at http://acorn.wikramaratna.org/, the entire contents of which is incorporated herein by reference.

[0040] The present disclosure considers a novel application of ACORN generators to cryptography, and the viability of that application has been demonstrated through extensive empirical testing using the TestU01 library. This is described in detail below, but first details of the ACORN generator are described by way of context.

[0041] The method of generating the sequence of pseudo-random numbers is discussed in more detail below with reference to FIG. 1.

[0042] FIG. 1 uses rectangles to represent integer values and arrows to denote modular arithmetic. The values are arranged in a two-dimensional array, as this conveniently reflects the mathematical operations according to which the full set of values is derived. A seed value is denoted by reference numeral 104 and an ordered set of initial values is denoted by reference numeral 106 (shown as bold-outline rectangles). A seed sequence 102 is defined as a repetition of the seed value (i.e. every term in the seed sequence 102 equals the seed value 104). Each other depicted value is a value derived directly or indirectly from the seed value 104 and at least one of the initial values 106 using modular arithmetic. Each such value is shown to have two other values connected to it, which denotes the fact that this value is derived as the mod-M sum of those two other values, where M is a defined modulus. The modulus M, seed value 102 and set of initialization values 104 constitute the initialization of the ACORN generator.

[0043] A sequence of terms is generated for each initial value of the ordered set of initial values 106 (i.e. one sequence per initial value). The sequence generated for a given initial value is generated from that initial value in combination with the previous sequence, in the following manner.

[0044] In the following, the seed value 102 is denoted in mathematical notation as s and the set of initial values 106 is denoted in matrix notation as (Y.sub.10, . . . Y.sub.k0), with k initial values in total. These are depicted in FIG. 1 as running vertically down the left-most column of values. The integer k is referred to as the “order” of the initialization. The seed sequence 102 is defined as

(Y.sub.00, . . . Y.sub.01)

with

Y.sub.0n=s∀0≤n≤l,

where l+1 is a sequence length. The ACORN generator can generate sequences of any desired sequence length (see below). The seed sequence 102 is shown running horizontally across the top-most row in FIG. 1.

[0045] Each derived value is defined as

Y.sub.mn=(Y.sub.m-1,n+Y.sub.m,n-1)modM,   (1)

for 0≤m<k and 0≤n≤l where the l can be as large as desired. In the cryptography application described below, l will be determined by the length of the one-time pad that is required in a given context.

[0046] Regarding notation, in the ACORN literature, the notation Y.sup.m.sub.n is used in place of Y.sub.mn. Herein, Y.sup.m.sub.n, Y.sub.mn and Y.sub.m,n are synonymous (the “Y.sub.m,n” form is used where helpful to avoid ambiguity). The notation Y.sup.m.sub.n is also used in Annex B of this description.

[0047] Under this definition, a sequence (Y.sub.m0, . . . , Y.sub.ml) of length l+1 is computed for each initial value Y.sub.m0. Each such sequence is referred to as a “derived sequence” or “ACORN sequence” to distinguish from the seed sequence 102. The first value of each derived sequence is the corresponding initial value. Expressed in words, it can he seen from Equation (1) that each subsequent (derived) value Y.sub.mn of each derived sequence is defined as the mod-M sum of the n-1.sup.th value, of the same sequence and the n.sup.th value, Y.sub.m-1,n, of the previous sequence (i.e. the sequence computed for the previous initial value Y.sub.m-1 for m>1 or, in the case of m=1, the seed sequence 102).

[0048] A “final” sequence (Y.sub.k0, . . . , Y.sub.kl), denoted by reference numeral 108, is computed for the final initial value Y.sub.k0 (reference numeral 110), which is shown as the bottom-most row in FIG. 1.

[0049] A novel application of the ACORN generator to cryptography will now be described, in which the final sequence 110 forms the basis of a one-time pad (that is, a keystream).

[0050] As depicted in FIG. 1A, the ACORN generator can be implemented as a function f, denoted by reference numeral 150, where:

f(s, Y.sub.1,n−1, . . . , Y.sub.k,n−1)=(Y.sub.1n, . . , Y.sub.kn).   (2)

[0051] That is, as a function f applied to the seed s and the n−1.sup.th column of values (i.e. the column containing value n−1 of every derived sequence), in order to return the n.sup.th column of values (i.e. the n.sup.th value of every derived sequence) in accordance with Equation (1). In order to generate sequences of arbitrary length l+1, the ACORN generator f is called l times, starting with the initial values (Y.sub.10, . . . , Y.sub.k0).

[0052] The value Y.sub.kn of the final sequence is a pseudorandom number (prn), and is the part of the ACORN output that is used as a basis for one-time pad generation, as will now be described.

[0053] FIG. 2 shows a flowchart for a method of generating a one-time pad using the ACORN generator. The method adopts certain parameter choices, and the reasons for these choices are elaborated on below.

[0054] Certain aspects of the method are optimized for efficient implementation on a 32-bit computing platform, e.g. formed of one or more 32-bit CPUs (central processing unit). A 32-bit architecture operates on units of data having a size of 32 bits. However, as will be appreciated, those aspects of the method can be readily adapted for implementation on other computer architectures, such as a 64-bit architecture (or 128 bit, or larger, if such hardware were available), in accordance with the general teaching presented herein.

[0055] One example of a 32-bit implementation uses two integer words to represent integers up to 2.sup.60 (with modulus M=2.sup.60) or four integer words to represent. integers up to 2.sup.120 (with modulus M=2.sup.120). As will be appreciated, a larger modulus becomes easier to implement on 64-bit (or higher) architecture using 64-bit (or higher) integers.

[0056] A 32-bit integer can store integers up to 2.sup.31−1 without overflow (the final bit is generally interpreted as a plus or a minus). Working in modulo 2.sup.30 makes it possible to add two such integers plus one (from a carry) without exceeding 2.sup.31−1 and getting an overflow. With 64-bit integers, it is possible to work with modulus up to 2.sup.62 but it is convenient to limit to modulus 2.sup.60 because it maintains a straightforward mapping between the 32-bit and 64-bit implementations. As will be appreciated, this is merely one example of convenient implementation, the present disclosure is not limited in this respect.

[0057] At Step 202, an order k for the generator is selected, where k is at least 9—to ensure the random nature of the resulting pad (see below).

[0058] At Step 204, a modulus M for the generator is selected. A suitable value is M=2.sup.120 and that is the value adopted in the following. However, a larger power of 2 may be used, with minor modifications to the method. It is convenient, but by no means essential, to work with a modulus that is power of two. Considerations around the choice of modulus are discussed in further detail below —see, in particular, the section entitled “Periodicity and randomness”.

[0059] At Step 206, a value of the seed s is selected as an odd integer between 1 and M−1. A value of s is chosen to satisfy conditions set out below (see Empirical Testing, below) as follows. For modulus M=2.sup.120, the seed is specified by four non-negative integer values, each strictly less than 2.sup.30 such that

s=(2.sup.90)s.sub.1+(2.sup.60)s.sub.2+(2.sup.30)s.sub.3+s.sub.4

where s.sub.1, s.sub.2 and s.sub.3 are each not equal to either 0 or 2.sup.30−1 (i.e. their binary representations are. not all zeroes or all ones) and s.sub.4 takes an odd value; modulus M=2.sup.120 gives more than 2.sup.110 values to choose from (the exact number is (2.sup.30−1)(2.sup.30−1)(2.sup.29).

[0060] The seed value 104 is an integer value greater than zero and less than the modulus. An odd seed value is chosen because the modulus in this example is even. More generally, that seed value s and modulus M are relatively prime. That is, the two values have no prime factors in common. For a modulus that is equal to a power of 2, the seed value 104 may conveniently take any odd value. However, the more general considerations pertaining to the selection of the modulus are discussed below, in the “Periodicity and randomness” section.

[0061] With the above formulation, an acceptable seed s may be obtained under the following conditions:

[0062] 1. s.sub.1, s.sub.2, s.sub.3 and s.sub.4 are all strictly less than 2.sup.30,

[0063] 2. The binary representations of s.sub.1, s.sub.2 and s.sub.3 are each not all zeroes and not all ones, and

[0064] 3. s.sub.4 is odd.

[0065] The above conditions have been determined for modulus M=2.sup.120 and are supported through empirical testing with TestU01, as detailed below. More generally, an acceptable seed may be determined through empirical randomness testing of the final ACORN sequence 108, for any choice of modulus.

[0066] At Step 208, k initial values are selected, (Y.sub.10, . . . , Y.sub.k0). The initial values can be assigned arbitrarily, though it may be convenient to select each initial value Y.sub.n0 so that it is approximately uniformly random between 0 and M−1. Any appropriate method can be used to generate the initial values 106. In theory, one could toss a coin 120 times for each initial value—which means 120 k times in all—and assign each bit 0 or 1 according to the outcome of the toss. A more practical implementation can apply any appropriate PRNG (which aright be a different ACORN generator or an arbitrary different PRNG) to generate k strings of 120 zeros and ones and assign the initial values accordingly. Note that the method used to assign the initial values need not be cryptographically strong per se, nor is it actually a requirement for the initial values to be uniformly distributed. It may be convenient, but not essential, to assign them uniformly at random (rather than, say, zeroes) as it makes exhaustive testing even more onerous for an attacker who may try to break the encryption scheme.

[0067] The encryption scheme is defined with respect to an “alphabet” of size a. A message to be encrypted should be made up entirely of symbols belonging to the alphabet (which defined a symbols in total). That is, all characters appearing in the plaintext must also appear in the alphabet; however, it is not a requirement that all characters in the alphabet need appear in the message. By way of example, the following alphabets are considered (but any suitable alphabet can be chosen in any given context): [0068] i. To encrypt a binary file, the alphabet would consist of [0,1] [0069] ii. To encrypt a hexadecimal file, the alphabet would consist of [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] [0070] iii. To encrypt an alphanumeric file, the alphabet might consist of [a,b,c,d,e,f,g,h,i,j,k,l, . . . , A,B,C,D, . . . , 0,1,2,3,4,5,6,7,8,9]; it could also be extended to include standard punctuation, for example “;” any other punctuation in the message but not included in the alphabet can also be handled by replacing the punctuation by a recognizable string before encryption (for example if % and & are included in the alphabet, any punctuation mark could be represented as “% string&” where “string” is a description of the punctuation mark and “%” and “&” are used exclusively as markers for non-standard punctuation; e.g. “%” could be replaced by “% percent&”; — could be replaced by “% ampersand&”; if “>” is not in the alphabet it could for example be replaced by “% greater than&”).

[0071] The one-time pad used to encrypt the message is made up of elements restricted to the same alphabet, and those values should be uniformly distributed within the one-time pad in that every symbol in the alphabet should appear with approximately equal probability in the one-time pad, independently of any other element of the one-time pad. Approximate uniformity should also be exhibited in any section of the one-time pad, regardless of the length of the section chosen (analogous to a pad generated from a truly random uniform sequence).

[0072] At Step 210, an alphabet of q different values is chosen. Whatever values are chosen, an integer representation is adopted, whereby the q values of the alphabet are represented by the integers [0, q−1] it is useful to define p=1+Int[log.sub.2 q], where Int[.Math.] denotes the integer part of the operand [n.Math.], This should ensure that 2.sup.p−1≤q<2.sup.p.

[0073] At step 212, a one-time pad is generated via an iterative algorithm, and each iteration proceeds as follows. Operations (a.) to (c.) below are depicted schematically in FIG. 2A, and a flowchart, of the operations is shown in FIG. 2B. The operations are repeated until a one-time pad of sufficient length has been generated (see below), starting with the first iteration n=1. [0074] (a.) Call the ACORN generator 150, as per Equation (2), using the chosen initialization to give an integer in the range [0, M−1). This integer is denoted by reference numeral 204 and is the vane Y.sub.kn, i.e. the n.sup.th value of the final derived sequence 108, as computed in the n.sup.th iteration. [0075] (b.) Divide the result Y.sub.kn by (M/2.sup.p) and take the integer part, to give an integer x in the range 0 to 2.sup.p−1. This is equivalent to retaining (sampling) only the p leading bits of Y.sub.kn (denoted by reference numeral 202), and discarding the remaining trailing bits (denoted by reference numeral 206). This is one form of “size reduction” operation, which reduces the value Y.sub.kn (of bit length log.sub.2 M) to a typically much smaller integer x (of bit length p). [0076] (c.) If x is less than or equal to q−1, output x as the next element of the one-time pad; else if x is greater than or equal to q, discard the value x. The effect of this is to discard any value of x that is outside of the alphabet. The algorithm then returns to (a), commencing the next iteration n+1.

[0077] The result x obtained in step (b.) is an example of a “reduced” pseudorandom number as that term is used herein—“reduced” in the sense of having a shorter bit length than the term Y.sub.kn from which it is derived, and derived in a way that preserves pseudo-randomness,

[0078] The effect of discarding terms outside the alphabet in step (c.) is to compute a “reduced” sequence—“reduced” in that the resulting sequence is shorter than the sequence that would be obtained if all terms were retained. For example, in the case that p=1+Int[log.sub.2 q] then, if q is a power of 2, q=2.sup.p-l and approximately half the terms will be discarded. This is merely an illustrative example, and there is no requirement for q to be a power of two. The techniques can be implemented with any suitable size of alphabet.

[0079] More generally, p could be defined as p=N+Int[log.sub.2 q] where N is a relatively small integer greater than or equal to 1. Increasing N means discarding a greater number of terms.

[0080] The overall effect of (b.) and (c.) is therefore to provide a reduced sequence of reduced pseudorandom numbers. Note that discarding any x value outside of the alphabet amounts to discarding any term Y.sub.kn of the final sequence which does not match any term of the alphabet (in the sense that the p leading bits of that term Y.sub.kn does not match any element of the alphabet). The operations performed at step (c.) therefore amount to selectively discarding terms of the final sequence 108 that do not match any element of the alphabet.

[0081] The seed s and the initial values (Y.sub.10, . . . , Y.sub.k0) selected in steps 202 to 208 are the “secret information” underpinning the encryption method. Rather than sharing/distributing the (potentially much larger) one-time pad, this secret information can be shared between any two or more parties who wish to communicate securely (i.e. the seed and the initial values may act as a shared secret between the parties, with each party deriving separately an instance of the one-time pad for the purpose of message encryption/description), or held by a single party in a non-communication context (e.g. a single party who encrypts and stored a message for later decryption by the same party).

[0082] The secret information allows the pad to be very easily reproduced assuming the alphabet and the modulus M are known. There is no particular requirement for the alphabet or the modulus M to be secret. Indeed, the alphabet can be determined from analysis of a sufficiently long cyphertext, and this is in no way detrimental to the security of the method. The modulus does not need to be kept secret to maintain secrecy of the encryption method. However, keeping the modulus secret would increase the security even further.

[0083] Without knowing the secret information, it is impossible to derive the secret information in a realistic period of time from a section of the one-time pad, irrespective of the length of the section available. The only way of deriving the secret information is by exhaustive testing of the possible secret information and the number of available alternative choices make this impossible with current computer hardware (even allowing for the speedup that may be obtained with quantum computers).

[0084] The method scales effectively to larger modulus increasing modulus e.g. from 2.sup.120 to 2.sup.240 is straightforward, and the only impact is a factor 2 increase in the pad generation time; by contrast, the resulting exhaustive search time will increase by a factor in excess of 2.sup.120—so the approach is future-proofed against all conceivable future computing hardware improvements.

[0085] In order to encrypt different messages, different sections of the same one-time pad can be used, provided that no section of the one-time pad is ever re-used (even in part).

[0086] Analysis of resulting one-time pads:

[0087] To illustrate the suitability of the above method to cryptography, some relevant analysis will now be provided.

[0088] The resulting one-time pad will eventually start to repeat itself, but has period length significantly greater than 2.sup.110, i.e. no such repetition will occur until the one-time pad has reached a length significantly greater than 2.sup.110. The inventor's analysis indicates the period to be 2.sup.123 for modulus 2.sup.120 and order 9 (for a more general discussion, see the “Periodicity and randomness” section. Before exhausting the period (i.e. reaching a length greater than the period), the one-time pad appears random and each term in the alphabet appears with approximately equal probability.

[0089] The total amount of data that can be encrypted using a single one-time pad (i.e. as generated from a single seed and a single set of initial values) is limited by the period of the one-time pad, as a consequence of the restriction on re-using any section of the one-time pad. However, the same one-time pad can be used to encrypt well in excess of 2.sup.110 data symbols, before a new set of secret information is required. This is a theoretical limit, as with a period in excess of 2.sup.110, it is impossible to exhaust the period in any practically conceivable period of time (for example, even generating 10.sup.9 or ˜2.sup.20 prn per second, it will take 2.5 centuries to generate 2.sup.60 prns, more than 3×10.sup.5 million years to generate 2.sup.90 . . . and effectively eternity to generate 2.sup.120 prns and/or to exhaust the available period of 2.sup.123.

[0090] A starting point in the pad for any particular message can be specified relative to the first value in the pad, counting front the start of the pad. The key point about a one-time pad is that one should never reuse a “page” (part) that has already been used. A party using the pad for encryption needs to keep track of any part of the pad that has already been used, and ensure that the next usage starts beyond the last entry that has already been used by them.

[0091] The party using the pad for encryption needs to share the order k, the modulus M, the seed s, the k initial values (all the preceding parameters can be shared once at the start of the process) and also the starting point in the pad (different for each particular message—and this can be shared at the same time as the message) with the party who is to use the pad for decryption.

[0092] The method provides a sufficient number of one-time pads to use a different pad for communication between every pair of computers currently in existence and still only use a miniscule proportion of the possible one-time pads that could be generated.

[0093] Assuming there to be some 7 billion people in the world today (8 billion ˜2.sup.33); hence some 2.sup.66 pairs of individuals. The proposed algorithm could generate a different one-time pad for every pair of people in the world, and no two pairs of people would need to use the same pad. A similar analysis could be applied to pairs of devices (including PCs, phones, and other electronic communications devices).

[0094] The method provides more than 2.sup.110 one-time pads (in fact there are inure than 2.sup.110 different seeds to choose from, and each choice of seed gives rise to many, many different one-time pads. The actual number is expected to exceed 2.sup.1000 in practice for a modulus of 2.sup.120. For any given order and modulus, the actual number is expected to be have magnitude approximating to k×M).

[0095] The one-time pads as generated above can be used for example in a Vernam cypher without compromising security of the messages. It has been believed up to now that using a software method to generate the pads is inherently insecure because it allows the possibility of an attacker being able to recreate the pad given knowledge of a sufficiently long section of the pad. The proposed method is resistant to such attacks, because of the huge number of different initialisations that are possible, and because the algorithm turns out to be inherently not susceptible to reverse-engineering the “secret information” from the contents of the pad.

[0096] Basing the one-time pads on the ACORN algorithm means that existing theoretical results concerning k-dimensional uniformity that already exist can be applied to the resulting one-time pads. Use of the ACORN algorithm allows very fast encryption/decryption; the method proposed guarantees security.

[0097] If k+1 consecutive terms from the ACORN sequences—i.e. the values Y.sub.kn, Y.sub.k,n+1, . . . , Y.sub.k,n+k . . . are known to full accuracy, then it is possible to reconstruct the entire ACORN sequence. Were the final ACORN sequence 108 to be used as a direct basis for the one-time pad, this underlying linearity of the ACORN method could be a potential source of weakness. However, this is avoided, as the linearity is effectively removed by the additional processing steps: the first part of the proposed method, i.e. step (b.) above, only uses a small number of high-order bits from each pin Y.sub.kn; the second part, i.e. step (c.), removes any resulting pills outside a specified range. Thus, the one-time pad only gives part of each of a selection of the numbers in the ACORN sequence, and there is no way of telling which numbers have been skipped (since no information is provided about them in the pad). This combination of two methods completely destroys the linearity of the underlying ACORN algorithm and ensures the process is not reversible. This is true even if the modulus M and the alphabet are known to an attacker.

[0098] Although it is considered preferable to apply both step (b.) and step (c.), either one of those steps, without the other, is sufficient to destroy the linearity of ACORN, and thus achieve the desired effect. Hence, in general, one or both of steps (b.) and (c.) may be applied.

Empirical Testing

Testing with TestU01

[0099] Extensive testing demonstrates that almost every choice of initialisation will give a sequence that passes all the TestU01 tests, provided the order k is sufficiently large (nine or greater) and the modulus a sufficiently large power of 2—testing has been performed with modulus of 2.sup.120, and this has been demonstrated to be sufficiently large to consistently pass all TestU01 tests. However, it is expected that sufficient randomness can be obtained with a smaller modulus. In general, the strength of the PRNG increases with the size of the modulus, and the level of strength required may be application specific (e.g. a larger modulus may he favoured in high-security applications such as diplomatic of military applications)

[0100] The inventor's tests have indicated that more than 2.sup.110 seeds (out of a total 2.sup.120 possible seeds) will consistently pass all the tests, assuming an odd seed s and all initial values set to zero. A significant proportion of the remaining seeds may well also pass all the tests, but they also include certain seeds that may give rise to failures—hence these other choices of seed are better avoided unless they have been individually tested. Note that 2.sup.110 is a conservative estimate—it is expected that the total number of viable seeds will, in fact, be closer to 2.sup.120.

[0101] Those tests have also indicated that, for these choices of seed, (almost) every initialisation will give a sequence that passes all the TestU01 tests; as an example, for order 9, this gives) (2.sup.120).sup.9=2.sup.1088 different choices of initial values for each seed, with each sequence of period 2.sup.12, implying 2.sup.965 possible sequences to choose from for each choice of seed. For larger values of the order there are correspondingly greater numbers of sequences to choose from.

[0102] In more formal terms, the tests performed by the inventors support the following conjectures, where as defined previously, for modulus M=2.sup.120, the seed is specified by four non-negative integer values, each strictly less than 2.sup.30 such that

s=(2.sup.90)s.sub.1+(2.sup.60)s.sub.2+(2.sup.30)s.sub.3+s.sub.4

[0103] Then:

[0104] Conjecture 1. For order k at least 9 and modulus 2.sup.120, a sufficient condition for the resulting ACORN sequence to pass all the TestU01 tests is that s.sub.1, s.sub.2 and s.sub.3 are each not equal to either zero or (2.sup.30−1) which means their binary representations are not all zeroes or all ones—and s.sub.4 takes an odd value. Initial values are assumed to be all equal to zero.

[0105] Conjecture 2. If seed, order and modulus satisfy the conditions for Conjecture 1, and initial values are assigned arbitrarily, then resulting ACORN sequence will pass all the TestU01 tests.

[0106] The results of the supporting tests for Conjecture 1 are summarized in Table 1 and Table 2 of “Annex A”. Conjecture 2 is supported by the results of the supporting tests for Conjecture 1, combined with the observation that for any choice of seed using non-zero initial values give rise to sequences that perform as well as (or better than) the sequence generated using the same seed and initial values all set to zero.

[0107] Table 1 summarises results from a first set of cases. The first number in each cell shows the number of failures while the second number (in brackets) shows the number of ‘suspect values’.

[0108] Following L'Ecuyer and Simard, a ‘failure’ is defined to be an individual test with a p-value less than or equal to 10.sup.−10 or greater than or equal to (1-10.sup.−10) and a ‘suspect value’ to be an individual test with p-value less than or equal to 10.sup.−4 or greater than or equal to (1-10.sup.−4).

[0109] Cases M100x do not satisfy the conditions for Conjecture 1 (apart from M1005, which does satisfy the conditions). Some cases result in one or more failures on TestU01.

[0110] Cases M101x have been assigned seed values selected arbitrarily but which do satisfy all the conditions. All cases have zero failures; a small proportion have one or two suspect values but this is to be expected even with a truly random sequence.

[0111] Cases M105x, M106x, M107x and M108x have just one non-zero bit in the binary representations of s1, s2 and s3 and no more than two non-zero bits in the binary representation of s4 (i.e. they just satisfy the conditions of the conjecture). All cases have zero failures; a small proportion have one or two suspect values but this is to be expected even with a truly random sequence.

[0112] Table 2 summarises results obtained to date (as at January 2020) from a second set of cases. As in Table 1, the first number in each cell shows the number of failures while the second number (in brackets) shows the number of suspect values.

[0113] The seed for Case N10xx is chosen such that seed values for Case N10xx and Case M10xx sum in each case to 2.sup.120. This means that ones and zeroes are switched in the binary representations except. for the last binary digit which is one in each case. The resulting sequences (after scaling to the unit interval) will always sum to 1.

[0114] The result of testing on Case N10xx is expected to be virtually identical to the corresponding case M10xx, and this is indeed the case. There is some small variation in the occurrence of suspect values but corresponding cases always either pass all the tests or have almost identical numbers of failures.

[0115] The results included in Tables 1 and 2 cover generators with order up to 25. Further testing has been undertaken with larger order generators, up to order 100 and more. The results for the larger order generators appear very similar to those already included in the Tables 1 and 2 for order between 15 and 25.

Periodicity and Randomness

[0116] As noted above, whilst it is convenient to choose a modulus that is a power of two, it is not essential to do so. Two considerations pertaining to the choice of modulus are (a) the periodicity of the resulting sequences (a long period is desirable for the reasons discussed above) and (b) randomness of the resulting sequences.

[0117] With regards to periodicity, “Annex B” sets out a proof of periodicity for any choice of modulus. in brief, this proves the period of the resulting ACORN sequences to increase with the size of the modulus in accordance with “THEOREM 1” of Annex B. The theorem is proved for any arbitrary modulus expressed as a composite of prime powers:

[00001]$M=\stackrel{s}{\underset{r=1}{.Math.}}{\left(q_r\right)}^{t_r},$

where each q.sub.r is a different prime. With a modulus that is a prime power, this reduces to M=q.sub.1.sup.t.sup.1 , and in the above examples of M=2.sup.120, q.sub.1=2 and t.sub.1=120. With modulus of 2.sup.120 and k=9, the period length of 2.sup.123 mentioned above follows from equation (11) and (12) of Annex B.

[0118] However, the proof of periodicity holds for any choice of modulus (both prime powers and composite). A composite modulus gives longer period length, but may give poorer randomness properties in certain circumstances; in particular choosing the modulus to he multiple of different primes (each to power one) gives maximal period but poor randomness (some failures on specific tests with TestU01). This can, however, be avoided by ensuring that at least one prime factor of a composite modulus is sufficiently large, i.e. that q.sub.r is large for at least one r (unwanted structure in the final result can arise from the use of a composite modulus where no individual prime factor is raised to a sufficiently large power, even if the modulus itself is large).

[0119] With regards to the requirement for randomness, ACORN generators have been proved to have good convergence properties for power of two modulus. See R. S. Wikramaratna, “Theoretical and Empirical Convergence Results for Additive Congruential Random Number Generators”, J. Comput. Appl. Math., 233, pp 2302-2311, 2010, which is incorporated herein by reference in its entirety. The results demonstrate convergence in that, for any sufficient value of the order, the resulting sequences will be longer and better approximate to ‘random, uniformly distributed on the unit interval’ as the modulus takes increasing powers of 2.

[0120] Hence, another benefit of using powers of two is that convergence has already been demonstrated for powers of two. Hence, for a power of two modulus, as the size of the modulus increases, it is known that both that the period will increase (as the more general periodicity theorem applies) and that the randomness will increase (by virtue of the known convergence results), without needing further verification. In a practical implementation, it may, therefore, be most convenient to choose a power of two modulus that is sufficiently large to achieve a desired period.

[0121] However, it is emphasised that the methodology is not limited in this respect. Although the above convergence results apply to a modulus of power two, different forms of modulus (such as powers of other primes, e.g. 3, 5 etc. or composite moduli) may be equally viable. Whether or not any given modulus provides sufficient randomness can be verified through empirical testing. For example, such testing has indicated that a modulus equal to r! (r factorial) for a sufficiently large r also yields acceptable results.

Example Application—Secure Communications

[0122] FIG. 3 shows a signalling diagram for an example method proposed for secure encryption of any text or binary file. The method considers two parties, Alice (encrypting party) and Bob (decrypting party).

[0123] A key distribution service (KDS) has the role of determining the initialization, and distributing it to Alice and Bob. The KDS could be a trusted “third party”, but the role of the KDS could also be assumed by Alice or Bob, who distributes the necessary information to the other, i.e. the described function of the KDS could be performed by Alice, Bob or a third party. Whilst described in relation to two parties, the description applied to any two or more parties who wish to communicate securely.

[0124] The initialization and the alphabet are rendered available to Alice and Bob at steps 302A and 302B respectively. This means sharing the order k, the modulus M, the seed s, the k initial values and the size and contents of the alphabet between all parties. This information can be shared by any appropriate secure method and could be done off-line (e.g. agreed in advance, or shared using a secure route or an agreed method); it should not be shared further with anybody else.

[0125] At steps 304A and 304B respectively, Alice and Bob separately compute one-time pads using the shared initialization and alphabet, by applying the above steps. Because of the reproducibility of the method, those one-time pads will be identical.

[0126] At step 306, Alice chooses a starting point y in the pad to he used for the current message. This can be the start of the one-time pad for the first message encrypted with the one-time pad, but for any subsequent message, the starting point y should be beyond the last point already used.

[0127] At step 308, Alice encrypts a message to be sent to Bob using the one-time pad and the determined start point y: Alice takes the message (assumed to only contain characters included in the alphabet) and encrypts first character by “cycling” t places to the right in the alphabet where t is the value at the starting point y in the pad. In other words, the first character is encrypted by computing the mod-q sum of the integer representation of that character with the value t of element y in the one-time pad. Similarly, the second and subsequent characters are using y+1 and subsequent element of the pad; keeping a record of the last value used so that next message can be guaranteed to use a different, unused section of the pad.

[0128] Note that, whereas the large modulus M is used within the PRNG to generate the one-time pad, encryption is performed with respect to the modulus q where q is the size of the alphabet.

[0129] The encrypted message will look like a random string of characters in the alphabet. There is no way of telling whether an apparently random string is simply a part of the one-time pad, or contains an encrypted message.

[0130] For example, the message may read:

[0131] HELLO

which can be converted into numerical values by transforming each letter of the alphabet into the numerical value of its location in the alphabet. That is, A=0, B=1, . . . , Z=25, as shown in the table below.

TABLE-US-00001 A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25

[0132] The message 506 can therefore be represented as a sequence of numerical values:

7, 4, 11, 11, 14.

[0133] As an example, say the first five terms of the one-time pad are:

23, 5, 16, 2, 21.

[0134] The message can be transformed by the modular addition of corresponding terms, the modulus being q=26:

(7+23) mod 26, (4+5) mod 26, (11+16) mod 26, (11+2) mod 26, (14+21) mod 26
=4, 9, 1, 13, 9
=E J B N J (the encrypted message).

[0135] At step 310, Alice sends the encrypted message to the Bob, together with the starting point y in the pad. The message is decrypted (Step 312) by Bob simply reversing the encryption algorithm, starting at the correct place y in Bob's identical one-time pad.

[0136] As will be appreciated, the names Alice and Bob are merely convenient labels with no implication as to the nature of the parties involved. In many practical contexts, Alice and Bob's steps will be performed by suitably-configured computer devices. To the extent any human input is involved, in many cases this may be restricted to the formation of the plaintext message to be encrypted, with the actual encryption and decryption steps being performed by the devices involved. For example, those functions may be implemented in software executed on the respective devices.

[0137] Widespread use of such methods effectively increases the security of such communications.

[0138] As an additional security measure, Alice could for example send 10 different “messages” most of which are just sections of the pad (or contain an obviously meaningless string of plaintext); an attacker would need to attempt to decrypt all of them to know whether any of them are meaningful. If none of the “messages” is amenable to cryptanalysis the attacker is in danger of just spending time trying to analyse effectively “random” sequences.

[0139] There is no way for an attacker to distinguish between a section of the pad and a cyphertext (since both appear to be random strings). By contrast, the intended recipient knows the correct initialisation and simply needs to decrypt each string and see whether the result is meaningful or not.

[0140] Messages can be communicated using any suitable channel. For example, Alice could post one or more web pages that may contain messages for particular “agents”, where a different set of secret information is shared with each agent. Each agent attempts to decrypt each message using his “secret information”; he will see any messages intended for him; all other pages will fail to decrypt. An attacker would not know how many of the pages contain messages nor which agent they were intended for, unless they knew each agent's “secret information”. Such a page could be posted daily, but only send a message occasionally. An attacker would never know if there is a message actually being sent, as opposed to simply, random “noise”.

[0141] One page could he posted which contains messages for a number of different agents at different places on the page. Each agent will see a meaningful message at the relevant section of the page (assuming there is a message intended for him). An attacker would not be able to see any of the messages unless he knows each set of “secret information”.

[0142] A section of “random” text (standard length, e.g. 80 characters, or 200 characters, or longer) at the foot of every email exchanged with an agent; an attacker would have no idea whether any particular mail included just random noise or a real message. If all (or a significant proportion) of email messages contained similar random strings there would be no information to be gained even by analysing which pairs of email addresses were including such strings.

[0143] One set of “secret information” could be used for messages going in each direction, or Alice could share one set and divide the pad into blocks of standard length which are used alternately for messages going in each direction.

[0144] The method can be used in real time for sharing intelligence and/or orders with a field agent. Without knowing all the relevant “secret information” it is impossible for an eavesdropper to know anything about what is being communicated.

[0145] By way of example, one practical application could use the method for transmitting data collected at a remote location (such as an oil rig, oil drilling platform, seismic logging facility, offshore windfarm etc.) to a central data processing or storage and distribution facility.

[0146] The method can be used for distributing large files in a secure manner to a purchaser. The encrypted files can be transferred to the would-be purchaser in advance of payment. On confirmation of both the file transfer and the payment the secret information can be shared with the purchaser who can then decrypt and read the contents of the file.

[0147] At the hardware level, the steps or functionality of the present disclosure may be implemented using a range of computer architectures. A computer system may comprise one or more computers, which in turn may comprise programmable and/or non-programmable processing hardware. Examples of programmable processing hardware include a CPU or CPUs, GPU(s)/accelerator processor(s) or any other general-purpose/instruction-based processor(s). In such cases, the method steps, algorithms, functions, functional components etc. disclosed herein may be encoded in computer-readable instructions embodied in transitory or non-transitory computer-readable media, and carried cut/implemented though execution of those instructions on an instruction-based processor(s). Examples of non-transitory media include magnetic, solid-state and optical storage. Another example of programmable hardware is a processor(s) in the form of an FPGA(s) (field-programmable gate array) whose circuit. configuration may be programmed via circuit description code and the like. Non-programmable hardware includes, for example, a non-programmable processor(s) in the form of an ASIC(s) (application-specific integrated circuit). In general, a computer, processor and the like may be formed of any type or combination of programmable and/or non-programmable, hardware configured to carry out any of the steps or implement any of the functionality disclosed herein. The terms computer program and program code encompass computer-readable instructions, circuit description code and the like for programming a programmable computer system to carry out such steps or implement such functionality.

ANNEX A—SUMMARY OF TEST RESULTS

[0148]

TABLE-US-00002 TABLE 1 Modulus 2{circumflex over ( )}120 Seed = s1*2{circumflex over ( )}90 + s2*2{circumflex over ( )}60 + s3*2{circumflex over ( )}30 + s4 Initial values all zero Seed Seed Seed Seed Order Order Order Order Order s1 s2 s3 s4 8 9 10 11 12 M1000 Not used M1001 0 0 0 1 34 (1)  21 (6)  5 (0) 1 (0) 1 (0) M1002 Not used M1003 0 0 1 1 22 (2)  5 (0) 0 (1) 0 (0) 0 (0) M1004 0 1 1 1 4 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1005 1 1 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1006 0 1 0 1 4 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1007 1 0 0 1 5 (0) 1 (0) 0 (0) 0 (0) 0 (0) M1008 1 0 1 1 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1009 1 1 0 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1010 9 77 555 3333 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1011 3333 555 77 9 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1012 11062019 12101955 30122017 29012019 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) M1013 29012019 30122017 12101955 11062019 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1014 12345 6789 98765 4321 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1015 4321 98765 6789 12345 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1016 12345 34567 56789 98765 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1017 98765 56789 34567 12345 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1018 1 1 1 731 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1019 731 1 1 1 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) M1005 1 1 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1050 2 1 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1051 4 1 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1052 8 1 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1053 32 1 1 1 1 (0) 0 (0) 0 (0) 0 (1) 0 (0) M1054 1024 1 1 1 1 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1055 1048576 1 1 1 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1056 33554432 1 1 1 3 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1057 134217728 1 1 1 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1058 268435456 1 1 1 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1059 536870912 1 1 1 3 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1060 1 2 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1061 1 4 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1062 1 8 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1063 1 32 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1064 1 1024 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1065 1 1048576 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1066 1 33554432 1 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1067 1 134217728 1 1 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1068 1 268435456 1 1 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1069 1 536870912 1 1 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1070 1 1 2 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1071 1 1 4 1 0 (0) 0 (0) 0 (0) 0 (2) 0 (0) M1072 1 1 8 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1073 1 1 32 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1074 1 1 1024 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1075 1 1 1048576 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1076 1 1 33554432 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1077 1 1 134217728 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1078 1 1 268435456 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1079 1 1 536870912 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1080 1 1 1 3 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1081 1 1 1 5 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1082 1 1 1 9 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) M1083 1 1 1 33 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1084 1 1 1 1025 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1085 1 1 1 1048577 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1086 1 1 1 33554433 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1087 1 1 1 134217729 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1088 1 1 1 268435457 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1089 1 1 1 536870913 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) Seed Seed Seed Seed Order Order Order Order Order s1 s2 s3 s4 8 9 10 11 12 Order Order Order Order Order Order Order Order Order Order Order Order Order 13 14 15 16 17 18 19 20 21 22 23 24 25 M1000 M1001 1 (0) 1 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1002 M1003 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1004 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1005 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1006 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (1) M1007 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) M1008 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1009 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (1) 0 (0) M1010 0 (0) 0 (1) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1011 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1012 0 (0) 0 (2) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) M1013 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1014 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1015 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1016 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1017 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1018 0 (0) 0 (0) 0 (1) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1019 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1005 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1050 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1051 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1052 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1053 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1054 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1055 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1056 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1057 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1058 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1059 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1060 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1061 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1062 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1063 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1064 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1065 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1066 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1067 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1068 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1069 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1070 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1071 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1072 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) M1073 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1074 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1075 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1076 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1077 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1078 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1079 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1080 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (1) 0 (0) 0 (0) 0 (0) M1081 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1082 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1083 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) M1084 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1085 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1086 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1087 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) M1088 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) M1089 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (2) 0 (0) 0 (0) Order Order Order Order Order Order Order Order Order Order Order Order Order 13 14 15 16 17 18 19 20 21 22 23 24 25

TABLE-US-00003 TABLE 2 Modulus 2{circumflex over ( )}120 Seed = s1*2{circumflex over ( )}90 + s2*2{circumflex over ( )}60 + s3*2{circumflex over ( )}30 + s4 Initial values all zero Seed Seed Seed Seed Order Order Order Order Order s1 s2 s3 s4 8 9 10 11 12 N1000 Not used N1001 1073741823 1073741823 1073741823 1073741823 34 (1)  21 (5)  5 (0) 1 (0) 1 (0) N1002 Not used N1003 1073741823 1073741823 1073741822 1073741823 22 (2)  5 (0) 0 (0) 0 (0) 0 (0) N1004 1073741823 1073741822 1073741822 1073741823 4 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1005 1073741822 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1006 1073741823 1073741822 1073741823 1073741823 4 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1007 1073741822 1073741823 1073741823 1073741823 5 (0) 1 (0) 0 (0) 0 (0) 0 (0) N1008 1073741822 1073741823 1073741822 1073741823 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1009 1073741822 1073741822 1073741823 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1010 1073741814 1073741746 1073741268 1073738491 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1011 1073738490 1073741268 1073741746 1073741815 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) N1012 1062679804 1061639868 1043619806 1044729805 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1013 1044729804 1043619806 1061639868 1062679805 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1014 1073729478 1073735034 1073643058 1073737503 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1015 1073737502 1073643058 1073735034 1073729479 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1016 1073729478 1073707256 1073685034 1073643059 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1017 1073643058 1073685034 1073707256 1073729479 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1018 1073741822 1073741822 1073741822 1073741093 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1019 1073741092 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1005 1073741822 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1050 1073741821 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1051 1073741819 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1052 1073741815 1073741822 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1053 1073741791 1073741822 1073741822 1073741823 1 (0) 0 (0) 0 (0) 0 (1) 0 (0) N1054 1073740799 1073741822 1073741822 1073741823 1 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1055 1072693247 1073741822 1073741822 1073741823 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1056 1040187391 1073741822 1073741822 1073741823 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1057 939524095 1073741822 1073741822 1073741823 3 (0) 0 (0) 0 (0) 0 (1) 0 (0) N1058 805306367 1073741822 1073741822 1073741823 3 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1059 536870911 1073741822 1073741822 1073741823 3 (1) 0 (0) 0 (0) 0 (0) 0 (0) N1060 1073741822 1073741821 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1061 1073741822 1073741819 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1062 1073741822 1073741815 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1063 1073741822 1073741791 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1064 1073741822 1073740799 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1065 1073741822 1072693247 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1066 1073741822 1040187391 1073741822 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1067 1073741822 939524095 1073741822 1073741823 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1068 1073741822 805306367 1073741822 1073741823 2 (0) 0 (0) 0 (1) 0 (0) 0 (0) N1069 1073741822 536870911 1073741822 1073741823 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1070 1073741822 1073741822 1073741821 1073741823 0 (1) 0 (0) 0 (0) 0 (0) 0 (1) N1071 1073741822 1073741822 1073741819 1073741823 0 (0) 0 (0) 0 (0) 0 (2) 0 (0) N1072 1073741822 1073741822 1073741815 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1073 1073741822 1073741822 1073741791 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1074 1073741822 1073741822 1073740799 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1075 1073741822 1073741822 1072693247 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1076 1073741822 1073741822 1040187391 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1077 1073741822 1073741822 939524095 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1078 1073741822 1073741822 805306367 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1079 1073741822 1073741822 536870911 1073741823 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1080 1073741822 1073741822 1073741822 1073741821 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1081 1073741822 1073741822 1073741822 1073741819 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1082 1073741822 1073741822 1073741822 1073741815 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1083 1073741822 1073741822 1073741822 1073741791 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) N1084 1073741822 1073741822 1073741822 1073740799 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1085 1073741822 1073741822 1073741822 1072693247 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1086 1073741822 1073741822 1073741822 1040187391 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1087 1073741822 1073741822 1073741822 939524095 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1088 1073741822 1073741822 1073741822 805306367 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1089 1073741822 1073741822 1073741822 536870911 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) Seed Seed Seed Seed Order Order Order Order Order s1 s2 s3 s4 8 9 10 11 12 Order Order Order Order Order Order Order Order Order Order Order Order Order 13 14 15 16 17 18 19 20 21 22 23 24 25 N1000 N1001 1 (0) 1 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1002 N1003 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1004 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1005 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1006 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1007 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) N1008 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1009 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1010 0 (0) 0 (1) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1011 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1012 0 (0) 0 (2) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (1) 0 (0) 0 (0) 0 (0) N1013 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1014 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1015 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) N1016 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1017 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1018 0 (0) 0 (0) 0 (0) 0 (1) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1019 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1005 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) N1050 0 (0) 0 (0) 0 (0) N1051 0 (0) 0 (0) 0 (0) N1052 0 (0) 0 (0) 0 (0) N1053 0 (0) 0 (0) 0 (0) N1054 0 (0) 0 (0) 0 (0) N1055 0 (0) 0 (0) 0 (0) N1056 0 (0) 0 (0) 0 (0) N1057 0 (0) 0 (0) 0 (0) N1058 0 (0) 0 (0) 0 (0) N1059 0 (0) 0 (0) 0 (0) N1060 0 (0) 0 (0) 0 (0) N1061 0 (0) 0 (0) 0 (0) N1062 0 (0) 0 (0) 0 (0) N1063 0 (0) 0 (0) 0 (0) N1064 0 (0) 0 (0) 0 (0) N1065 0 (0) 0 (0) 0 (0) N1066 0 (0) 0 (0) 0 (0) N1067 0 (0) 0 (0) 0 (0) N1068 0 (0) 0 (0) 0 (0) N1069 0 (0) 0 (0) 0 (0) N1070 0 (0) 0 (0) 0 (0) N1071 0 (0) 0 (0) 0 (0) N1072 0 (0) 0 (0) 0 (0) N1073 0 (0) 0 (0) 0 (0) N1074 0 (0) 0 (0) 0 (0) N1075 0 (0) 0 (0) 0 (0) N1076 0 (0) 0 (0) 0 (0) N1077 0 (0) 0 (0) 0 (0) N1078 0 (0) 0 (0) 0 (0) N1079 0 (0) 0 (0) 0 (0) N1080 0 (0) 0 (0) 0 (0) N1081 0 (0) 0 (0) 0 (0) N1082 0 (0) 0 (0) 0 (0) N1083 0 (0) 0 (0) 0 (0) N1084 0 (0) 0 (0) 0 (0) N1085 0 (0) 0 (0) 0 (0) N1086 0 (0) 0 (0) 0 (0) N1087 0 (0) 0 (0) 0 (0) N1088 0 (0) 0 (0) 0 (0) N1089 0 (0) 0 (0) 0 (0) Order Order Order 13 14 15

ANNEX B

OVERVIEW—THE ACORN GENERATOR

[0149] Let k be a finite, strictly positive integer. As described above, the k-th order Additive Congruential Random Number (ACORN) generator is defined by Wikramaratna [1, 2] from an integer modulus M, an integer seed Y.sup.0.sub.0 satisfying 0<Y.sup.0.sub.0<M and an arbitrary set of k integer initial values Y.sup.m.sub.0, m=1, . . . , k, each satisfying 0≤Y.sup.m.sub.0<M by the equations

Y.sup.0.sub.n=Y.sub.n−1.sup.0 n≥1   (B-1)

Y.sup.m.sub.n=[Y.sup.m−1.sub.n+Y.sup.m.sub.n−1].sub.mod M n≥1, m=1, . . . , k   (B-2)

where by [Y].sub.mod M we mean the remainder on dividing Y by M. In what follows, we will make use of some standard properties of modular arithmetic and congruences; if required, the reader can refer to a textbook on Number Theory for further exposition on these topics. In this Annex we will sometimes use a compressed notation where the use of square brackets around a vector or matrix means that each individual component of the relevant vector or matrix is evaluated and the result taken modulo M.

[0150] Finally, the sequence of numbers Y.sup.k.sub.n can be normalised to the unit interval by dividing by M

X.sup.k.sub.n=Y.sup.k.sub.n/M n≥1   (B-3)

[0151] It turns out that the numbers X.sup.k.sub.n defined by equations (B-1) (B-3) approximate to being uniformly distributed on the unit interval in up to k dimensions, provided a few simple constraints on the initial parameter values are satisfied.

[0152] The original implementation proposed in [1] used real arithmetic modulo one, calculating the X.sup.k.sub.n directly. This implementation suffered from a number of conceptual and practical limitations (in particular, the sequences generated with any specific initialisation could not be guaranteed reproducible on different hardware or with different compilers, although the statistical properties of the sequences were unaffected) which could be overcome [2] through the use of the integer implementation based on equations (B-1)-(B-3). Theoretical analysis given by Wikramaratna [2] has shown that the numbers Y.sup.m.sub.n are of the form

[00002]$\begin{array}{cc}{Y}_n^m={\left[\underset{i=0}{\overset{m}{.Math.}}{Y}_0^i{Z}_n^{m-i}\right]}_{\mathrm{mod}M}& \left(B-4\right)\end{array}$

where for any integer values of a (non-negative) and b (positive) we define Z.sup.a.sub.b by

[00003]$\begin{array}{cc}{Z}_b^a=\frac{\left(a+b-1\right)!}{a!\left(b-1\right)!}& \left(B-5\right)\end{array}$

[0153] The following sections of the present Annex are devoted to the development of some relevant background, followed by the statement and proof of a theorem concerning the periodicity of ACORN sequences having arbitrary modulus, where the seed is chosen such that it is relatively prime with the modulus.

[0154] The theorem proved in this Annex covers not only cases where the modulus is either a prime number or a prime raised to an integer power, but also extends the result to the general case where the modulus has two or more distinct prime factors, each raised to a (possibly different) integer power.

MATRIX FORMS OF ACORN EQUATIONS

[0155] It should be observed that there is more than one way in which the ACORN equations (B-1)-(B-3) can be represented in matrix form. The form that will be adopted in this Annex is particularly well suited to the analysis of periodicity and specifically to the proof of the theorem below. However, it is different from the form of the equations that was adopted in [3] and [4], where the ACORN generator was viewed as a special case of a multiple recursive generator—this required a matrix of size k by k (rather than k+1 by k+1 as in equation (B-7) of this Annex) and different structure and leads to a matrix with different properties. In particular we note that in [3] the resulting matrix turned cut to be centro-invertible (which means [4] that its inverse can be found simply by reversing the order of both the rows and columns of the matrix, equivalent to rotating all elements of the matrix through 180° about the mid-point of the matrix). It will be clear from an inspection of equation (B-7) below that this is not the case with the matrix form of the equations that is considered in this Annex.

[0156] For any given value of k, define L.sub.k to be the (k+1) by (k+1) lower triangular matrix with all entries equal to 1 both on the diagonal and in the lower triangle, while all entries in the upper triangle are equal to zero. Let y.sub.n be the (k+1) vector with i-th component equal to [Y.sup.i−1.sub.n]. Equations (B-1) and (B-2) for a k-th order ACORN generator can then be rewritten in matrix form as follows

[00004]$\begin{array}{cc}{{y_n-(Y_n^0]}_{\mathrm{mod}M},{\left[Y_n^1\right]}_{\mathrm{mod}M},.Math.,{\left[Y_n^k\right]}_{\mathrm{mod}M})}^T={\left[L_k{y}_{n-1}\right]}_{\mathrm{mod}M}=.Math.={\left[L_k^n{y}_0\right]}_{\mathrm{mod}M}& \left(B-6\right)\end{array}$

[0157] We observe that for each k the matrix L.sub.k is an inevitable matrix with determinant equal to 1; its inverse is the (k+1) by (k+1) lower triangular matrix with all entries equal to 1 on the diagonal, equal to −1 on the lower “off-diagonal” with unit offset, while all remaining entries in the lower triangle and all entries in the upper triangle are equal to zero. For example, for k=3

[00005]$\begin{array}{cc}{L}_3=\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right){\left(L_3\right)}^{-1}=\left(\begin{array}{cccc}1& 0& 0& 0\\ -1& 1& 0& 0\\ 0& -1& 1& 0\\ 0& 0& -1& 1\end{array}\right)& \left(B-7\right)\end{array}$

[0158] If we write

[L.sub.k.sup.n].sub.mod M=(L.sub.k, l, p, q.sup.n)   (B-8)

where on the right hand side of this equation the terms

[00006]$L_{k\left(p,q\right)}^n$

represent the individual components of the matrix (modulo M), where the indices k and n identify the matrix which is being considered and the power to which it is raised and the subscript terms (p, q) are respectively the row and column indices, each running from 1 to (k+1); then, comparing terms between equations (B-4), (B-6) and (B-8), we obtain

[00007]$\begin{array}{cc}\begin{array}{c}{L}_{k\left(p,q\right)}^n=0\mathrm{if}p<q\\ L_{k\left(p,q\right)}^n={\left[Z_{p-q+1}^{n-1}\right]}_{\mathrm{mod}M}={\left[Z_n^{p-q}\right]}_{\mathrm{mod}M}\\ ={\left[\frac{\left(n+p-q-1\right)!}{\left(p-q\right)!\left(n-1\right)!}\right]}_{\mathrm{mod}M}\mathrm{if}p\ge q\end{array}& \left(B-9\right)\end{array}$

where the meaning of Z.sup.a.sub.b is as defined previously in equation (B-5). it should be noted that the right hand side of equation (B-9) is a function of (p-q), so that each matrix (L.sub.k).sup.n is a lower triangular matrix with constant values along the diagonal (equal to 1) and with a (different) constant value along each lower off-diagonal with fixed offset.

PERIOD LENGTH FOR ACORN SEQUENCES

[0159] THEOREM 1. Let X.sup.k.sub.n be a k-th order ACORN sequence, defined by equations (B-1)-(B-3), with modulus

[00008]$\begin{array}{cc}M=\stackrel{s}{\underset{r=1}{.Math.}}{\left(q_r\right)}^{t_r}& \left(B-10\right)\end{array}$

where each q.sub.r is a prime (ordered such that q.sub.r<q.sub.r+1), each t.sub.r is a positive integer and suppose that the seed and modulus are chosen to be relatively prime. Then the sequence X.sup.k.sub.n, k=1, . . . , n will have a period length equal to

[00009]$\begin{array}{cc}P=\underset{r=1}{\overset{s}{.Math.}}{\left(q_r\right)}^{i_r}M& \left(B-11\right)\end{array}$

where for each r, i.sub.r the largest integer such that

(q.sub.r).sup.i.sup.r≤k   (B-12)

Proof

[0160] The proof is in two parts.

[0161] (i) In the first part it is proved that, provided the seed and modulus are relatively prime, then a necessary and sufficient condition for the period to be N is that [L.sub.k.sup.N].sub.modM=I (where I is the k+1 by k+1 identity matrix) and [L.sub.k.sup.n].sub.modM≠I for any n<N.

[0162] The sufficiency of this condition is obvious: from equation (B-6) we obtain

y.sub.N+r=[L.sub.k.sup.N].sub.mod My.sub.r=Iy.sub.r=y.sub.r   (B-13)

[0163] This holds for all r and N is the smallest value for which it holds, which is the definition of the period length.

[0164] Necessity is also clear. Suppose (assumption A) that [L.sub.k.sup.N].sub.modM‥I; we know from (B-9) that L.sub.k(1,1).sup.N=1 and there must he at least one other non-zero element in the first column of [L.sub.k.sup.N].sub.modM (if not, this would contradict assumption A—since each lower off-diagonal has constant values),

[0165] Suppose that the second non-zero element is in row t, so that L.sub.k(t,1).sup.N is the second non-zero element in the first column of the matrix. From an inspection of equation (B-9) it can he seen that in this case the t-th row of the matrix can have only two non-zero elements; thus if we write Y.sup.t−1.sub.0 for the t-th element of the vector yo then in this case the t-th row of the matrix equation (B-6) reduces to

(B-14)

and since the terms on the diagonal are all equal to 1, this in turn requires

(B-15)

[0166] Remembering that this equation must be satisfied modulo and that the seed Y.sup.0.sub.0 and the modulus are relatively prime, this equation can only be satisfied if L.sub.k(i,1).sup.N divisible by M and therefore equal to zero modulo M. This contradicts assumption A, proving that the condition [L.sub.k.sup.N].sub.modM=I is necessary.

[0167] This completes the first part of the proof.

[0168] (ii) In the second part of the proof we will use mathematical induction on the order of the generator, together with the result of the first part of the proof, to prove the theorem.

[0169] Consider first the cases where p−q=1 (when k=1 this means that p=2 and q=1)

Z.sup.1.sub.n=n   (B-16)

[0170] Choosing n=M is the smallest solution with equation (B-16) equal to zero modulo M. Hence the period for a first-order ACORN sequence must he equal to M, provided that the seed and the modulus are relatively prime. This proves the theorem for k=1.

[0171] Now suppose that the theorem holds for all k less than or equal to K. Suppose that the period length for the K-th order sequence is n.sub.KM. Then the theorem will be proved if we can show that (a) n.sub.K+1 is equal to Pn.sub.K whenever K+1 is a power of a prime P which is a factor of M; (b) n.sub.K+1 is equal to n.sub.K whenever K+1 is a power of a prime P which is not a factor of M; (c) n.sub.K+1 is equal to n.sub.K whenever K+1 is a composite number, ie has two or more different prime factors which may each be raised to any integer power greater than or equal to 1. We will consider each of these cases separately in the relevant, paragraphs below.

[0172] We know that (K+1) can he written in the form (K+1)=ab where all the prime factors of a are also prime factors of M and where b and M are relatively prime (and where we allow the possibility that either a orb may be equal to 1; we observe that they cannot both be 1 by the induction hypothesis).

[0173] Let T be a positive integer. We can write

[00010]$\begin{array}{cc}\begin{array}{c}{Z}_{{\mathrm{Tn}}_{K}M}^{K=1}=\frac{\left({\mathrm{Tn}}_{K}M+K\right)!}{\left(K+1\right)!\left({\mathrm{Tn}}_{K}M-1\right)!}\\ =\frac{\left({\mathrm{Tn}}_{K}M\right)\left({\mathrm{Tn}}_{K}M+1\right).Math.\left({\mathrm{Tn}}_{K}M+K\right)}{\left(K+1\right)!}\\ =\frac{\left(T{n}_{K}M\right)}{\left(K+1\right)}\frac{\left({\mathrm{Tn}}_{K}M+1\right).Math.\left({\mathrm{Tn}}_{K}M+K\right)}{K!}\\ =\frac{\left(T{n}_{K}M\right)}{\left(K+1\right)}{Z}_{n_{K}M+1}^K=\frac{{\mathrm{Tn}}_{K}M}{a}\frac{Z_{n_{K}M+1}^K}{b}\end{array}& \left(B-17\right)\end{array}$

[0174] This equation holds for any integer value of T, and clearly still holds if both sides are evaluated modulo M. [0175] (a) Suppose K+1 is a power of a prime, and the prime (which we shall call P) is a factor of M. [0176] By assumption, this requires b=1. By the induction hypothesis, we know that [Z.sup.K.sub.n.sub.k.sub.M+1].sub.mod M=[Z.sup.K.sub.1].sub.mod M=1 and so in this case equation (B-17), when evaluated modulo M, reduces to

[00011]$\begin{array}{cc}{\left[Z_{{\mathrm{Tn}}_{K}M}^{K+1}\right]}_{\mathrm{mod}M}={\left[\frac{\left({\mathrm{Tn}}_{K}M\right)}{a}\right]}_{\mathrm{mod}M}& \left(B-18\right)\end{array}$ [0177] By the induction hypothesis when K+1 is a prime power, n.sub.K is divisible by a/P, but not by a (since K+1=a=P.sup.t for some integer t, the largest power of P less than or equal to K must be P.sup.t−1=a/P). Hence T=P is the smallest value of T such that equation (B-18) is equal to zero. We have shown that in this case n.sub.K+1=Pn.sub.K, as required for the theorem. [0178] (b) Now suppose K+1 is a power of a prime (which we shall again call P), but the prime is not a factor of the modulus M. [0179] in this case a=1 and b has just a single prime factor raised to some power. Suppose we put z=1 and also set T=1 in equation (B-17)

[00012]$\begin{array}{cc}\begin{array}{c}{Z}_{n_{K}M}^{K+1}=\frac{\left(n_{K}M\right)}{\left(K+1\right)}{Z}_{n_{K}M+1}^K\\ =n_{k}M\left(\frac{Z_{n_{K}M+1}^K}{b}\right)\end{array}& \left(B-19\right)\end{array}$ [0180] The left hand side of this equation (B-19) is a binomial coefficient and hence it must be an integer. We know by its definition that b does not have any factors in common with either M or nK, so therefore it follows that the final term in brackets on the right hand side of equation (B-19) must also be an integer. Hence it follows that

[00013]$\begin{array}{cc}{\left[Z_{n_{K}M}^{K+1}\right]}_{\mathrm{mod}M}={\left[n_{K}M\frac{Z_{n_{K}M+1}^K}{b}\right]}_{\mathrm{mod}M}=0& \left(B-20\right)\end{array}$ [0181] Therefore we have shown that in this case n.sub.K+1=n.sub.K, as required for the theorem. [0182] (c) Suppose finally that K+1 is not a prime power. Suppose. we set T=1 in equation (B-17), then

[00014]$\begin{array}{cc}{Z}_{{\mathrm{Tn}}_{K}M}^{K+1}=\frac{n_{K}M}{a}\left(\frac{Z_{n_{K}M+1}^K}{b}\right)& \left(B-21\right)\end{array}$ [0183] We note that it is possible in (B-21) that either a or b may he equal to 1; however if a=1 then b must be composite and if b=1 then a must be composite (since otherwise K+1 would have only a single prime factor, contradicting the assumption that it is not a prime power). By the induction hypothesis, since K+1 is not a prime power, n.sub.K must clearly be divisible by a. On the other hand, neither n.sub.K nor M can be divisible by b, so by an analogous argument to that used in part (b) above, we require the final term in brackets on the right hand side of equation (B-21) to be an integer. Hence it follows that

[00015]$\begin{array}{cc}{\left[Z_{{\mathrm{Tn}}_{K}M}^{K+1}\right]}_{\mathrm{mod}M}={\left[\frac{n_{K}M}{a}\frac{Z_{n_{K}M+1}^K}{b}\right]}_{\mathrm{mod}M}=0& \left(B-22\right)\end{array}$ [0184] Therefore we have shown that in this case n.sub.K+1=n.sub.K, as required for the theorem.

[0185] Given that the induction hypothesis holds for K, the combination of the cases (a), (b) and (c) proves the induction hypothesis holds for K+1; we have already shown that it holds for K=1 and hence it must hold for all K; this completes the proof of the theorem.

[0186] For the special case where the modulus is equal to the product the first s prime numbers greater than 1 there is a simpler way of writing the period length, specified in the theorem by equations (B-11) and (B-12). This is given by the following Corollary 1, where we define L.sub.k to be the least common multiple of the first k integers (in this context we make use of curly brackets to denote the least common multiplier of the numbers contained within them, as in equation (B-23) below)

L.sub.k={1,2, . . . ,k}  (B-23)

[0187] Corollary 1. Let X.sup.k.sub.n be a k-th order ACORN sequence, as in Theorem 1, and suppose that the modulus M is equal to the product of the first s prime numbers greater than 1, ie p.sub.1=2, p.sub.2=3, . . . p.sub.s.

[00016]$\begin{array}{cc}M=\stackrel{s}{\underset{i=1}{.Math.}}{p}_i& \left(B-24\right)\end{array}$

[0188] Let L.sub.k be the least common multiple of the first k integers, as defined by equation (B-23). Then for any 1≤k<p.sub.s+1 (where, p.sub.s+1 is the (s+1)-th prime number greater than 1) the sequence X.sup.k.sub.n will have period length equal to

P=ML.sub.k   (B-25)

Proof

[0189] The conditions of the Corollary 1 satisfy the conditions of Theorem 1 with the added restriction that the primes q.sub.r, r=1, . . . , s defined in the theorem are required to he the first s prime numbers greater than 1, thus q.sub.r=p.sub.r for each r. The Corollary will be proven provided it can be established that

[00017]$\begin{array}{cc}{L}_k=\stackrel{s}{\underset{r=1}{.Math.}}{\left(p_r\right)}^{i_r}& \left(B-26\right)\end{array}$

where for each r, i.sub.r the largest integer such that

(p.sub.r).sup.i.sup.r≤k   (B-27)

[0190] This follows immediately from the definition of the least common multiple of k integers as the smallest number that is divisible by each of those k integers: first, L.sub.k must be divisible by each of the trims in the product on die right hand side of equation (B-26), since by equation (B-27) each such term is an integer less than or equal to k; secondly, every, integer less than or equal to k can be written as a product of powers of the p.sub.r, with the power of p.sub.r being less than or equal to the corresponding i.sub.r (since otherwise this would require the integer in question to be greater than k).

REFERENCES

[0191] Reference is made in the above to the following, each of which is incorporated herein by reference in its entirety:

[0192] 1 R. S. Wikramaratna, ACORN—A New Method for Generating Sequences of Uniformly Distributed Pseudo-random Numbers, J. Comput. Phys., 83, pp1 6-31, 1989.

[0193] 2 R. S. Wikramaratna, Theoretical Background for the ACORN Random Number Generator, Report AEA-APS-0244, AEA Technology, Winfrith, Dorset, UK. 1992.

[0194] 3 R. S. Wikramaratna, The Additive Congruential Random Number Generator A Special Case of a Multiple Recursive Generator, J. Comput. and Appl. Mathematics, 261, pp 371-387, 2008. [doi: 10.1016/j.cam.2007.05.018].

[0195] 4 R. S. Wikramaratna, The Centro-invertible Matrix: A New Type of Matrix Arising in Pseudo-random Number Generation, Linear Algebra and its Applications, 434, pp 144-151, 2011. [doi: 10.1016/j.laa.2010.08.01.11].