Paper 2013/251

Permutation Polynomials and Their Differential Properties over Residue Class Rings

Yuyin Yu and Mingsheng Wang

Abstract

This paper mainly focuses on permutation polynomials over the residue class ring ${\mathbb{Z}}_N$, where $N>3$ is composite. We have proved that for the polynomial $f(x)=a_1{x}^1+\cdots +a_k{x}^k$ with integral coefficients, $f(x)modN$ permutes ${\mathbb{Z}}_N$ if and only if $f(x)modN$ permutes $S_{\mu }$ for all $\mu \mid N$, where $S_{\mu }=\{0<t<N:gcd(N,t)=\mu \}$ and $S_N=S_0=\{0\}$. Based on it, we give a lower bound of the differential uniformities for such permutation polynomials, that is, $\delta (f)\ge \frac{N}{\mathrm{\#}{S}_a}$, where $a$ is the biggest nontrivial divisor of $N$. Especially, $f(x)$ can not be APN permutations over the residue class ring \mathbb{Z}_{N}$.Itisalsoprovedthat$f(x)\bmod N$and$(f(x)+x)\bmod N$cannotpermute$\mathbb{Z}_{N}$atthesametimewhen$N$ is even.