AKS算法及其在公钥加密术中的意义

AKS Algorithm and It's Effect on Public-key Encryption

AKS算法是3位印度的计算机科学家于2002年8月提出的,它是一个能在输入规模的多项式时间内确定的对一个数进行素性测试的方法.本文详细介绍了AKS算法的基本思想、算法流程以及时间复杂度的分析.又由于大素数的选取在公钥加密术中极为重要,因此讨论了AKS算法在公钥加密术中的意义.

AKS algorithm was proposed by three computer scientists in India in Aug 2002.This algorithm can unconditionally determine whether an input number is a prime in polynomial time. In this paper, the basic idea, the algorithm and the time complexity analysis of AKS algorithm are described in detail. The impact of this algorithm on public-key encryption is discussed because the selection of a big prime is very important to it.