一種基于Verilog的大整數(shù)除法器的實(shí)現(xiàn).pdf

1、隨著計(jì)算機(jī)網(wǎng)絡(luò)和現(xiàn)代信息技術(shù)的蓬勃發(fā)展，大整數(shù)的除法作為一項(xiàng)基本運(yùn)算在各種場合扮演著越來越重要的作用。在物理學(xué)、生物學(xué)和化學(xué)等學(xué)科的許多研究中，都離不開大整數(shù)的除法運(yùn)算。而在信息安全領(lǐng)域，眾多加解密技術(shù)如 RSA、ECC、DSA以及ElGamal等公鑰密碼算法更是以大整數(shù)的運(yùn)算為基礎(chǔ)的，而大整數(shù)的除法運(yùn)算正是大整數(shù)運(yùn)算的重要組成部分之一，因此，如何快速完成大整數(shù)的除法運(yùn)算，對這些加解密算法起著至關(guān)重要的作用。盡管在很多場合下，研究人員更

2、多的是采用C語言或者C++來實(shí)現(xiàn)大整數(shù)的各項(xiàng)運(yùn)算算法，但是由于這些加密算法都會運(yùn)用到芯片的加密程序中，因此大整數(shù)除法的硬件實(shí)現(xiàn)就顯得格外重要了。
　　由于在眾多硬件描述語言中，Verilog HDL語言效率高，靈活性強(qiáng)，而且最為常用，因此本文目標(biāo)是以Verilog HDL語言為基礎(chǔ)，實(shí)現(xiàn)位寬達(dá)到2048位的被除數(shù)對除數(shù)進(jìn)行相除的大整數(shù)除法器。本文首先對包括除法在內(nèi)的大整數(shù)的運(yùn)算的重要性及意義做了簡明扼要的闡述，并且對從大整數(shù)除法得

3、到重視以來科學(xué)家們對其的研究與實(shí)現(xiàn)所做的大量工作做了一定的介紹。然后對大整數(shù)的存儲方法以及表示方法進(jìn)行了說明，接著分析了大整數(shù)的加法、減法以及乘法的算法思想及實(shí)現(xiàn)思路，并且對常見的幾種大整數(shù)的除法算法盡行了分析和比較之后，確定使用估商試除法的思想來最終完成大整數(shù)除法器的設(shè)計(jì)。對于估商試除法來說，最關(guān)鍵的一步就是估商的過程，因?yàn)閷ι痰墓烙?jì)越準(zhǔn)確，后續(xù)對商的糾正工作就會越簡單，否則，修正商就會浪費(fèi)大量的時間與空間。因此在對商的估計(jì)與修正中，

4、采用了唐納德.克努特于六十年代提出的估商算法，這個算法可以使估商的誤差不大于2，使得整個除法的運(yùn)算量得到大大簡化。
　　本文花了最大篇幅對大整數(shù)除法器的實(shí)現(xiàn)過程進(jìn)行了詳細(xì)的介紹。在確定了采用克努特估商算法聯(lián)合試除法的思想來設(shè)計(jì)除法器之后，本文首先明確了整個除法的運(yùn)算過程和步驟，并以此為基礎(chǔ)設(shè)計(jì)了除法器的主體架構(gòu)。然后根據(jù)大整數(shù)除法器的主體架構(gòu)對各個模塊進(jìn)行了劃分，并最終完成設(shè)計(jì)和驗(yàn)證工作。本文所設(shè)計(jì)的大整數(shù)除法器可以完成被除數(shù)位寬