GNU Multiple Precision Arithmetic Library

在開發程式的過程中,程式設計師不一定每一個原件都會純手工打造,事實上,很多東西會直接使用現有的工具。一來可以節省開發的成本,二來自己實作可能也比不上現有工具的功用跟效能(或許還會產生不少BUG)。所以在這裡也會介紹一些好用的工具或是函式庫。當然,前提這些東西都是自由或是能免費取得的。

名稱:GMP~GNU Multiple Precision Arithmetic Library
網址:http://gmplib.org/
功能:提供大數運算

大數運算是一個很重要的功能,特別是在處理數學問題、密碼學演算法上面。傳統C語言所能提供的數字運算,最多是到 double (以 32-bit 的機器來說,通常是 64-bit),但這對動不動就要 128 bit 的密碼學演算法來說,根本不敷使用。今天介紹的這一套 GMP,就是一套提供大數運算的函式庫。這套函式庫很有意思,他還把計算RSA的速率跟 Openssl
進行比較,結果呢,當然是樂勝囉~

這套函式庫提供了整數、分數、小數的型態,下面「稍微」看一下人家是怎麼設計的。我們只看看整數的部分,並且看一下人家的加法是如何處理的。

typedef struct
{
int _mp_alloc; /* Number of *limbs* allocated and pointed
to by the _mp_d field. */
int _mp_size; /* abs(_mp_size) is the number of limbs the
last field points to. If _mp_size is
negative this is a negative number. */
mp_limb_t *_mp_d; /* Pointer to the limbs. */
} __mpz_struct;

mpz 就是GMP中的整數型態。簡單來說,他是拿一串 limb 串起來來當作大數, limb 就是一般程式中所使用的數學型態。(根據平台不同,可能是 unsigned int or unsigned long),然後他還會記錄 size。

我認為,mp_alloc 跟 mp_size 的不同,在於一個是已經 alloc 出來的空間個數,另一個是計算上結果所需的空間個數(不一定一樣,因為可能多 alloc,或是出現進位造成 alloc 不夠),對了,還順便表示正負號。

至於加減法,程式碼在下面。有註解以後還挺好懂得,所以就不說明了。(有些定義沒放上來,但,看命名也知道那是什麼吧)

void
FUNCTION (ARGUMENTS)
{
mp_srcptr up, vp;
mp_ptr wp;
mp_size_t usize, vsize, wsize;
mp_size_t abs_usize;
mp_size_t abs_vsize;

usize = u->_mp_size;
vsize = VARIATION v->_mp_size;
abs_usize = ABS (usize);
abs_vsize = ABS (vsize);

if (abs_usize < abs_vsize)
{
/* Swap U and V. */
MPZ_SRCPTR_SWAP (u, v);
MP_SIZE_T_SWAP (usize, vsize);
MP_SIZE_T_SWAP (abs_usize, abs_vsize);
}

/* True: ABS_USIZE >= ABS_VSIZE. */

/* If not space for w (and possible carry), increase space. */
wsize = abs_usize + 1;
if (w->_mp_alloc < wsize)
_mpz_realloc (w, wsize);

/* These must be after realloc (u or v may be the same as w). */
up = u->_mp_d;
vp = v->_mp_d;
wp = w->_mp_d;

if ((usize ^ vsize) < 0)
{
/* U and V have different sign. Need to compare them to determine
which operand to subtract from which. */

/* This test is right since ABS_USIZE >= ABS_VSIZE. */
if (abs_usize != abs_vsize)
{
mpn_sub (wp, up, abs_usize, vp, abs_vsize);
wsize = abs_usize;
MPN_NORMALIZE (wp, wsize);
if (usize < 0)
wsize = -wsize;
}
else if (mpn_cmp (up, vp, abs_usize) < 0)
{
mpn_sub_n (wp, vp, up, abs_usize);
wsize = abs_usize;
MPN_NORMALIZE (wp, wsize);
if (usize >= 0)
wsize = -wsize;
}
else
{
mpn_sub_n (wp, up, vp, abs_usize);
wsize = abs_usize;
MPN_NORMALIZE (wp, wsize);
if (usize < 0)
wsize = -wsize;
}
}
else
{
/* U and V have same sign. Add them. */
mp_limb_t cy_limb = mpn_add (wp, up, abs_usize, vp, abs_vsize);
wp[abs_usize] = cy_limb;
wsize = abs_usize + cy_limb;
if (usize < 0)
wsize = -wsize;
}

w->_mp_size = wsize;
}

留言

這個網誌中的熱門文章

如何將Linux打造成OpenFlow Switch:Openvswitch

如何利用 Wireshark 來監聽 IEEE 802.11 的管理封包

我弟家的新居感恩禮拜分享:善頌善禱