RSA加密算法数学基础

1.同余类

概念：给定正整数 $m$ ，全体整数可按照模 $m$ 是否同余分成若干两两不相交的集合，使得每一个集合中的任意两个正整数对模 $m$ 一定同余，而属于不同集合的任意两个整数对模 $m$ 不同余，每一个这样的集合称为模 $m$ 的同余类或剩余类。
例子：取 $m=7$ ，则 $\{0,7,14,...\}$ 是模7的同余类。
定理：对于给定的正整数 $m$ ，有且恰有 $m$ 个不同的模 $m$ 的剩余类。
模 $m$ 的m个剩余类可分别记为 $[i]$ ， $i$ 为该剩余类中整数除 $m$ 所得的余数，可分别如下表示：
$[0]=\{...,-2m,-m,0,m,2m,...\}$
$[1]=\{...,-2m+1,-m+1,1,m+1,2m+1,... \}$
$[2] = \{...,-2m+2,-m+2,2,m+2,2m+2,... \}$
...
$[m-1] = \{...,-2m+(m-1),-m+(m-1),m-1,m+(m-1),2m+(m-1),... \}$

2.完全剩余系

概念：在整数模 $m$ 的所有剩余类中各取一个代表元素 $a_1,a_2,...,a_m,(a_i\in [i-1],i = 1,2,...,m)$ ，则称 $a_1,a_2,...,a_m$ 为模 $m$ 的完全剩余系。完全剩余系 $0,1,2,...,m-1称为最小非负完全剩余系$ 。
例子： $7,15,16,-4,-10,5,-1$ 为模7的一组完全剩余系。 $0,1,2,3,4,5,6$ 为模 $7$ 的最小非负完全剩余系。
$Z_m$ 表示由 $m$ 的最小非负完全剩余系集合 $Z_m = \{ 0,1,2,...,m-1\}$ 。 $Z_m$ 中的加法、减法、乘法都是模 $m$ 下的运算。
定理：设 $m$ 是正整数，整数 $a$ 满足 $gcd(a,m)=1$ ， $b$ 是任意整数。若 $x$ 遍历模 $m$ 的一个完全剩余系，则 $ax+b$ 也遍历模 $m$ 的一个完全剩余系。
定理：设 $m_1,m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个完全剩余系， $y$ 遍历模 $m_2$ 的一个完全剩余系，则 $m_1y+m_2x$ 遍历模 $m_1m_2$ 的一个完全剩余系。

3.欧拉函数

在模 $m$ 的一个剩余类当中，如果有一个数与 $m$ 互素，则该剩余类中所有的数均与 $m$ 互素，这时称该剩余类与 $m$ 互素。
概念：与 $m$ 互素的剩余类的个数称为欧拉函数，记为 $\phi(m)$ 。 $\phi(m)$ 等于 $Z_m$ 当中与 $m$ 互素的数的个数。对于任意一个素数 $p$ ， $\phi(p)=p-1$ 。
例子： $\phi(6)=2$ ，表示 $Z_6$ 中与 $6$ 互素的数的个数，既 $1,5$ 。

4.简化剩余系

概念：在与 $m$ 互素的 $\phi(m)$ 个模 $m$ 的剩余类中各取一个代表元 $a_1,a_2,...,a_{\phi(m)}$ ，它们组成的集合称为模 $m$ 的一个既约剩余系或简化剩余系。 $Z_m$ 中与 $m$ 互素的数构成模 $m$ 的一个既约剩余系，称为最小非负既约剩余系。
定理：设 $m$ 是正整数。整数 $a$ 满足 $gcd(a,m)=1$ 。若 $x$ 遍历模 $m$ 的一个既约剩余系，则 $ax$ 也遍历模 $m$ 的一个既约剩余系。
定理：设 $m_1,m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个既约剩余系， $y$ 遍历模 $m_2$ 的一个既约剩余系，则 $m_1y+m_2x$ 遍历模 $m_1m_2$ 的一个既约剩余系。

5.欧拉定理

推论：设 $m,n$ 是两个互素的整数，则 $\phi(mn)=\phi(m)\phi(n)$ 。
定理：若 $m = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ ，则 $\phi(m) = m\prod_{i=1}^{k}(1-{1\over{p_i}})$ 。
证明：当 $m = p^{e}$ 为单个素数的方幂时，在模 $m$ 的完全剩余系 $\{0,1,2,...,p^e-1\}$ 的 $p^e$ 整数中与 $p$ 不互素的只有 $p$ 的倍数，共有 $p^{e-1}$ ，因此与 $p^e$ 互素的数共有 $p^e-p^{e-1}$ ，即 $\phi(p^e)=p^{e}-p^{e-1}=p^e(1-{1\over p})$ ，根据上面的推论有 $\phi(m) = \phi(p_1^{e_1})\phi(p_2^{e_2})...\phi(p_k^{e_k})=\prod_{i=1}^{k}p^{e_i}_i(1-{1\over{p_i}})=m\prod_{i=1}^{k}(1-{1\over{p_i}})$ 。
例子： $\phi(120)=120\cdot(1-{1\over2})(1-{1\over3})(1-{1\over5})=32$
定理：设 $m$ 是正整数， $r\in{Z_m}$ ，若 $gcd(r,m)=1$ ，则存在整数 $s\in{Z_m}$ ，使得 $rs\equiv1(mod\ m)$ ，整数 $s$ 也成为 $r$ 模整数 $m$ 下的乘法逆元。
例子：求 $15\ (mod\ 26)$ 的乘法逆元。
解： $15$ 与 $26$ 互素，存在乘法逆元。做辗转相除法，可得：
$26 = 1\times15+11$
$15 = 1\times11+4$
$11 = 2\times4+3$
$4=1\times3+1$
由此有：
$1 = 4-3$
$\ \ =4-(11-2\times4)$
$\ \ =3\times4-11$
$\ \ =3\times(15-11)-11$
$\ \ =3\times15-4\times11$
$\ \ =3\times15-4\times(26-15)$
$\ \ =7\times15-4\times26$
所以 $15\ mod(\ 26)$ 的乘法逆元为 $7$ 。
欧拉定理：设 $m$ 是正整数， $r\in{Z_m}$ ，若 $gcd(r,m)=1$ ，则 $r^{\phi(m)}\equiv{1}(mod\ m)$ 。

参考文献：

电子科技大学-现代密码学课件。

最后编辑于：2019.12.18 10:19:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342

RSA加密算法数学基础

1.同余类

2.完全剩余系

3.欧拉函数

4.简化剩余系

5.欧拉定理

参考文献：

推荐阅读更多精彩内容