# 算法实现
平方比较简单,未做过多优化,如果用汇编实现的话,可以优化一下,少一部分的乘法,效率有一定的提升,汇编执行2亿次乘法6.25s,平方5s,相差1.2s左右。
实现代码如下:
void gm_bn_sqr(gm_bn_t r, const gm_bn_t a, const gm_bn_t m) {
gm_bn_mont_mul(r, a, a, m);
}
1
2
3
2
3
# 单元测试
main函数增加:
TEST_BN_ALG("gmp_sqr",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"0000000000000000000000000000000000000000000000000000000000000000",
"D34B72070B8ED7CFA57E42CAAFC947B88AE9C241224110D0E7A4883B3FB787E3");
TEST_BN_ALG("gmn_sqr",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"0000000000000000000000000000000000000000000000000000000000000000",
"64FC21F78304770E66FDF83E8E29C632A1EE34A64B323FA9C9208D9F5D1B25F1");
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
test_bn函数增加:
else if(strcmp(alg, "sqr") == 0){ // 1千万
gm_bn_to_mont(bnr, bna, m);
for (i = 0; i < 10000000; i++) {
gm_bn_sqr(bnr, bnr, m);
}
gm_bn_from_mont(bnr, bnr, m);
}
1
2
3
4
5
6
7
2
3
4
5
6
7
算法效率:
saintdeMacBook-Pro:bn saint$ time ./a.out gmp_sqr
r = D34B72070B8ED7CFA57E42CAAFC947B88AE9C241224110D0E7A4883B3FB787E3
test result: ok
real 0m12.256s
user 0m12.011s
sys 0m0.087s
saintdeMacBook-Pro:bn saint$ time ./a.out gmn_sqr
r = 64FC21F78304770E66FDF83E8E29C632A1EE34A64B323FA9C9208D9F5D1B25F1
test result: ok
real 0m12.278s
user 0m12.024s
sys 0m0.087s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
未经本人同意,禁止转载!