Fast evaluation of Rédei functions
Fast evaluation of Rédei functions (scientific article; zbMATH DE number 32689)
Let \(m=\prod^ r_{i=1}p_ i^{e_ i}\) be an arbitrary integer and \(\alpha\) a quadratic nonresidue \(\bmod {p_ i}\), \(1\leq i\leq r\). For a positive integer \(n\) define \(g_ n(x)\), \(h_ n(x)\in\mathbb{Z}[x]\) by \((x+\sqrt\alpha)^ n=g_ n(x)+h_ n(x)\sqrt\alpha\). The rational function \(f_ n(x)=g_ n(x)/h_ n(x)\) is referred to as a Rédei permutation if its evaluation on \(\mathbb{Z}/(m)\) induces a permutation. In particular if \(v=[p_ 1^{e_ 1-1}(p_ 1+1),\ldots,p_ r^{e_ r- 1}(p_ r+1)]\) is relatively prime to \(n\) then \(f_ n(x)\) is a Rédei permutation. Recursive formulas are given for the polynomials \(g_ n\), \(h_ n\) and \(f_ n\) and used to give a fast evaluation algorithm for the Rédei functions.
- Rédei-Permutationen auf Restklassenringen \({\mathbb{Z}}/(m)\). (Rédei- permutations over residue class rings \({\mathbb{Z}}/(m))\)
- Rédei functions and their application in cryptography
- On the length of cycles of Rédei permutations.
- Rédei-Funktionen für Zweierpotenzen. (Rédei functions for powers of two)
- On generalized Redei functions
This page was built for publication: Fast evaluation of Rédei functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3988504)