Fast evaluation of Rédei functions

From MaRDI portal
(Redirected from 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.











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)