這篇紀錄一些RSA運算時要用到的數學定理和我比較能夠理解的證明

同餘理論

定義
對於整數 a,b，若正整數 m 能整除 a-b ，以符號表示就是 m | (a-b) ，則稱為 a,b 對於模 m 同餘，可以寫成
$a-=b(mod m)$

由此定義可以推導出
$a-=b (mod m) <=> a mod m = b mod m$

證明1：

$a ≡ b (mod m) ⇒ a mod m = b mod m$

$a-=b (mod m) => a mod m = b mod m$
令

$a=mp+r , b=mq+s$ (r,s為餘數)

$a -= b (mod m)$

$a-=b(mod m)$

$=> m |(a-b)$

$=> m | m(p-q)+(r-s)$

$=> m |(r-s)$

r,s是除以m的餘數，

$0 <= r,s < m$

$=>0 <= |r-s| < m$

$=>r-s =0$

$=>r=s 得證$

證明2：

$a mod m = b mod m ⇒ a -= b (mod m)$
a,b 除以 m 餘數相同
令

$a=mp+r,b=mq+r$

$=>a-b = m(p-q)$

$=> m | m(p-q)$

$=> m | a-b$

$=> a -= b (mod m) 得證$

由證明1,2得知

$a-=b (mod m) <=> a mod m = b mod m$

(*) 也有看過將 a ≡ b (mod m)定義成 a,b 除以m餘數相同，再由此定義去推導出

$a -= b (mod m) <=> m |(a-b)$

同餘的性質

1.反身性(reflexive) $a -= a (mod m)$
2.對稱姓(symmetric) $a -= b (mod m) => b -= a (mod m)$
3.遞移性(transitive) $a -= b (mod m), b -= c (mod m) => a -= c (mod m)$
4.加姓 $a -= b (mod m), c -= d (mod m) => a+c -= b+d (mod m)$
5.乘性 $a -= b (mod m), c -= d (mod m) => ac -= bd (mod m)$
6.冪性 $a -= b (mod m),k>=0 => a^k -= b^k (mod m)$
7.
$\left. \begin{matrix} a \equiv b \pmod{m} \\ n|m \end{matrix} \right\} \Rightarrow a \equiv b \pmod n$
8.
$\left. \begin{matrix} a \equiv b \pmod{m_1} \\ a \equiv b \pmod{m_2} \\ \vdots \\ a \equiv b \pmod{m_n} \\ (n \ge 2) \end{matrix} \right\} \Rightarrow a \equiv b \pmod{lcm(m_1,m_2,\cdots,m_n)}$

證明
1.反身性

$m|(a-a)$

$=>a -= a (mod m)$

2.對稱姓

$m|(a-b)$

$令a-b=mk$

$=>b-a=-mk$

$=>m|-mk$

$=>m|(b-a)$

$=>b -= a (mod m)$

3.遞移性

$a -= b (mod m)$

$=>m|(a-b),令a-b=p m$
同理，令

$b-c=qm$

$(a-b)+(b-c)=pm+qm$

$a-c=(p+q)m$

$=>m|(a-c)$

$=> a -= c (mod m)$

4.加性

$a -= b (mod m)$

$=>m|(a-b),令a-b=p m$
同理，令

$c-d=qm$

$=>(a+c)-(b+d)=(p+q)m$

$=>m|(a+c)-(b+d)$

$=>a+c -= b+d (mod m)$

5.乘性
同上

$a=b+p m,c=d+qm$

$=>ac=bd+m(bq+dp+pqm)$

$=>ac-bd=m(bq+dp+pqm)$

$=>m|ac-bd$

$=>ac -= bd (mod m)$

6.冪性
利用乘性即可推倒

$a-=b (mod m),a-=b (mod m)$

$=>aa-=bb (mod m)$

$=>a^2=>b^2 (mod m)$
再用歸納法就能推出

$=>a^k=>b^k (mod m)$

7.

$a-=b (mod m)$

$令a-b=km$

$n|m$

$令m=ln$

$=>a-b=lkn$

$=>a-=b (mod n)$

8.

$(a-b)同時被m_1,m_2,...,m_n整除$

$=>lcm(m_1,m_2,...,m_n)|(a-b)$

$=>a-=b (mod lcm(m_1,m_2,...,m_n))$

模反元素(Modular multiplicative inverse)

整數a的模反元素為整數x，x滿足 $ax-=1(mod m)，x可寫成a^-1$
$模反元素存在的充分必要條件為a與m互質$

歐拉函式(Euler's totient function)

定義： $\phi(n)$ 為小於等於 $n$ 的正整數中與 $n$ 互質的個數

若

$p$ 為質數

$因為<=p的正整數都和p互質$

$=>phi(p)=p-1$

若

$n=p^a$ ，則小於等於

$n$ 的正整數中，
和

$n$ 有公因數的為

$p,2p,...,p^(a-1)p$

$=>\phi(n)=p^a-p^(a-1)$

$=p^a-p^(a-1)$

若

$n=pxxq,p,q 為兩相異質數，求\phi(n)$

第一步：扣除含有

$p$ 這個因數的數

$p,2p,...,n/p p,共n/p個$

$n-n/p=n(1-1/p)$
第二步：再扣除含有

$q$ 這個因數的數
n(1-1/p)-n/q
第三步：含有

$pq$ 這個因數的數倍多扣了一次，再加回來

$\phi(n)=n(1-1/p)-n/q+n/(pq)$

$=n(1-1/p)(1-1/q)$

$=(p-1)(q-1)$

通式寫成

$\phi(n)=n\prod_(p|n)(1-1/p)$

這個證明還沒看懂

在RSA演算法中會用到的只會有2個因數

$n=pq$ , $p,q$ 為兩相異質數
$\phi(n)=(p-1)(q-1)$

費馬小定理

假如a是一個整數，p是一個質數，那麼a^p - a 是p的倍數，可以表示為
$a^p \equiv a \pmod{p}$
如果a不是p的倍數，這個定理也可以寫成
$a^{p-1} \equiv 1 \pmod{p}$

證明
1.若

$p$ 整除

$a$ ，

$p$ 也整除

$a^p$

$=>a^p-=a (mod p)$

2.若

$p$ 不整除

$a$

令集合

$S_1$ 為

${1,2,...,p-1}$
令集合

$S_2$ 為

$S_1xxa形成的集合{a,2a,...,(p-1)a}$

$S_1為所有mod p可能出現的值形成的集合(0 除外)$

$S_2的值mod p之後都會對應到S_1而且不會重複$ ，這點可以用反證法證明

$假設存在整數 k,l$

$k != l$ ,

$1 <= k,l < p$ 使得

$ka -= la (mod p)$ 又因為

$1 <= k , l < p$ ，上式要成立必須

$k=l$ ，與假設矛盾

$=>S_2的值mod p之後都會對應到S_1而且不會重複$

$令S_1所有值的乘積為W則S_2所有值的乘積為a^(p-1)W$

$a^(p-1)W -= W (mod p)$
因為

$gcd(W,p) = 1可以同除W$

$a^(p-1) -= 1 (mod p)$

Jimmy's Blog

RSA非對稱加密演算法 (二) 數學理論

同餘理論

定義
對於整數 a,b，若正整數 m 能整除 a-b ，以符號表示就是 m | (a-b) ，則稱為 a,b 對於模 m 同餘，可以寫成
$a-=b(mod m)$

由此定義可以推導出
$a-=b (mod m) <=> a mod m = b mod m$

同餘的性質

模反元素(Modular multiplicative inverse)

整數a的模反元素為整數x，x滿足 $ax-=1(mod m)，x可寫成a^-1$
$模反元素存在的充分必要條件為a與m互質$

歐拉函式(Euler's totient function)

定義： $\phi(n)$ 為小於等於 $n$ 的正整數中與 $n$ 互質的個數

$n=pq$ , $p,q$ 為兩相異質數
$\phi(n)=(p-1)(q-1)$

費馬小定理

假如a是一個整數，p是一個質數，那麼a^p - a 是p的倍數，可以表示為
$a^p \equiv a \pmod{p}$
如果a不是p的倍數，這個定理也可以寫成
$a^{p-1} \equiv 1 \pmod{p}$

沒有留言:

張貼留言

RSA非對稱加密演算法 (二) 數學理論

同餘理論

定義 對於整數 a,b，若正整數 m 能整除 a-b ，以符號表示就是 m | (a-b) ，則稱為 a,b 對於模 m 同餘，可以寫成 a≡b(modm)a-=b(mod m) 由此定義可以推導出 a≡b(modm)⇔amodm=bmodma-=b (mod m) <=> a mod m = b mod m

同餘的性質

模反元素(Modular multiplicative inverse)

整數a的模反元素為整數x，x滿足 ax≡1(modm)，x可寫成a-1ax-=1(mod m)，x可寫成a^-1 模反元素存在的充分必要條件為a與m互質模反元素存在的充分必要條件為a與m互質

歐拉函式(Euler's totient function)

定義：ϕ(n)\phi(n)為小於等於nn的正整數中與nn互質的個數

n=pqn=pq , p,qp,q 為兩相異質數 ϕ(n)=(p-1)(q-1)\phi(n)=(p-1)(q-1)

費馬小定理

假如a是一個整數，p是一個質數，那麼a^p - a 是p的倍數，可以表示為 ap≡a(modp)a^p \equiv a \pmod{p} 如果a不是p的倍數，這個定理也可以寫成 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

沒有留言:

張貼留言

定義
對於整數 a,b，若正整數 m 能整除 a-b ，以符號表示就是 m | (a-b) ，則稱為 a,b 對於模 m 同餘，可以寫成
$a-=b(mod m)$

由此定義可以推導出
$a-=b (mod m) <=> a mod m = b mod m$

整數a的模反元素為整數x，x滿足 $ax-=1(mod m)，x可寫成a^-1$
$模反元素存在的充分必要條件為a與m互質$

定義： $\phi(n)$ 為小於等於 $n$ 的正整數中與 $n$ 互質的個數

$n=pq$ , $p,q$ 為兩相異質數
$\phi(n)=(p-1)(q-1)$

假如a是一個整數，p是一個質數，那麼a^p - a 是p的倍數，可以表示為
$a^p \equiv a \pmod{p}$
如果a不是p的倍數，這個定理也可以寫成
$a^{p-1} \equiv 1 \pmod{p}$