费马小定理和素数在密码学的应用

陈政培

【摘要】素数一直以来都是数学界研究的重要课题，而素数的正确利用可以为密码学提供有效的工具。本文将要介绍获取并检验素数的方法，以及著名的RSA密码的原理。

【关键词】求模运算  RSA算法  米勒拉宾算法  密码学

【中图分类号】G642                              【文献标识码】A      【文章编号】2095-3089（2016）11-0199-02

公元前在古希腊就产生了早期的算术，直到20世纪初才开始使用数论这个词汇。而从早期到中期的这段时间数论却几乎没有什么发展，直到19世纪才由费马、梅森、欧拉、高斯、黎曼、希尔伯特等人发展起来。而且主要内容是寻找素数通项公式，由初等数论向解析数论和代数数论转变，但也产生很多无法解决的猜想。20世纪有些猜想得以解决，但现在仍然有很多结论是以黎曼猜想一类未能被完全证明的猜想为理论基础的，也就是说假使这些猜想是正确的很多理论也会随之正确并有可能上升为定理，一旦猜想是错误的很多理论也会随之覆灭。目前解决大多数猜想的瓶颈就是素数通项公式，有这样一个说法“如果找到一个素数通项公式，一些困难问题就可以由解析数论转回到初等数论范围”，可见，素数在当今还有很大的研究空间，尽管我们无法确定素数通项公式是否存在。而我想就当前日益发展的科技领域谈谈数论中素数的关键地位。

在这个科技化时代，计算机的地位不断上升，人们对计算机的诉求也不断增大，可能作为一个普通的程序员对于计算机内部的数据处理和优化没有太大的需求。……