最近在做RSA加密算法，急需要对大数（很大的数，一般来说是十进制500位以上的数字）进行加法和乘法操作。这就需要对如此大的数操作很快才可以。自然而然，我就想到了Python，它天生就支持大数操作。所以我的RSA也是用Python实现的。

简单地搜了一下网上的一些实现，用C的基本上都采用了gmp库，很牛的一个数字计算的库，接口很方便，而且效率也很乐观。下载一个其中一个还算漂亮的实现，速度超快。相比之下，我的Python程序就慢成马了，难以容忍，优化了一下循环，替换了一个判断素数的算法，效率还是低得出奇。无奈之下，向Herbert求救，在他的提示下，对C和Python的大数操作benchmark了一番。

我用的源代码如下：（声明：C代码编写仓促，很是丑陋，勿模仿！）

include

include

include

include

include

void timediff(struct timeval a,struct timeval b,struct timeval* result)
{
(result)->tv_sec = (a)->tv_sec - (b)->tv_sec;
(result)->tv_usec = (a)->tv_usec - (b)->tv_usec;

if((result)->tv_usec tv_sec;
    (result)->tv_usec += 1000000;
}

}

int main(void)
{
int i;
mpz_t p, q, r;
struct timeval before, after, diff;
char p_str[1024] = {‘1’,};
char q_str[1024] = {‘1’,};

mpz_init(p);
mpz_init(q);
mpz_init(r);
srand(time(NULL));

for(i=1;i<1024;i++)
    p_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;

for(i=1;i<1024;i++)
    q_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;
mpz_set_str(p, p_str, 10);
mpz_set_str(q, q_str, 10);

gettimeofday(&before, NULL);
mpz_add(r, p, q);
gettimeofday(&after, NULL);
timediff(&after, &before, &diff);
printf("add needs time:");
printf("n%-15s : %ld","Seconds", diff.tv_sec);
printf("n%-15s : %ld","Microseconds", diff.tv_usec);
puts("");

gettimeofday(&before, NULL);
mpz_mul(r, p ,q);
gettimeofday(&after, NULL);
timediff(&after, &before, &diff);
printf("multiply needs time:");
printf("n%-15s : %ld","Seconds", diff.tv_sec);
printf("n%-15s : %ld","Microseconds", diff.tv_usec);
puts("");

mpz_clear(r);
mpz_clear(q);
mpz_clear(p);
return 0;

}

!/usr/bin/env python

import time
import string
import random

p = q = r = 0
BIG_NUM = []

for i in range(1024):
BIG_NUM.append(random.choice(‘0123456789’))

p = int(‘’.join(BIG_NUM))

for i in range(1024):
BIG_NUM[i] = random.choice(‘0123456789’)

q = int(‘’.join(BIG_NUM))

before = time.time()
r = p+q
after = time.time()

print r

print “Add needs time: %f us”%((after - before)1000.01000.0)

before = time.time()
r = p*q
after = time.time()

print r

print “Multiply needs time: %f us”%((after - before)1000.01000.0)

实验结果如下：
(C version, compiled with gcc -O9)
$ ./bench
add needs time:
Seconds : 0
Microseconds : 5
multiply needs time:
Seconds : 0
Microseconds : 11

(Python version)
$ ./bench.py
Add needs time: 15.020370 us
Multiply needs time: 207.901001 us

-_-b 刚才搞错进制了。。。 1 second=1000*1000 microseconds 这下对了。Python确实比C慢。抑或是真正的问题出在这里？而不在我的算法？

顺便也在这里问一下：有没有什么好的寻找大素数的算法？？
（整个RSA实现会在以后的文章中贴出。）