Fast evaluation of Rédei functions (Q3988504)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 32689
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Fast evaluation of Rédei functions |
scientific article; zbMATH DE number 32689 |
Statements
28 June 1992
0 references
finite rings
0 references
permutation polynomials
0 references
cryptography
0 references
Rédei permutation
0 references
fast evaluation algorithm
0 references
Rédei functions
0 references
0.8372060060501099
0 references
0.8240662813186646
0 references
0.8205351829528809
0 references
0.8188508749008179
0 references
0.8181178569793701
0 references
Fast evaluation of Rédei functions (English)
0 references
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.
0 references