跨越千年的RSA算法

    数论,数学中的皇冠,最纯粹的数学。早在古希腊时代,人们就开始痴迷地研究数字,沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后,几千年来的数论研究成果突然有了实际的应用,这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》,但受篇幅限制,只有一万字左右的内容。其实,从数论到 RSA 算法,里面的数学之美哪里是一万字能扯完的?在写作的过程中,我查了很多资料,找到了很多漂亮的例子,也积累了很多个人的思考,但最终都因为篇幅原因没有加进《程序员》的文章中。今天,我想重新梳理一下线索,把所有值得分享的内容一次性地呈现在这篇长文中,希望大家会有所收获。需要注意的是,本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释,一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述,可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后,希望大家能够积极指出文章中的缺陷,我会不断地做出修改。

======= 更新记录 =======

2012 年 12 月 15 日:发布全文。
2012 年 12 月 18 日:修改了几处表达。

======== 目录 ========

(一)可公度线段
(二)中国剩余定理
(三)扩展的辗转相除
(四)Fermat 小定理
(五)公钥加密的可能性
(六)RSA 算法

Read more…

几个精彩的数论问题

从同事那里借来了一本单墫教授主编的《初等数论》奥数书,看到很多精彩的问题,在这里做个笔记,与大家一同分享。不少问题和答案都有过重新叙述,个别问题有所改动。

 
问题:找出所有使得 2n – 1 能被 7 整除的正整数 n 。

答案:由于 2n 的二进制表达为 1000…00 (n 个 0),因此 2n – 1 的二进制表达为 111…11 (n 个 1)。而 7 的二进制表达是 111 ,要想让它整除 n 个 1 ,显然 n 必须是也只能是 3 的倍数。

Read more…

用抛物线筛选质数

    今天见到一种看上去很帅的质数筛选法。在平面直角坐标系上画出抛物线 y = x2 的图像,然后标出抛物线上的所有格点(两坐标均为整数的点)。其中,只有点 (0, 0) 正好在 y 轴上,其余的点要么在 y 轴左侧,要么在 y 轴右侧。把 y 轴左侧除了 (-1, 1) 以外的所有格点与 y 轴右侧除了 (1, 1) 以外的所有格点相连,这些连线将自动避开 y 轴上纵坐标为质数的点。连接足够多的线条之后,质数就逐渐露了出来。

      

    这是因为, (-a, a2) 和 (b, b2) 的连线将经过 (0, a · b) ,这可以通过计算斜率的方法得到验证。这个颇具创意的质数筛选法叫做 visual sieve ,它是由 Yuri Matiyasevich 和 Boris Stechkin 提出的。

查看更多:
http://plus.maths.org/content/catching-primes
http://www.mathteacherctk.com/blog/2011/10/the-parabolic-sieve-of-prime-numbers/

又一种证明素数无穷多的方法

    今天又学到一种证明素数无穷多的方法。它是由 Filip Saidak 发现的,论文曾发表在 2006 年的 The American Mathematical Monthly 上。

    首先注意到,两个相邻自然数一定是互质的(否则,假设它们有大于 1 的公因数 k ,则它们的差也能被 k 整除,这显然是不可能的)。现在,取一个自然数 n > 1 。由于 n 和 n + 1 是相邻自然数,因此 n 和 n + 1 是互质的。也就是说,n 的质因数和 n + 1 的质因数完全没有重合,因而 n(n + 1) 至少有两个不同的质因数。类似地,由于 n(n + 1) 和 n(n + 1) +1 是相邻自然数,因此它们是互质的,这说明 n(n + 1) 和 n(n + 1) +1 没有相同的质因数,也就是说 (n(n + 1))(n(n + 1) +1) 至少有三个不同的质因数。我们可以无限地这样推下去,从而得出,素数必然是无穷多的。

Read more…