RSA公开密钥加密算法

工作中用某library写了些RSA公钥密钥对生成,则有空时就重新阅读并思考了下这个已被广泛运用的加密技巧。我是高中时得知这个算法的,当然完全是似懂非懂,主要是那时候对其所基于的数论还未形成最基本的直觉,所以必然无法真正搞懂,不久就忘掉如没学一样。好的是,用现在更成熟的眼光看,这个算法真挺直接的,要点就那么几个。

先简单讲讲它的背景。他的被公布的发现发明是七十年代末,由美国的Rivest, Shamir, Adleman。维基百科的英文页也说这算法也是七十年代初就被英国情报局的一位数学家发现,但它直到九十年代末才被公布。那时候的计算力量还不足以让这个算法可被实现在我们日常生活中,但是好像八九十年代Rivest, Shamir, Adleman为此创办了一家公司,把它非常成功的商业化了,也赚了不少钱。毫无疑问,这算是比较重要的新技术和发展,美国也占了它的牛耳。这些如何进入别的国家(或是被别人也独立发现而至今为公布)我就不太清楚了,我读到过美国对密码学技术出口法律上有严格限制的,九十年代在美国好像有个做这个的人由于公开某加密技术而被美国政府调查,这个人的名字是Zimmerman

RSA算法

现在,我把RSA的技巧简单解释一下,细节也不必讲的太透彻,主要讲讲他的思路和启发。

基本数论有个欧拉定理(欧拉18世纪就发现了),它的断言为

a^{\phi(n)} \equiv 1 \mod n

\phi为totient函数,\phi(n) = |\{1 \leq k \leq n : \gcd(k, n) = 1\}|

通过这个可以观察到在a^m,若m \equiv 1 \mod \phi(n),就可恢复a。那如果d \cdot e \equiv 1 \mod \phi(n),可以试试以a^d加密编码为a信息,收信方以e为自己的钥,以其解密。在\mod nd次方是计算复杂度很高的计算问题,则即使第三方知道被加密的信息是某数的d次方,也难以进行反过来的操作,而取d次方确是个复杂度为\log d的问题。 Continue reading “RSA公开密钥加密算法”

Advertisements

A derivation of a Riemann zeta function identity

Yesterday, I saw the following Riemann zeta function identity:

\displaystyle\sum_{n=1}^{\infty} \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s)\zeta(s-a)\zeta(s-b)\zeta(s-a-b)}{\zeta(2s-a-b)}.

I took some time to try to derive it myself and to my great pleasure, I succeeded.

Eventually, I realized that it suffices to show that

\{(dd_a, dd_b, d^2 n) : d_a | n, d_b | n : d, d_a, d_b, n \in \mathbb{Z}\}

and

\{(dd_a, dd_b, n) : dd_a d_b | n : d, d_a, d_b, n \in \mathbb{Z}\}

are equal as multisets. As sets, they are both representations of the set of 3-tuples of positive integers such that the third is a multiple of the least common multiple of the first two. In the latter one, the frequency of (a,b,c) is the number of d that divides both a and b such that ab | cd. In the other one, if we write (a,b,c) as (d_1 d_2 a', d_1 d_2 b', c) where \mathrm{gcd}(a', b') = 1, the ab | cd condition equates to d_1^2 d_2 a'b' | c, which corresponds to the number of d_1 dividing a and b and such that d_1^2 | c and with that, d_2a', d_2b' both dividing d_1^2 / c, which is the frequency of (a,b,c) via the former representation.

The coefficients \{a_n\} of the Dirichlet series of the LHS of that identity can be decomposed as follows:

a_n = \displaystyle\sum_{d^2 | n, d_a | \frac{n}{d^2}, d_b | \frac{n}{d^2}} (dd_a)^a (dd_b)^b.

The coefficients \{b_n\} of the Dirichlet series of the RHS of that identity are

b_n = \displaystyle\sum_{dd_a d_b | n} (dd_a)^a (dd_b)^b.

Observe how both are equivalent in that via the multiset equivalence proved above, n determines the same multiset of (dd_a, dd_b) for both and across that, the values of the same function (dd_a)^a (dd_b)^b are summed. Hence the two series are equal.

湾区游

我们在群里所讨论的好多与种族,文化,智商,和学科相关,还记得我曾经对数学尖子开玩笑,美国IMO选手,非亚裔,必犹裔,而他似乎未感到我的玩笑口气,回说他那界有一两位非犹太白人。他还强调自己很美国人,不是那种在以色列待过的。高中时,他选了中文为他的外语,以童话为他爱听的一首中文歌。学术上,给的感觉是专注,单一的纯数学本科生,非常肯定他会走学术道路。他的具体数学兴趣及倾向为组合数学和理论计算机和解析数论。那天晚上,问他知道那几个二次互反律(law of quadratic reciprocity)的证明,他回答一个引用Zolotarev’s lemma的,并且发了个链接。当时,我只知道高斯和(Gauss sum)的那个,而细节已经记不清楚了。我花了一小时细读那个证明,领悟后感觉漂亮无比,引用的工具极其简单。从来没有想到可以将这数论皇后的定理视为,表达为置换的奇偶的积,毕竟Legendre symbol给的是1或-1,与sgn一样,好妙啊。回顾透明Legendre symbol给的基本是在给循环阿贝尔群(\mathbb{Z}/{p\mathbb{Z}})^{\times}的元素奇偶,二次剩余和偶置换在他们对应母群都是指数为2的子群。这又让我想到高斯对于正十七边形可作图的证明也是引用指数2的子群,其由Galois theory对应于度数为2的域扩张。过两天,我又学到了Gauss lemma,就是\left(\frac{a}{p}\right) = (-1)^n, n\{a, 2a, \ldots, \frac{p-1}{2}a\}大于p/2的元素的数量。证明思路很直接,将\{a, 2a, \ldots, \frac{p-1}{2}a\}的大于p/2的元素负掉,可和其他元素从新凑成\{1, 2, \ldots, \frac{p-1}{2}\}. Eisenstein对该定理的证明,我以前知道其存在但没看懂的,引用类似于Gauss lemma的引理,思路及证明策略抓住,这次却清晰了然。二次互反律的美妙我之前无法欣赏,记得对此定理有过一种稀奇古怪,难以思议之感,是没有抓住并且悟觉它的美妙的对称结构。想起在Eisenstein的证明中,画了一个pq的格子,将-1的次数示为格子的下左象限所有的点数,此为(p-1)(q-1)/4的来源。

Continue reading “湾区游”

Proof of fundamental theorem of arithmetic

I read it a couple days ago and actually remembered it this time in a way that I will never forget it. It invokes Euclid’s lemma, which states that if p | ab for p prime, then p | a or p | b, which can be proved using Bezout’s lemma. For existence, it does induction on the number of factors, with 1 as the trivial base case. For the non base case, wherein our number is composite, apply the inductive hypothesis on the factors. For uniqueness, assume two distinct factorizations: p_1p_2\ldots p_n = q_1q_2\ldots q_n. By Euclid’s lemma, each of the p_is divides and is thus equal to one of the q_is. Keep invoking Euclid’s lemma, canceling out a prime factor on each iteration and eventually we must end with 1 = 1 in order for the two sides to be equal.