大素数阶有限域上的乘法运算

mathe

我试了下用ipp对两个随机256比特大整数相乘。如果把cpu类型设置成未知，64位比32位快3倍，这个好理解。设成支持sse2,结果32位和64位速度相同。但是改成sse3以后，32位速度没有提升，但是64位提升将近3倍

liangbch

Intel 对自己的CPU最了解。它家的库对自己的CPu优化的很好。
看来我们需要好好研究下SSE3指令的乘法运算。

mathe

很简单的乘法代码:

1. #include <ippcp.h>
   
2. #include <ippcore.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. #define COUNT 1000000000
   
6. int _tmain(int argc, _TCHAR* argv[])
   
7. {
   
8.     int bignumsize512=0;
   
9.     int bignumsize256=0;
   
10.     IppsBigNumState *pSum = NULL;
    
11.     IppsBigNumState *pMul = NULL;
    
12.     unsigned int data[256/32];
    
13.     srand((int)time(NULL));
    
14.     ippInit();
    
15.     IppStatus error_code = ippsBigNumGetSize(512/32, &bignumsize512);
    
16.     if(error_code != ippStsNoErr)
    
17.         return -1;
    
18.     error_code = ippsBigNumGetSize(256/32, &bignumsize256);
    
19.     if(error_code != ippStsNoErr)
    
20.         return -1;
    
21.     int i;
    
22.     for(i=0;i<256/32;i++)data[i]=rand()*65536+rand();
    
23.     pSum = (IppsBigNumState *)malloc(bignumsize512);
    
24.     pMul = (IppsBigNumState *)malloc(bignumsize256);
    
25.     error_code = ippsBigNumInit(512/32, pSum);
    
26.     ippsBigNumInit(256/32, pMul);
    
27.     ippsSet_BN(IppsBigNumPOS, 256/32, data, pMul);
    
28.     time_t start = time(NULL);
    
29.     for(i=0;i<COUNT;i++){
    
30.         ippsMul_BN(pMul, pMul, pSum);
    
31.     }
    
32.     printf("Total cost %d seconds\n", (int)(time(NULL)-start));
    
33.         return 0;
    
34. }
    

复制代码

$10^9$次乘法，ipp8.0, 64位代码30秒，32位机器73秒
如果换成ipp7.0, 64位代码63秒，32位95秒

mathe

64位机器上做256比特乘法直接做16次乘法效率相当快了。就是不知道是否可以用toom-cook算法改进。比如分为52*5,只是toom-5不是很好设计。另外一个可以考虑的是如果我们改成支持56＊4=224比特，效率是否可以高很多，toom-4只要7次乘法加些额外加减移位运算即可

liangbch

256bit仅仅相当于8个机器字（32位模式）或者4个机器字（64位）模式，这种规模，硬乘法是最快的，toom-cook乘法运算的减少不足以抵消额外的加减和复制等操作的开销。

mathe

普通两256比特整数乘法需要16次64比特整数乘法，而一个256比特整数平方需要10次64比特整数乘法
找到一篇文章: A Cryptographic Library for the Motorola DSP56000，利用其中算法，做一次Montgomery Reduce只需要20次64比特整数乘法。（远远好于二次乘法）

无心人

现在的CPU 5周期1次乘法，是不是256位乘，能在200周期完成？