分布式計(jì)算環(huán)境下大整數(shù)分解的研究.pdf

1、大整數(shù)分解問(wèn)題歷來(lái)是數(shù)學(xué)家們關(guān)注的熱點(diǎn)問(wèn)題。隨著信息技術(shù)的飛速發(fā)展，以RSA為代表的公鑰密碼體制得到了廣泛的應(yīng)用。RSA的安全性基于大整數(shù)分解是困難的這一命題，即：找到兩個(gè)大素?cái)?shù)并計(jì)算它們的乘積是容易的，而知道這個(gè)乘積逆向求它的因子是困難的。 隨著計(jì)算機(jī)硬件水平的提高和分解算法的發(fā)展，大整數(shù)分解的速度得到了極大提高。因此，在過(guò)去的十年中，RSA的密鑰長(zhǎng)度從512位提高到1024位，對(duì)于長(zhǎng)久保存的信息則要求使用2048位。此外，分

2、布式計(jì)算技術(shù)的發(fā)展也極大的推動(dòng)了分解能力的提高。其中，作為分布式計(jì)算技術(shù)的典型代表，由Ian Foster博士在上個(gè)世紀(jì)90年代提出的網(wǎng)格計(jì)算代表了計(jì)算機(jī)分布式技術(shù)的發(fā)展水平。 本文以大整數(shù)分解算法和網(wǎng)格計(jì)算技術(shù)的研究為基礎(chǔ)，對(duì)多個(gè)多項(xiàng)式的二次篩法（MPQS）的分布式實(shí)現(xiàn)技術(shù)進(jìn)行了重點(diǎn)研究。針對(duì)算法實(shí)現(xiàn)過(guò)程中的小乘因子選取、分解參數(shù)的選取、多項(xiàng)式的生成等問(wèn)題，進(jìn)行了深入的分析和討論；通過(guò)對(duì)參數(shù)及結(jié)果傳遞的各種方案比較，結(jié)合網(wǎng)格計(jì)