Uniformly distributed sequences of $p$-adic integers

V. S. Anashin

Diskretnaya Matematika, Tome 14 (2002) no. 4, pp. 3-64.

Résumé

The paper describes ergodic (with respect to the Haar measure) functions in the class of all functions, which are defined on (and take values in) the ring $Z_p$ of $p$-adic integers and which satisfy (at least, locally) the Lipschitz condition with coefficient one. The equiprobable (in particular, measure-preserving) functions of this class are described. In some cases (and especially for $p=2$) the descriptions are given by explicit formulas. Some of the results may be viewed as descriptions of ergodic isometric dynamical systems on the $p$-adic unit disk. The study is motivated by the problem of pseudorandom number generation for computer simulation and cryptography. From this view the paper describes nonlinear congruential pseudorandom generators modulo $m$ which produce strictly periodic uniformly distributed sequences modulo $m$ with maximal possible period length (that is, exactly $m$). Both the state change function and the output function of these generators can be, for example, meromorphic on $Z_p$ functions (in particular, polynomials with rational, but not necessarily integer coefficients) or compositions of arithmetical operations (like addition, multiplication, exponentiation, raising to integer powers, including negative ones) with standard computer operations such as bitwise logical operations (for example, $\mathtt{XOR}$, $\mathtt{OR}$, $\mathtt{AND}$, $\mathtt{NEG}$). The linear complexity of the produced sequences is also studied.

Bibliographie

[1] Keipers L., Niderreiter G., Ravnomernoe raspredelenie posledovatelnostei, Nauka, Moskva, 1985 | MR

[2] Knut D., Iskusstvo programmirovaniya, t. 2, Vilyams, Moskva, 2000

[3] Mahler K., $p$-adic numbers and their functions, Cambridge Univ. Press, Cambridge, 1981 | MR | Zbl

[4] Alperin R. C., “$p$-adic binomial coefficients $\operatorname{mod}p$”, Amer. Math. Monthly, 92 (1985), 576–578 | DOI | MR

[5] Hall R. R., “On pseudo-polynomials”, Arch. Math., 18 (1971), 71–77 | MR | Zbl

[6] Koblits N., $p$-adicheskie chisla, $p$-adicheskii analiz i dzeta-funktsii, Mir, Moskva, 1982 | MR

[7] Marsaglia G., “Random numbers fall mainly in the planes”, Proc. Nat. Acad. Sci. USA, 61 (1968), 25–28 | DOI | MR | Zbl

[8] Lausch H., Nöbauer W., Algebra of polynomials, North-Holland, Amsterdam, 1973 | MR | Zbl

[9] Kaiser H. K., Nöbauer W., “Permutation polynomials in several variables over residue class rings”, J. Austral. Math. Soc., 43 (1987), 171–175 | DOI | MR | Zbl

[10] Yurov I. A., O $p$-adicheskikh funktsiyakh, sokhranyayuschikh meru Khaara, 63 (1998), 935–950 | MR | Zbl

[11] Anashin V. S., “Ravnomerno raspredelennye posledovatelnosti tselykh $p$-adicheskikh chisel”, Matem. zametki, 55:2 (1994), 3–46 | MR | Zbl

[12] Anashin V. S., “Uniformly distributed sequences over $p$-adic integers” (Proc. NTAMCS'93 van der Poorten, A. J., et al., Eds.), World Scientific, Singapore, 1995, 1–18 | MR | Zbl

[13] Rivest R., “Permutation polynomials modulo $2^w$”, Finite Fields and Appl., 7 (2001), 287–292 | DOI | MR | Zbl

[14] Anashin V. S., “Uniformly distributed sequences over $p$-adic integers with application to nonlinear congruential generators”, Abstr. Conf. Number Theoretic and Algebraic Methods in Computer Science (Intern. Centre for Sci. and Tech. Inform.), Moscow, 1993, 6–8 | MR

[15] Larin M. V., “Tranzitivnye polinomialnye preobrazovaniya kolets vychetov”, Diskretnaya matematika, 14:2 (2002), 20–32 | Zbl

[16] Kuratovskii K., Topologiya, t. 1, Mir, Moskva, 1966 | MR

[17] Anashin V. S., “Uniformly distributed sequences in computer algebra, or how to construct program generators of random numbers”, J. Math. Sci., 89 (1998), 1355–1390 | DOI | MR | Zbl