×

Permutation polynomials modulo \(2^w\). (English) Zbl 0997.11111

The author explicitly characterizes permutation polynomials modulo \(2^n\) for \(n\geq 2\). In addition, he proves that pairs of polynomials defining a pair of orthogonal Latin squares (modulo \(2^n\)) do not exist.

MSC:

11T06 Polynomials over finite fields
05B15 Orthogonal arrays, Latin squares, Room squares
12E05 Polynomials in general fields (irreducibility, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Euler, L., Recherches sur une nouvelle espece des quarrés magiques, Verh. Zeeuwsch Genenot. Wetensch. Vliss, 9, 85-239 (1782)
[2] Hall, M., Combinatorial Theory (1967), Blaisdell: Blaisdell Boston · Zbl 0196.02401
[3] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1975), Clarendon: Clarendon Oxford
[4] Lidl, R.; Niederreiter, H., Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading
[5] Lidl, R.; Mullen, G. L., When does a polynomial over a finite field permute the elements of the field?, Amer. Math. Monthly, 95, 243-246 (1988) · Zbl 0653.12010
[6] Lidl, R.; Mullen, G. L., When does a polynomial over a finite field permute the elements of the field? II, Amer. Math. Monthly, 100, 71-74 (1993) · Zbl 0777.11054
[7] Lidl, R.; Müller, W. B., Permutation polynomials in RSA-cryptosystems, (Chaum, D., Proc. CRYPTO 83 (1984), Plenum: Plenum New York), 293-301 · Zbl 1487.94128
[8] Ma, K.; von zur Gathen, J., The computational complexity of recognizing permutation functions, Proceedings of the 26th ACM Symposium on the Theory of Computing (1994), ACM: ACM Montreal, p. 392-401 · Zbl 1345.68177
[9] Matthews, R., Permutation properties of the polynomials \(1+ x\)+···+ \(x^k\) over a finite field, Proc. Amer. Math. Soc., 120, 47-51 (1994) · Zbl 0806.11058
[10] Mullen, G.; Stevens, H., Polynomial functions (mod \(m)\), Acta Math. Hungar., 44, 237-241 (1984) · Zbl 0563.12017
[11] Mullen, G. L., Local polynomials over \(Z_p\), Fibonacci Quart., 18, 104-107 (1980)
[12] R. L. Rivest, M. J. B. Robshaw, R. Sidney, and, Y. L. Yin, The RC6 block cipher, submitted;, available athttp://theory.lcs.mit.edu/ rivest/rc6.pdfhttp://csrc.nist.gov/encryption/aes/; R. L. Rivest, M. J. B. Robshaw, R. Sidney, and, Y. L. Yin, The RC6 block cipher, submitted;, available athttp://theory.lcs.mit.edu/ rivest/rc6.pdfhttp://csrc.nist.gov/encryption/aes/
[13] Rivest, R. L.; Shamir, A.; Adleman, L. M., A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM, 21, 120-126 (1978) · Zbl 0368.94005
[14] Schnorr, C. P.; Vaudenay, S., Black box cryptanalysis of hash networks based on multipermutations, (Santis, De, Proc. EUROCRYPT’94, 950 (1994), Springer-Verlag: Springer-Verlag New York), 47-57 · Zbl 0909.94013
[15] Shannon, C. E., Communication theory of secrecy systems, Bell Sys. Tech. J., 28, 657-715 (1949) · Zbl 1200.94005
[16] Vaudenay, S., On the need for multipermutations: cryptanalysis of MD4 and SAFER, (Preneel, B., Fast Software Encryption, 1008 (1994), Springer-Verlag: Springer-Verlag Berlin/New York), 286-297 · Zbl 0939.94542
[17] von zur Gathen, J., Tests for permutation polynomials,, SIAM J. Comput., 20, 591-602 (1991) · Zbl 0733.11048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.