初等数论 ——关于素数、同余和密文的计算方法外文翻译资料

初等数论

——关于素数、同余和密文的计算方法

原文作者： William Stein 单位：华盛顿大学

摘要：本书对于素数、同余、密文展开详细理论知识讲解，同时，整本书配有适当的计算例子，向读者介绍了强大的免费开源的数学软件系统——塞奇。读者阅读时，将被强烈鼓励动手去操作书中的习题，书后附有较为详细的答案。

关键词：素数；同余；密文；计算方法

1

素数

每个正整数都可以写成特定的素数的相乘的形式，例如。这是很难证明，正如我们接下来将会读到的。实际上更令人震惊的是，似乎以现在的技术难以找到一个方法编写某些1000位以上的数字写成质数相乘的形式，然而数据显示这正被使用，当每天数以百万计的人们在网上买东西的时候。

因为素数是整数的基石，很自然地，人们想知道素数在整数之间的分布。

“有两个事实关于素数的分布。首先，他们是数学家们最随意和最基础的研究对象：他们像杂草成长于自然数之间，表面上看上去除了偶尔不服从任何其他规律外，没有人能预测接下里会发现什么。第二个事实是更惊人的，因为它刚好阐述了相反的一面，素数表现出惊人的规律性，素数有它们的行为规律，它们服从这些规律近乎军事般的准确。”

——唐·札席尔

数论理论中最著名的未解决的问题——黎曼猜想：猜想素数分布的问题具有一个非常精确的规律。

本章我们通过研究素数的规律，整数分解，素数的分布，为接下来学习数论奠定基础理论。在1.1节中，我们严格证明每一个正整数都是素数的产物，并以特定整数为例，找到这样的分解将赢得大量的“现金补贴”。在1.2节中，我们将讨论一系列素数定理，从欧几里德的证明这组是无限到并讨论已知最大的素数。最后，我们通过素数定理和黎曼假设讨论素数的分布。

1.1 素数分解

1.1.1 素数

自然数的集合是

N = {1， 2， 3， 4， . . .}，

整数的集合是

Z = {. . . ，minus;2，minus;1， 0， 1， 2， . . .}.

定义1.1.1 (整除). 如果a，b Z， ac = b 且 c Z.我们说a能整除b，写为a | b，在这种情况下，我们就说a是 b的一个因数。

例如，我们有2 | 6和3 | 15。同时，所有整数都可以被0整除，且被0整除商都为0。然而，3不能整除7在自然数范围内。

备注1.1.2符号b a 表示“b可被a除尽”常见于俄罗斯数论著作中。

定义1.1.3 (素数和合数)。如果一个整数n gt; 1除了1和它本身以外不再有其他的因数，我们称之为素数。如果n不是素数，我们则称之为合数。

1既不是素数也不是合数。

自然数里较小的素数有：

2， 3， 5， 7， 11， 13， 17， 19， 23， 29， 31， 37， 41， 43， 47， 53， 59， 61， 67， 71， 73， 79， . . . ，

自然数里较小的合数有：

4， 6， 8， 9， 10， 12， 14， 15， 16， 18， 20， 21， 22， 24， 25， 26， 27， 28， 30， 32， 33， 34， . . . .

备注1.1.4约翰·何顿·康威提出minus;1应该被看成一个质数。此外，在1914年莱默提出1理应看做一个素数。在这本书中，我们不把minus;1和1作为素数考虑。

塞奇（华盛顿大学开发开源数学软件）例子1.1.5我们使用塞奇来计算a和bminus;1之间的所有素数。

塞奇：素数范围(10，50)

[11、13、17、19、 23、 29、 31、 37、 41、 43、 47]

我们也可以在一个间隔中计算合数：

塞奇:[n到 n的范围(10、30)如果不是素数(n)]

(10、12、14、15、16、18、20、21、22、24、25、26、27、28]

每一个不是素数的自然数，以独特的方式构建。

定理1.1.6 (算术基本定理)。每一个自然数可以写成有限个素数的乘积。

注意，素数的因子只有一个，1是一个空因子。

备注1.1.7我们将在1.1.4节中证明的定理1.1.6，可能比你想象的更难证明。例如，有限的分解可能失败

6的两种不同因子表示方式不同：

1.1.2最大公约数

我们将使用两个整数的最大公约数的概念证明：如果p是一个素数，且p | ab，同时p |a或p | b。证明这关键一步是我们定理1.1.6的证明。

定义1.1.8(最大公约数) 让

gcd (a，b) = max {d Z : d | a and d | b} ，

除非a和b都是0，在这种情况下，gcd (0，0)= 0。

例如，gcd(1，2) = 1，gcd(6，27) = 3，对于任意的a，gcd (0，a) =gcd(a，0) = a.

引理1.1.9 对于任何整数a和b，我们有

gcd (a，b)= gcd (b)= gcd (plusmn;a、plusmn;b)= gcd (a、bminus;a)= gcd (a、b a)。

证明：我们只证明gcd(a，b)= gcd (a、bminus;a)，其他情况下证明方式相类似。

假设d | b和d，所以存在整数c₁和c₂，d c₁ = b和d c₂ = b。然后bminus;a = d c₂minus;d c₁ = d(c₂minus; c₁)，所以 d |b – a。因此gcd(a，b)gcd(a，b minus; a)，因为这最大的大于我们讨论的最大公约数 gcd(a，b) 是最大公约数的子集(a，b minus;a)。同理，a被minus;a取代，b被b –a取代，显示gcd(a，b minus;a) = gcd(minus;a，b minus; a) gcd(minus;a，b) = gcd(a，b)， 它证明gcd(a， b) = gcd(a,b minus;a).

引理1.1.10 假设a、b、nz 。则gcd(a，b)=gcd(a、bminus; an)。

证明：通过重复应用引理1.1.9，我们得到

gcd(a，b) = gcd(a，b minus; a) = gcd(a，b minus; 2a) =hellip; = gcd(a，b minus; an).

现在假设我们已经证明了定理1.1.6。一个天真的方式计算gcd(a，b)是a和b的一个因子同时由定理1.1.6知a是素数，然后gcd(a，b)素因子分解可以认为a和b素因子分解。例如，如果a= 2261且b = 1275，那么a= 7·17·19，同时b = 3·52·17，所以gcd(a，b)= 17。事实证明，整数的最大公约数，甚至非常大的数（数百位的位数)，使用下面算法1.1.13计算非常容易，计算gcd(a，b)没有因式分解a或b。

为了激励算法1.1.13，我们用不同的方式计算gcd（2261，1275）。首先，我们回顾一个有用的事实。

命题1.1.11 假设a和都是整数，且b不为0。然后存在特定的整数q和r，使得0r 且a= bq r。

证明：为简单起见，假设a和b是正数（我们向读者舍弃一般情况）。使得Q是所有非负整数n的集合且a-bn 非负。那么Q不为空，因为0 Q，同时Q是有界的，因为a-bn lt;0对所有的ngt; a/b。设q是Q中最大元素。则r = a - bq lt;b，否则q 1也将属于Q。因此证明Q和R满足存在的结论。

为了证明唯一性，假设qacute;和 racute;也满足了结论。

那么既然qacute; Q因为Q =a- b qacute; 0，所以qacute; q，我们可以写qacute; = q - m对于一些m 0。如果qacute;q，又m1，因此

racute; = a minus; b qacute; = a minus; b(q minus; m) = a minus; bq bm = r bmb

由于R 0产生一个矛盾。因此， q= qacute;和racute; =一 - b qacute; = a - bq = r，得证。

对我们来说，一个算法是可以遵循的指令特定的任务在的有限序列下执行，诸如包含的指令的序列计算机程序，该程序必须终止在任何有效的输入。单词“算法”有时被比这里所定义的广义的使用（有时更精确），但该定义将足以满足我们。

算法1.1.12（除法算法）。假设a和b是整数且b不为0。此算法计算整数q和r，使得0r 且a= bq r。

我们将不描述算法1.1.12的实际步骤，因为它恰恰类似于长的除法算法。需要注意的是它可能与你在学校学到的标准长除法算法不是完全一样的，因为我们得到了一个余数当我们用一个整数除以一个负数时。

我们用除法算法反复计算gcd（2261，1275）。2261除以1275，我们发现，

2261=1·1275 986，

所以，q =1和r=986。请注意，如果一个自然数d同时整除两者2261和1275，则d整除它们的余数986且d仍然整除1275。也就是说，当d整除1275和986，那么它必须整除它们的和2261！我们已经取得了进展：

gcd（2261，1275）= GCD（1275，986）。

这种平等也遵循应用引理1.1.9。重复地，我们有

1275=1·986 289，

所以gcd（1275，986）= gcd（986，289）。继续前进：

986=3·289 119

289=2·119 51

119=2·51 17。

由此cdg（2261，1275）=···= gcd（51，17），这是因为1717|51因此

gcd（2261，1275）=17。

除了一些繁琐的运算，这个计算是系统的，这是没有必要计算任何整数的因数（尤其当如果涉及的数有上百位数，我们无法迅速的计算出其因数）。

算法1.1.13（最大公约数）。给定整数a，b，这算法计算gcd（a，b）。

1. [假设Agt; Bgt;0]我们已经知道gcd（a，b）= gcd（| a |，| b |）= gcd（| b |，| a |），

因此，我们可以用它们的绝对值代替a和b，因此假设a，b 0。如果a = B，输出a,终止。如果有必要交换，我们假设a gt; b。如果b = 0，我们输出a。

2.[商和余数]使用算法1.1.12，写成a =bq r，0lt;b和q Z.

外文文献出处：William Stein, Elementary Number Theory Primes Congruences and Secrets A computational Approach, Science Business Media, LLC 2009

剩余内容已隐藏，支付完成后下载完整资料

---

附外文文献原文:

1

Prime Numbers

Every positive integer can be written uniquely as a product of prime numbers, e.g. . This is surprisingly difficult to prove, as we will see below. Even more astounding is that actually finding a way to write certain 1,000-digit numbers as a product of primes seems out of the reach of present technology, an observation that is used by millions of people every day when they buy things online.

Since prime numbers are the building blocks of integers, it is natural to wonder how the primes are distributed among the integers.

“There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision.”

— Don Zagier [Zag75]

The Riemann Hypothesis, which is the most famous unsolved problem in number theory, postulates a very precise answer to the question of how the prime numbers are distributed.

This chapter lays the foundations for our study of the theory of numbers by weaving together the themes of prime numbers, integer factorization, and the distribution of primes. In Section 1.1, we rigorously prove that the every positive integer is a product of primes, and give examples of specific integers for which finding such a decomposition would win one a large cash bounty. In Section 1.2, we discuss theorems about the set of prime numbers, starting with Euclidrsquo;s proof that this set is infinite, and discuss the largest known prime. Finally we discuss the distribution of primes via the prime number theorem and the Riemann Hypothesis.

1.1 Prime Factorization

1.1.1 Primes

The set of natural numbers is

N = {1, 2, 3, 4, . . .},

and the set of integers is

Z = {. . . ,minus;2,minus;1, 0, 1, 2, . . .}.

Definition 1.1.1 (Divides). If a, b Z we say that a divides b, written a | b, if ac = b for some c Z. In this case, we say a is a divisor of b.

For example, we have 2 | 6 and minus;3 | 15. Also, all integers divide 0, and 0 divides only 0. However, 3 does not divide 7 in Z.

Remark 1.1.2. The notation b a for “b is divisible by a” is common in Russian literature on number theory.

Definition 1.1.3 (Prime and Composite). An integer n gt; 1 is prime if the only positive divisors of n are 1 and n. We call n composite if n is not prime.

The number 1 is neither prime nor composite. The first few primes of N are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, . . . ,

and the first few composites are

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, . . . .

Remark 1.1.4. J. H. Conway argues in [Con97, viii] that minus;1 should be considered a prime, and in the 1914 table [Leh14], Lehmer considers 1 to be a prime. In this book, we consider neither minus;1 nor 1 to be prime.

SAGE Example 1.1.5. We use Sage to compute all prime numbers between

a and b minus; 1.

sage: prime_range(10,50)

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

We can also compute the composites in an interval.

sage: [n for n in range(10,30) if not is_prime(n)]

[10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]

Every natural number is built, in a unique way, out of prime numbers:

Theorem 1.1.6 (Fundamental Theorem of Arithmetic). Every natural number can be written as a product of primes uniquely up to order.

Note that primes are the products with only one factor and 1 is the empty product.

Remark 1.1.7. Theorem 1.1.6, which we will prove in Section 1.1.4, is trickier to prove than you might first think. For example, unique factorization fails in the ring

where 6 factors in two different ways:

1.1.2 The Greatest Common Divisor

We will use the notion of the greatest common divisor of two integers to prove that if p is a prime and p | ab, then p | a or p | b. Proving this is the key step in our proof of Theorem 1.1.6.

Definition 1.1.8 (Greatest Common Divisor). Let

gcd(a, b) = max {d Z : d | a and d | b} ,

unless both a and b are 0 in which case gcd(0, 0) = 0.

For example, gcd(1, 2) = 1, gcd(6, 27) = 3, and for any a, gcd(0, a) =

gcd(a, 0) = a.

Lemma 1.1.9. For any integers a and b, we have

gcd(a, b) = gcd(b, a) = gcd(plusmn;a,plusmn;b) = gcd(a, b minus; a) = gcd(a, b a).

Proof. We only prove that gcd(a, b) = gcd(a, b minus; a), since the other cases are proved in a similar way. Suppose d | a and d | b, so there exist integers c₁ and c₂ such that d c₁ = a and d c₂= b. Then bminus;a = d c₂minus;d c₁ = d(c₂minus; c₁), so d | b minus; a. Thus gcd(a, b)gcd(a, b minus; a), since the set over which we are taking the max for gcd(a, b) is a subset of the set for gcd(a, b minus; a). The same argument with a replaced by minus;a and b replaced by b minus;a, shows that gcd(a, b minus; a) = gcd(minus;a, b minus; a)gcd(minus;a, b) = gcd(a, b), which proves that

gcd(a, b) = gcd(a, b minus; a).

Lemma 1.1.10. Suppose a, b, n Z. Then gcd(a, b) = gcd(a, b minus; an).

Proof. By repeated application of Lemma 1.1.9, we have

lt;

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[287121]，资料为PDF文档或Word文档，PDF文档可免费转换为Word