区块链中的数学 - 欧拉函数积性和扩展剩余定理

本节主要介绍了欧拉函数积性证明和扩展剩余定理,扩展剩余定理应用更加广泛

写在前面

上一节介绍了中国剩余定理并加以证明。有了中国剩余定理的基础,我们来看欧拉函数的积性证明和中国剩余定理的扩展。本节之后,我们可以重回RSA主题。

欧拉函数的积性证明

欧拉定理和欧拉函数一节中,提到欧拉函数是积性函数【注:积性函数:对于数论函数 f(n) 不恒等于0,当 gcd(m,n) = 1 时,满足 f(mn) = f(m)f(n) ,则称 f(n) 为积性函数。如果不要求m,n互质,则f(n) 为完全积性函数 】

欧拉函数积性性质:φ(mn) = φ(m) * φ(n)

  1. 中国剩余定理证明法 用中国剩余定理可以证明,证明的思路是建立这样一种一一对应的关系: \<a, b> <---> x 其中正整数a小于m,并且gcd(a, m) = 1, 正整数b小于n并且gcd(b, n) = 1, 这里的整数x要满足: 0< x < mn && gcd(mn, x) = 1。那么x的个数就是φ(mn)的值。

  2. 证明过程如下: (1)根据中国剩余定理,如果m和n互素,那么关于未知量x的方程组:

$ \begin{cases} x=a\ mod\ m\ x=b\ mod\ n \end{cases} $

当0 <= x < m * n时存在并且仅存在一个解。

如果m, n相同,但是a, b不同,那么上述方程组的解x一定不同。

下面证明求满足gcd(m * n, x) = 1条件的x与求满足gcd(m, a) = 1且gcd(n, b) = 1条件的<a,b> 是等价的。

(2)证明gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的充分必要条件

<2.1> 证明充分性:

gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的充分条件:

由x=a mod m 可得:

x = k * m + a

由公约数性质:gcd(x, m) = gcd(m, a) = 1

同理可得:gcd(x, n) = gcd(n, b) = 1

所以:gcd(mn, x) = 1 【注:参见欧拉函数性质2相关

从而证明了充分性。

<2.2>证明必要性

反正法证明:

gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的必要条件:

假设gcd(a, m) = k > 1,由此可得:

a = a' * k;

m = m' * k

得到:x = k' m + a = k' k m' + k a' = k (k' m' + a')

所以 gcd(x, m) = k > 1。

同理,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。

所以gcd(x, mn) > 1 与假设条件(x与mn互质)矛盾。

所以x和mn互素的必要条件是:a和m互素且b和n互素。

上述结论表明,求x就是求等价数对(a, b)的值 二者建立起一一对应的关系的,有多少个(a, b),就有多少个对应的x。

符合条件的a个数是 φ(m),

符合条件的b的个数是 φ(n).

于是x可取的个数为:φ(m) * φ(n) = φ(mn)

到这里证明了欧拉函数的积性表达。

  1. 欧拉函数通式证明法

还有一种证明方式使用欧拉函数通式来证明的,有人说是不对的,理由是欧拉函数通式的推导用到了积性函数的性质【前篇欧拉函数性质5就是这样推导的】,属于循环论证。

这种说法是片面的,因为欧拉函数通式的推导可以使用积性函数的性质,也可以不使用。 下面举出一种不使用积性函数的性质推导的方法:

设$p_1,p_2,...,p_k$ 是n的素因子【质因子唯一分解定理保证一定存在】。

那么1到n中与n不互质的数的个数为:

$n/p_1 + n/p_2 +...+ n/p_k - n/(p_1p_2)- n/(p_2p3)- ... - n/(p{k-1}p_k) - n/(p_1p_2p3) - ... - n/(p{k-2}p_{k-1}p_k)- ...+ n/(p_1,p_2,...,p_k)$

所以与n互质的数个数为:

$\varphi(n) = n-(n/p_1 + n/p_2 + n/p_k - n/(p_1p_2)- n/(p_2p3)- ... - n/(p{k-1}p_k) - n/(p_1p_2p3) - ... - n/(p{k-2}p_{k-1}p_k)- ...+ n/(p_1,p_2,...,p_k) ) = n *(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1})$

下面用该通式来证明欧拉函数的积性:

$\varphi(m) \varphi(n)=m(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1}) * n(1-{p'}_1^{-1})(1-{p'}_2^{-1})...(1-{p'}_k^{-1})$

其中$p_1,p_2,...p_k$为m的质因数,${p'}_1,{p'}_2,...{p'}_k$为n的质因数, 而m,n无公因数, 所以$p_1,p_2,...p_k$,${p'}_1,{p'}_2,...{p'}_k$互不相同, 所以$p_1,p_2,...p_k$,${p'}_1,{p'}_2,...{p'}_k$均为mn的质因数 且为mn质因数的全集, 因此:

$\varphi(m) \varphi(n)=mn(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1})(1-{p'}_1^{-1})(1-{p'}_2^{-1})...(1-{p'}_k^{-1})$

所以φ(mn)=φ(m)φ(n)。

这种证明法更易理解!

中国剩余定理的扩展

上一节说到的中国剩余定理是经典的范式,要求方程组中两两互质。如果不一定两两互质的情况,如何处理呢?

这里用到了剩余定理的扩展

$\begin{cases} x=a_1\ mod\ m_1 \ x=a_2\ mod\ m_2 \ ...\ x=a_2\ mod\ m_2 \end{cases}$

求解过程:

假设已经求出前k-1个方程组成的一个解为x, 且$M=\prod_{i=0}^{k-1}m_i$

则前k-1个方程的方程组通解为: x + i * M (i∈Z)

那么引入第k个方程后的方程组, 我们要求得一个整数i,使得

$x + i * M \equiv a_k\ mod\ m_k$

即 $i * M \equiv a_k-x\ mod\ m_k$ 到这里可以用扩展欧几里算法【参见历史文章】得求解i

若该同余式无解,则整个方程组无解。

小结

本节主要介绍了欧拉函数积性证明和扩展剩余定理,扩展剩余定理应用更加广泛。

关于剩余定理和扩展的代码实现,可以很容易找到,文中没有列出。

剩余定理扩展没有特别详细描述,是基于大家很好理解经典剩余定理的前提,如有必要后续在单独详诉,在此不再赘述。

好了,有了这些铺垫,下一篇继续回到RSA主题。

欢迎关注公众号:blocksight

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-06-26 18:42
  • 阅读 ( 110 )
  • 学分 ( 0 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

58 篇文章, 1373 学分