论文总字数：16118字

目 录

1素数的介绍 4

1.1素数的背景 4

2 素数个数 5

2.1欧几里得无限多素数证明 5

2.2素数倒数累和发散证明 5

2.3费马素数无限多证明 6

2.4函数证明素数无限多证明 7

3素数分布的规律 8

3.1素数的分布情况及通式 8

4素数的猜想 9

4.1孪生素数猜想 9

4.2哥德巴赫猜想 10

5素数筛选 11

5.1埃拉托色尼筛选法  12

5.2 Miller-Rabin 算法 14

6素数的应用 16

6.1素数在密码学中的应用 16

6.2素数在哥德巴赫猜想的应用 16

6.3素数在Fibonacci数列中的素数分布 17

7结论及展望 17

参考文献 17

致谢 18

素数个数及素性检测

俞超

数学与统计学院 20121314027

摘要：素数是数论中重要的一环，被无数的数学家重视研究，素数是指能被1和自身整除的自然数，有无穷多个，它的分布规律一直在被研究，被发现。其中主要的猜想有哥德巴赫猜想，孪生素数猜想，黎曼猜想，梅森素数猜想，它们作为数学当中的经典题目一直在吸引更多数学家研究。本文先从素数的个数入手，用欧几里得，黎曼函数，费马素数，函数不同的方法证明素数有无穷多个，接下来找出无穷多个素数分布规律，但经过很多数学家的努力只是找到了它的近似分布规律，这里会介绍几个著名的近似分布规律，写出关于素数的一些基本猜想。如何用程序将素数筛选出来，通常有两种方法，一种是真素数筛选，就是利用素数的简单定义，用比判断的整数小的整数依次去整除这个数，耗费时间长，计算量庞大，在生活应用中操作起来不现实，所以真素数检测通常适用于一定范围内的小素数，那么对大素数的筛选我们提供另外一种方法，来提高判别素数的效率。新的，高效率的算法是对整数有个概率性的判断，miller-rabin素数筛选方法是概率性判别法中比较出众的算法，本文会对它以及在密码学等领域的应用做一个分析。

关键字： 素数个数 分布规律 素性检测

The number of primes and primality testing

Yu chao

School of mathematics and statistics ，NUIST，Nanjing 20121314027，China

Abstract：The prime number is an important part in the theory and is valued by many mathematicians. Prime referring to the natural number can be divisible by 1 and itself. There are infinite whose distribution pattern has been studied and found to be. The main conjecture is Goldbach conjecture, the twin prime conjecture, Riemann conjecture, Mason prime conjecture，Classical topics in mathematics have been attracting more mathematicians. Understand a thing first from its nature. This article starts with the basic nature of prime numbers. With Euclid, Riemann function, Fermat primes, proof of different methods of function has an infinite number of primes. Next is to find out the law of the distribution of the infinite number of prime numbers. But through the efforts of many mathematicians, it is found that its approximate distribution law. We will introduce several well-known approximate distribution law and write some basic guesses about prime numbers..How to use the program to select the prime number? There are usually two ways. A true prime screening，is the simple definition of the prime number.，with the small integer integer ratio judgment in order to divide this number，take a long time，Calculation is relatively large, operating in the life of the application is not realistic. So real prime detection is usually applied to a certain range of small prime. Then we provide a new method for the screening of large prime numbers. To improve the efficiency of discriminant prime，this method is a probability prime number filter. Miller-Rabin prime screening method is the mainstream of the probability of prime discriminant method. This article will make an analysis of it, since the prime discriminant out。

Key words：Number of prime numbers Distribution law primality test

1素数的介绍

1.1素数的背景

年代久远的数论是数学科目中不可缺少的一部分，历史上遗留下来的素数难题和哥德巴赫猜想一直是数论研究的重要问题之一，对于他们的研究可以极大推动整个数论的发展，数学研究人员为之付出了巨大的努力和艰辛的劳动，促进了数论的发展 ，并取得了重要的结果，但它并没有赢得真正意义上的进步，如素数分布问题等。素数的这个概念，早在公元前就为人们所熟知，我们将质数又称为素数，有无限多个素数，我们对素数通常的理解是1和它自身可以整除，其他数不能整除它.比如说3，7，11，进行判断之后就能确定它是一个素数。我们对素数最精确的定义是，自然数集里面，,很容易看到我们把1，叫做的平凡因子，设大于1的自然数，若有平凡因子，则把称作素数；相反，若有非平凡的因子，则把称作合数。比如说11,13,17这些都是素数，12,14,18等都是合数。所以整数，包含自然数集和0还有负整数，自然数集包含1和素数和合数。

素数在数学中占有很重要的地位，它是整数和自然数集当中不可或缺的一部分，因为素数具有的无穷魅力，像哥德巴赫猜想，梅森素数猜想，孪生素数猜想等等，千百年来被无数的数学家所热爱并对它进行研究，我们已经发现了素数的不少规律，但还有很多，未知的素数规律等待着我们去发现，现在来简单介绍一些已发现的素数规律和素数的基本性质。

后来人们发现自然数可以由素数相乘得到的，并且存在很多个这样的整数，于是猜测自然数既然无穷大，那么对应的素数也肯定无穷大，后来欧几里得最早证明了素数无穷大。但是在自然数中素数与合数随意排列，对一些素数的分布情况进行研究，发现素数的分布没有规则，因此鉴定一个自然数是素数还是合数就成为一个问题。

素数的问题在16世纪引起了当时人们的关注，大家尝试去研究素数的某些规律，高斯确认了没有一成不变的素数规律，但他却发现了一个素数的近似公式，当时的人们比较落后，没有高性能的计算机，对于一个小整数来做素性判别是十分困难的问题，11位以上的整数更没有办法进行检测，所以只好去研究一些小位数，个别的整数，进行一般性的判断，研究一个位数较多的整数是否为素数，经常是计算量的庞大而功亏一篑，直到近代，手摇计算机的出现，有力的帮助数学家去研究素数检测，1960年后，电子计算机的出现大大的支持了数学家去研究素数判别，并开创了不同的途径去研究素性检测，但经典的素数判别法对素数个体的研究还是最不错的办法。

本文以素数个数的研究为起点，用欧几里得，黎曼函数等等不同的办法去证明素数有无限多个，接下来找出无穷多个素数分布规律，但经过很多数学家的努力只是找到了它的近似分布规律，这里会介绍几个著名的近似分布规律，写出关于素数的一些基本猜想。如何用程序将素数筛选出来，通常有两种方法，一种是真素数筛选，就是利用素数的简单定义，用比判断的整数小的整数依次去整除这个数，如果整除下来就是无可置疑的合数，不能整除就是素数，如果出现一个大素数，检查起来就会费劲，耗费的时间比较长，计算量比较庞大，在生活应用中操作起来是不现实的，所以真素数检测通常适用于一定范围内的小素数，那么对大素数的筛选我们提供了另外一种方法，来提高判别素数的效率。这种不同于以往的筛选方法叫做概率素数筛选，miller-rabin素数筛选是主要的、也是比较实用的概率素数判别法之一，本文会对它做一个分析以及举例。

2 素数个数

首先素数的个数有无限个，对于素数研究很早就开始了，起初是欧几里德先证明出来的，在《几何原本》中提到了素数无限个，并由它自己写出了经典证明，接下来又有不同的数学家用他们自己方法证明了素数个数无穷多个。这里简单的介绍费马素数无限多的证明，素数函数无限多的证明，素数倒数之和是发散的证明，从中可以明确得到素数无穷多个。

2.1欧几里得无限多素数证明

欧几里得使用了证明中的常用方法：反证法。

证明，假定，存在有限的个素数，按照顺序排成为。

剩余内容已隐藏，请支付后下载全文，论文总字数：16118字

相关图片展示：