R S Wikramaratna
March 2020
Download full reportThe Additive Congruential Random Number (ACORN) generator represents an approach to generating uniformly distributed pseudo-random numbers which is straightforward to implement for arbitrarily large order and modulus (where the modulus is a sufficiently large power of 2, typically up to 2120); it has been demonstrated in previous papers to give rise to sequences with long period which, for the kth order ACORN generator with modulus a power of 2, can be proven from theoretical considerations to approximate in a particular defined sense to the desired properties of uniformity in up to k dimensions. In this paper we state and prove a theorem concerning the exact period length for an ACORN sequence with any given order and any integer modulus (which may either be a prime power, or a composite modulus with two or more different prime factors each raised to a possibly different power) for cases where the seed and modulus are assumed to be relatively prime. For those cases where the modulus is a prime number or has just one single prime factor raised to an integer power, we show that this theorem is exactly equivalent to an existing, but previously unproven, conjecture concerning the periodicity. The theorem also extends the periodicity results beyond those in the conjecture, to include those cases where the modulus is composite, having two or more prime factors each of which might be raised to a different integer power.