中国剩余定理

AUTHOR: Locez
VERSION: 1

什么是中国剩余定理?


中国剩余定理是数论中关于一元线性同余方程组的定理,说明了一元线性同于方程组有结的准则以及求解方法。《孙子算经》中有一题:

1
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

这个题目翻译过来的意思就是:

1
一个整数除以 3 余 2, 除以 5 余 3, 除以 7 余 2,求这个整数是什么?

同时这也是韩信点兵的故事的来源,韩信让士兵们依次按 3 人一排,5 人一排, 7 人一排进行排列整队,每次只数最后一排的人,便可算出总人数

而韩信点兵与上面的题目同理,数最后一排的人数,也即数余数。3, 5, 7 这种小的数可以枚举,也可以有口诀,但是当这些除数很大,要怎么求解这些一元线性同余方程组,就是中国剩余定理要解决的了。

Read More

RSA 算法

AUTHOR: Locez
VERSION: 1

RSA 是什么?


RSA 是以发明者 Ron RivestAdi ShamirLeonard Adleman 名字的首字母命名的一种非对称加密算法。在公钥密码系统中,加密密钥与解密密钥不同,由加密密钥推导出解密密钥在计算上是不可行的,系统的加密算法和加密密钥可以公开,只要保存好解密密钥即可。而 RSA 则是基于整数因子分解问题的,对极大数做因数分解的难度决定了 RSA 算法的可靠性。

Read More