剩余类环Z/(pn)上若干类单圈多项式构造

游 伟 戚文峰

(解放军信息工程大学 郑州 450002)

1 引言

若f(x)是一个整系数多项式，当x通过模m的一个完全剩余系时，f(x)也通过模m的一个完全剩余系，则称f(x)是模m的一个置换多项式。关于置换多项式的研究结果非常多，可参考文献[1-7]。引起置换多项式迅速发展的一个主要原因是它已逐渐在数论，组合论，密码系统等领域中得到应用。事实上，著名公钥密码体制 RSA[8]和分组密码算法 RC6[9]就是其中的两个应用。

本文研究的是一类特殊的置换多项式，即剩余类环上的单圈多项式(见定义 1)。单圈多项式在密码学的众多领域都有重要应用。例如，在伪随机数发生器[10]的理论中，状态转移函数必须提供伪随机性，特别地，它必须保证状态序列的元素分布和周期。为了达到这个目的，我们可以选择单圈多项式作为状态转移函数，这样就可以保证状态序列达到最大周期并且其元素满足严格一致分布。事实上，经典的线性同余发生器使用的即是一次单圈多项式，它的优势是实现速度快，但弱点是结构过于简单。本文的目标是构造任意次数的单圈多项式，这样就可以利用高次单圈多项式来产生非线性同余发生器以取代线性同余发生器。伪随机数在包括仿真，抽样，数值分析，公钥密码算法设计等众多领域中都有着不同形式的应用。另外，单圈多项式还可以用来构造拉丁方。拉丁方的应用也是极其广泛的。例如，在保密通信网络中用来做口令的分发；以及在某些密码算法的设计中作为多重置换来使用。……