Inversive congruential generators are a type of nonlinear congruential pseudorandom number generator, which use the modular multiplicative inverse (if it exists) to generate the next number in a sequence. The standard formula for an inversive congruential generator, modulo some prime q is:
Such a generator is denoted symbolically as ICG(q, a, c, seed) and is said to be an ICG with parameters q, a, c and seed seed.
The sequence must have after finitely many steps, and since the next element depends only on its direct predecessor, also etc. The maximum possible period for the modulus q is q itself, i.e. the sequence includes every value from 0 to q − 1 before repeating.
A sufficient condition for the sequence to have the maximum possible period is to choose a and c such that the polynomial (polynomial ring over ) is primitive. This is not a necessary condition; there are choices of q, a and c for which is not primitive, but the sequence nevertheless has a period of q. Any polynomial, primitive or not, that leads to a maximal-period sequence is called an inversive maximal-period (IMP) polynomial. Chou describes an algorithm for choosing the parameters a and c to get such polynomials. [1]
Eichenauer-Herrmann, Lehn, Grothe and Niederreiter have shown that inversive congruential generators have good uniformity properties, in particular with regard to lattice structure and serial correlations.
ICG(5, 2, 3, 1) gives the sequence 1, 0, 3, 2, 4, 1, 0, 3, 4, 2, 1, 0, ...
In this example, is irreducible in , as none of 0, 1, 2, 3 or 4 is a root. It can also be verified that x is a primitive element of and hence f is primitive.
The construction of a compound inversive generator (CIG) relies on combining two or more inversive congruential generators according to the method described below.
Let be distinct prime integers, each . For each index j, 1 ≤ j ≤ r, let be a sequence of elements of periodic with period length . In other words, .
For each index j, 1 ≤ j ≤ r, we consider , where is the period length of the following sequence .
The sequence of compound pseudorandom numbers is defined as the sum
The compound approach allows combining inversive congruential generators, provided they have full period, in parallel generation systems.
The CIG are accepted for practical purposes for a number of reasons.
Firstly, binary sequences produced in this way are free of undesirable statistical deviations. Inversive sequences extensively tested with variety of statistical tests remain stable under the variation of parameter. [2] [3] [4]
Secondly, there exists a steady and simple way of parameter choice, based on the Chou algorithm [1] that guarantees maximum period length.
Thirdly, compound approach has the same properties as single inversive generators, [5] [6] but it also provides period length significantly greater than obtained by a single inversive congruential generator. They seem to be designed for application with multiprocessor parallel hardware platforms.
There exists an algorithm [7] that allows designing compound generators with predictable period length, predictable linear complexity level, with excellent statistical properties of produced bit streams.
The procedure of designing this complex structure starts with defining finite field of p elements and ends with choosing the parameters a and c for each inversive congruential generator being the component of the compound generator. It means that each generator is associated to a fixed IMP polynomial. Such a condition is sufficient for maximum period of each inversive congruential generator [8] and finally for maximum period of the compound generator. The construction of IMP polynomials is the most efficient approach to find parameters for inversive congruential generator with maximum period length.
Equidistribution and statistical independence properties of the generated sequences, which are very important for their usability in a stochastic simulation, can be analyzed based on the discrepancy of s-tuples of successive pseudorandom numbers with and respectively.
The discrepancy computes the distance of a generator from a uniform one. A low discrepancy means that the sequence generated can be used for cryptographic purposes, and the first aim of the inversive congruential generator is to provide pseudorandom numbers.
For N arbitrary points the discrepancy is defined by , where the supremum is extended over all subintervals J of , is times the number of points among falling into J and denotes the s-dimensional volume of J.
Until now, we had sequences of integers from 0 to , in order to have sequences of , one can divide a sequences of integers by its period T.
From this definition, we can say that if the sequence is perfectly random then its well distributed on the interval then and all points are in J so hence but instead if the sequence is concentrated close to one point then the subinterval J is very small and so Then we have from the better and worst case:
Some further notation is necessary. For integers and let be the set of nonzero lattice points with for .
Define
and
for . For real the abbreviation is used, and stands for the standard inner product of in .
Let and be integers. Let with for .
Then the discrepancy of the points satisfies
The discrepancy of arbitrary points satisfies
for any nonzero lattice point , where denotes the number of nonzero coordinates of .
These two theorems show that the CIG is not perfect because the discrepancy is greater strictly than a positive value but also the CIG is not the worst generator as the discrepancy is lower than a value less than 1.
There exist also theorems which bound the average value of the discrepancy for Compound Inversive Generators and also ones which take values such that the discrepancy is bounded by some value depending on the parameters. For more details see the original paper. [9]
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.
In mathematics, a linear form is a linear map from a vector space to its field of scalars.
In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem in the Euclidean plane.
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a low discrepancy.
In computer science, a 2–3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2–3 tree.
In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance of a vector from the origin is a norm, called the Euclidean norm, or 2-norm, which may also be defined as the square root of the inner product of a vector with itself.
Sobol sequences are an example of quasi-random low-discrepancy sequences. They were first introduced by the Russian mathematician Ilya M. Sobol in 1967.
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science.
In mathematics, the classifying space for the unitary group U(n) is a space BU(n) together with a universal bundle EU(n) such that any hermitian bundle on a paracompact space X is the pull-back of EU(n) by a map X → BU(n) unique up to homotopy.
In control theory, the linear–quadratic–Gaussian (LQG) control problem is one of the most fundamental optimal control problems, and it can also be operated repeatedly for model predictive control. It concerns linear systems driven by additive white Gaussian noise. The problem is to determine an output feedback law that is optimal in the sense of minimizing the expected value of a quadratic cost criterion. Output measurements are assumed to be corrupted by Gaussian noise and the initial state, likewise, is assumed to be a Gaussian random vector.
In operator theory, a branch of mathematics, a positive-definite kernel is a generalization of a positive-definite function or a positive-definite matrix. It was first introduced by James Mercer in the early 20th century, in the context of solving integral operator equations. Since then, positive-definite functions and their various analogues and generalizations have arisen in diverse parts of mathematics. They occur naturally in Fourier analysis, probability theory, operator theory, complex function-theory, moment problems, integral equations, boundary-value problems for partial differential equations, machine learning, embedding problem, information theory, and other areas.
In mathematics, Hochschild homology is a homology theory for associative algebras over rings. There is also a theory for Hochschild homology of certain functors. Hochschild cohomology was introduced by Gerhard Hochschild (1945) for algebras over a field, and extended to algebras over more general rings by Henri Cartan and Samuel Eilenberg (1956).
Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.
In mathematics, a Redheffer matrix, often denoted as studied by Redheffer (1977), is a square (0,1) matrix whose entries aij are 1 if i divides j or if j = 1; otherwise, aij = 0. It is useful in some contexts to express Dirichlet convolution, or convolved divisors sums, in terms of matrix products involving the transpose of the Redheffer matrix.
In 1997, Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public-key cryptography. Their result is the construction of an efficient pseudorandom function. Let p and l be prime numbers with l |p−1. Select an element g ∈ of multiplicative order l. Then for each (n+1)-dimensional vector a = ∈ they define the function
An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli with arbitrary distinct primes will be present here.
In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable.
Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's Theorem is a special case of Szemerédi's Theorem for the case .
In mathematics, the hypergraph regularity method is a powerful tool in extremal graph theory that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma. It is a generalization of the graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.