有限域上的置换多项式及其在密码学中的应用

摘要

置换多项式在数论、组合论、群论和非结合代数等领域有着广泛的应用。上世纪70年代以来，由于密码学研究的需要，有限域上置换多项式的研究更是受到数学界和工程技术人员的广泛关注。近来，人们又发现了一些特殊形式的置换多项式在Turbo 码和LDPC码中有很好的应用。本文主要是对有限域上置换多项式的构造的研究，重点作了以下几方面工作： 首先，介绍了置换多项式的发展历史与应用，以及一些开放性问题和猜想。总结了置换多项式的判别方法，包括Hermite判别准则，以及通过考察其值集的个数来判别等。 其次，本文构造了一些置换多项式。讨论了有限域上的一些特殊多项式的性质，并证明它们在一定的条件下是置换多项式，包括线性化的置换多项式，正形置换多项式等。其中，给出了 和 上4次正形置换多项式的形式与计数， 上8次线性化的正形置换多项式的形式与计数，以及有限域上一般正形置换多项式的构造。 最后，介绍了有限域上置换多项式的一些应用。本文给出了密码系统的简介，并举例说明了置换多项式在构造APN置换和平衡码字中的应用。本文还求出了一类置换多项式的逆，从而可以构造一个密钥交换协议。