RSA之歐拉02(未完成)

blacksapper

從今天開始連載.兩年前我做過相關(guān)的準(zhǔn)備.現(xiàn)在打算用C和java分別實(shí)現(xiàn)RSA算法.文章不定期更新.今天實(shí)現(xiàn)的是歐拉函數(shù).

關(guān)于如何求質(zhì)數(shù)表可以看http://blog.chinaunix.net/space.php?uid=25887681&do=blog&id=379066

我先采用老師的優(yōu)化算法b.如果是大數(shù)運(yùn)算可以使用確定性算法.這個(gè)太費(fèi)時(shí)間了.

計(jì)劃就是

1.能夠生成密鑰.分為確定性算法和不確定算法

2.能夠加密和解密

3.支持2048位(2進(jìn)制)的大質(zhì)數(shù)運(yùn)算.

算法寫出來更新下面部分.

公式是

Euler(n)=TT(pi-1)*pi^(ai-1) TT表示加氏積.i表示數(shù)字下標(biāo).

比如24=3*2^3 Euler(24)=(3-1)*3^(1-1)*(2-1)*2(3-1)=8

也就是1 5 7 9 11 13 17 19 23

Euler公式如果n=p*q且p、q都是質(zhì)數(shù)則n=(p-1)*(q-1)如果是其中一個(gè)是合數(shù)就用上面的公式.

上面的公式包含下面的特例.

先實(shí)現(xiàn)基礎(chǔ)算法.后實(shí)現(xiàn)大數(shù)運(yùn)算.

寫出來了貼出來.

(未完成)