【文章內(nèi)容簡介】 tr以類似的方式支持從字符串輸入或輸出到字符串。輸入例程可用于為big或flash設(shè)置一大的常量值。通過輸出到字符串，可在實際輸出文件或I/O設(shè)備之前完成格式化。最大可表示基數(shù)為256的值，基數(shù)小于等于60的數(shù)使用09，AZ以及az中的符號。64進制數(shù)字強制使用base64編碼。如有必要，base64數(shù)字輸出時將在結(jié)尾后以 ‘=’符號填充（不會有其它格式）。輸入時，空白字符會被跳過，并忽略填充部分。不要對flash數(shù)字使用base64。不要使用base64輸出負數(shù)（會忽略符號）。如果基數(shù)大于64且不等于64，則將使用ASCII碼0255?；鶖?shù)256在將一行文件當(dāng)作大整數(shù)來解析時有用，如在第8章描述的公鑰加密程序中。例程big_to_bytes和bytes_to_big允許直接在內(nèi)部的big格式和二進制之間進行轉(zhuǎn)換。字符串通常是以零結(jié)尾的。但在使用基數(shù)256時會產(chǎn)生一個問題。在這種情況下0255中的任何一個數(shù)字都可出現(xiàn)在一個數(shù)中，所以零不應(yīng)當(dāng)作字符串的終止符。輸入時應(yīng)采用別的方式來指定字符串中數(shù)字的數(shù)量。通過在調(diào)用innum或instr之前設(shè)置實例變量INPLEN（例如置為25），輸入將在送入25個字符后終止。INPLEN初始為0，并且每次相關(guān)操作都會在返回之前將它重置為0。例如，先初始化一個使用400字節(jié)長的big變量的MIRACL實例：miracl *mip = mirsys(400,256)。使用此基數(shù)，內(nèi)部計算將非常高效。將一個ASCII字符串作為一個256進制數(shù)輸入，它以0結(jié)尾，因為不需要INPLEN：innum(x, stdin)?，F(xiàn)在再輸入一個1024位的隨機值：mipINPLEN=128。innum(y, stdin)。以16進制查看輸出：mipIOBASE = 16。cotnum(w, stdout)。以64進制查看輸出：mipIOBASE = 64。cotnum(w, stdout)。有理數(shù)可以使用小數(shù)點形式（）或分數(shù)形式（例如1/3）來輸入。也可以通過設(shè)備實例變量RPOINT為ON或OFF來選擇以哪一個形式輸出。第四章 內(nèi)部表示大部分語言的編譯器通常提供一到兩種浮點類型用于表達所有實數(shù)，與一到多種整數(shù)類型一起用來描述所有數(shù)字。這些內(nèi)置數(shù)據(jù)類型與底層的計算機架構(gòu)密切相關(guān)，它們通常合理地設(shè)計為對出現(xiàn)頻率更高的較小數(shù)運算得更快，而不是與那些出現(xiàn)頻率領(lǐng)很低的大數(shù)字一樣慢。浮點類型允許使用相對來說小范圍的二進制數(shù)字（例如32位）來以足夠的精度在一個大的動態(tài)范圍內(nèi)表示實數(shù)。整數(shù)類型直接使用相同的二進制值來表示一個限值內(nèi)的所有整數(shù)，或用二進制補碼來表示負數(shù)。傳統(tǒng)的計算機運算方式存在幾個缺陷：1. 浮點和整數(shù)類型是不相容的。整數(shù)集雖然是無窮的，但依然是有理數(shù)的一個子集，而有理數(shù)則是實數(shù)的一個子集。因此每個整數(shù)都有一個等價的浮點表示。不幸的是這兩種表示通常是不一樣的。例如整數(shù)類型會用等價的二進制來表示一個小的正整數(shù)，而浮點類型則會用分開的尾數(shù)和冪來表示。這意味著需要用轉(zhuǎn)換程序來從一種形式轉(zhuǎn)換為另一種形式。2. 大部分有理數(shù)都無法被精確的表示（例如1/3,譯注：貌似1/3是無理數(shù)?。?。事實上浮點系統(tǒng)只能精確地表示那些分母是底層表示的基數(shù)的因子的整數(shù)倍的有理數(shù)。例如我們熟悉的十進制系統(tǒng)只能精確地表示分母是2或5的倍數(shù)的有理數(shù)；1/，而1/...3. 浮點的圓整是依賴于基數(shù)的，而且也是不明顯的錯誤的一個根源。4. 一個事實是整數(shù)和浮點數(shù)據(jù)類型的尺寸由計算機架構(gòu)決定，這使語言設(shè)計者難以保持它們的語言能夠真正可移植。5. 數(shù)字只能以固定的依賴機器的精度來表示。在許多應(yīng)用程序中這是嚴重的缺陷，例如在新興的正在成長的公鑰加密算法領(lǐng)域。6. 基數(shù)依賴的現(xiàn)象是不易考慮的。例如很難從傳統(tǒng)的整形中訪問十進制數(shù)的某一位。這里描述了一組用于直接操作多倍精度有理數(shù)的C例程，多倍精度整數(shù)是其一個兼容子集。同時也可以進行近似的實數(shù)運算。兩個新的數(shù)據(jù)類型是big和flash。前者用于存儲多倍精度整數(shù)，后者以floatingslash(不固定斜杠)的形式用分子和分母來存儲小數(shù)。兩者的格式都是一個固定長度的數(shù)字數(shù)組，外加一個包含符號和長度信息的獨立32位整數(shù)。需要用一種內(nèi)置類型來儲存數(shù)字，這個類型定義為mr_small，它可以是int、long甚至double。struct bigtype{mr_unsign32 L。mr_small *d。}。typedef struct bigtype *big。typedef struct bigtype *flash。定義變量：big x, y[10], z[10][10]。要注意一個big變量僅僅是一個指針，big(或flash)變量實體所需要的內(nèi)存是從堆(也可以從棧)中分配的。因此使用前必須進行初始化。分母長度為0意味著實際上分母是1，分子長度為0意味著實際上分母是1。零本身定義為一個首元素是0的數(shù)字。flash中的斜杠并不在一個固定位置，它依賴于分子和分母的相對尺寸。操作flash時，會將它拆分為分別等于分子和分母的兩個big值。big的操作由提取并操作其中的每個mr_small元素組合而成。為避免可能的溢出，每個元素中的值通常限定在一個比完整的變量所能表示的最大值小的范圍，例如在16位機上是032767（2的15次方 1），但基于2的16次方進行編程也是可以的，C語言不會報告整數(shù)溢出錯誤。系統(tǒng)初始化時用戶必須指定一個固定的尺寸（以字或字節(jié)為單位）和基數(shù)，這兩個值將應(yīng)用于所有big和flash變量?；鶖?shù)的上限與機器字長有關(guān)，可以使用不超過上限的任意值作為基數(shù)。當(dāng)使用一個偏小的基數(shù)b時，系統(tǒng)實際上將使用b*n作為基數(shù)（這能夠更高的效率），n是一個滿足使b*n能被單個機器字表示的最大整數(shù)。當(dāng)使用一個完整寬度的基數(shù)時，程序通常運行得最快。若使用這個基數(shù)，請在調(diào)用mirsys時指定基數(shù)為0。需要注意的是對某些時間關(guān)鍵的例程，這種模式在部分常用的編譯器/處理器組合中是由大量的匯編代碼支持的。例如，對于使用Borland/Turbo C和80x86處理器。將符號和分子、分母的大小信息編碼到單個字中是可行的，C語言包含位操作的完整結(jié)構(gòu)。第五章 實現(xiàn)big類型的算術(shù)運算的實現(xiàn)并沒有太大的創(chuàng)造性，使用的算法是Knuth[Knuth81]。但是做了一些速度優(yōu)化的工作。在耗時的乘除法內(nèi)部，典型的實現(xiàn)是對操作數(shù)的每一位相乘，加上上一次操作的“進位”，將結(jié)果分為一個數(shù)字和對下一個操作的“進位”。以10進制乘法為為例，考慮8723536221 * 9：為了正確地處理數(shù)字5所在的列，需要計算5 * 9 = 45，加上前一列的進位3，得到48，將其中的8作為結(jié)果，4作為對下一列的進位?；镜脑疾僮魇怯嬎?a * b + c) / m的商和余數(shù)。在上例中：a = 5, b = 9, c = 3, m = 10這個操作具有驚人的廣泛用途，并且它處算法的最里層循環(huán)中，因此它的高效實現(xiàn)是非常必要的。對這個MAD(Multiply, Add and Divide)操作，高級語言在實現(xiàn)時通常具有三個難點：1. 慢。2. 商和余數(shù)不能同時作為一次除法的結(jié)果，因此計算過程執(zhí)行兩次，一次用來獲得商，一次用來獲得余數(shù)。3. 即使操作結(jié)果是兩個單值，但中間結(jié)果ab + c可能是雙倍長度的。很慶幸地C語言擁有l(wèi)ong整形可以用來臨時保存這個乘積。因為這些原因，最好用匯編語言來實現(xiàn)這些關(guān)鍵操作。即使C語言的long類型不是雙倍長度（在32位機器上，大部分C編譯器的int和long都是32位），在機器語言層也通常能處理一個臨時的雙倍長度的結(jié)果。MIRACL對big和flash類型使用固定長度的數(shù)組，這是為了避免可變長度方式下需要進行內(nèi)存分配和碎片收集的困難度和時間消耗。這也意味著在對big值進行計算時，所有的結(jié)果和中間數(shù)者必須小于等于在mirsys中指定的固定尺寸。在實踐中，穩(wěn)態(tài)計算中涉及的數(shù)字的尺寸大多相近。除非兩個數(shù)相乘導(dǎo)致產(chǎn)生一個雙倍長度的中間結(jié)果，但這也通常會接下來立即在一次除法操作中縮小。這種情況的一個典型的例子是PollardBrentl因式分解。請注意上面提到的問題的另一個微觀表現(xiàn)。只是為了拷貝這些偶然出現(xiàn)的中間值，而為每個變量分配所需大小的兩倍的存儲是很可惜的。因此，MIRACL庫提供了一個特殊的Multiply,Add,Divide例程(名為mad)。它已經(jīng)被證明在內(nèi)存受限的機器上實現(xiàn)大型程序（像PomeranceSilvermanMontgomery因式分解）時非常有用。除了基本的算法運算，以下例程也有提供：1. 生成和判斷質(zhì)數(shù)，使用概率質(zhì)數(shù)判斷方法[Knuth81]。2. 生成隨機big和flash，基于subtractwithborrow生成器[Marsaglia]。但是請注意內(nèi)部實現(xiàn)的的基本隨機數(shù)生成器并不具有秘密安全性（cryptographicly secure，保密性？）。在真實的加密應(yīng)用程序中，它是不夠可靠的。3. 計算冪和根。4. 實現(xiàn)了普通的和擴展的歐幾里得最大公約數(shù)(Euclidean GCD)算法。5. 實現(xiàn)了中國剩余定理[Knuth81]，以及計算雅可比符號(Jacobi Symbol)[Reisel]。6. 超大數(shù)的乘法，使用快速傅里葉變換(Fast Fourier Transform)[Pollard71]。在進行大規(guī)模模運算(modular arithmetic)時，一個時間上的關(guān)鍵操作是模乘，就是對兩個數(shù)進行乘法之后再除以一個固定的n，取其余數(shù)。一個明顯的解決方案是用之前提到的mad例程來完成，但Montgomery提出了一種替代方案，這要求要求先將兩個數(shù)轉(zhuǎn)換為特殊的nresidue樣式，在nresidue樣式下可以通過一個完全沒有用到除法的特殊例程更快的完成模乘操作，然后再將結(jié)果轉(zhuǎn)換為普通格式。請注意nresidue的模加與模減操作與普通的類似，使用相同的例程。 鑒于要求對變量進行nresidue格式轉(zhuǎn)換，Montgomery算法只應(yīng)考慮用于對同一個模數(shù)進行大量模運算的計算場合。這在C++環(huán)境中使用更為方便，因為屏蔽了這些細節(jié)。MIRACL庫中的許多要進行大量模運算的例程在內(nèi)部使用了蒙哥馬利算法，如高度優(yōu)化的模冪(modular exponentiation)函數(shù)powmod，以及實現(xiàn)GF(P)橢圓曲線運算的函數(shù)，可以在參考手冊中找到相關(guān)信息。為了達到最快的模運算，同時還必須使用匯編，針對特定的模數(shù)或特定尺寸的模數(shù)進行優(yōu)化等方法。有相當(dāng)數(shù)量的技術(shù)可供使用：首先是Comba和KCM方法。這是通過宏展開程序mex自動完成的。為使嵌入的程序獲得盡可能快的性能，當(dāng)沒有與您的編譯器/，建議你自己創(chuàng)建一個。另外有兩種在一定程序上屬于實驗性的技術(shù)，僅適合于80x86系列處理器和Borland C++編譯器。在滿足條件時，相應(yīng)的代碼將被自動調(diào)用。請務(wù)必注意上述四種技術(shù)要求編譯器支持內(nèi)聯(lián)匯編，而且后兩者僅用Borland C++ 。第一種方法的思路是對乘法和歸約過程(multiplication and reduction process)中隱含的循環(huán)進行完全的分解和重組，由[Comba]首先提出，[Scott96]對其進行了修改。這種方法必須使用固定寬度的模數(shù)并在編譯時確定(，以字為單位)。對中小尺寸的模數(shù)這種方法工作得很好，尤其是在GF(p)橢圓曲線加密算法中。若要獲得比這還要快的速度，歸約過程可對某些具有特別簡單的樣式(particularly simple form)的模數(shù)進行優(yōu)化。針對