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

      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references