# 算法实现
蒙哥马利算法也比较简单，大家套算法就行，具体实现：
void gm_bn_exp(gm_bn_t r, const gm_bn_t a, const gm_bn_t b, const gm_bn_t m) {
gm_bn_t t;
uint64_t w;
int i, j;
// set t to mont one
gm_bn_to_mont(t, GM_BN_ONE, m);
for (i = 7; i >= 0; i--) {
w = b[i];
for (j = 0; j < 32; j++) {
gm_bn_sqr(t, t, m);
if (w & 0x080000000ULL) {
gm_bn_mont_mul(t, t, a, m);
}
w <<= 1;
}
}
gm_bn_copy(r, t);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 单元测试
main函数增加：
TEST_BN_ALG("gmp_exp",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"9DDD52AF95B748A553D1B1E106627F901CD453F067A0D50202C672130C90F607",
"161F67FA7D66D931B1B743EFA1E66F141324C3A3AF7C5A32D124007AF44BEABA");
TEST_BN_ALG("gmn_exp",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"9DDD52AF95B748A553D1B1E106627F901CD453F067A0D50202C672130C90F607",
"F0A72A00F0DB40E177BF56EE177EC88D11BD928AE097973060CFDBDFDDB04146");
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
test_bn函数增加：
else if(strcmp(alg, "exp") == 0){ // 1万
gm_bn_to_mont(bnr, bna, m);
for (i = 0; i < 10000; i++) {
gm_bn_exp(bnr, bnr, bnb, 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_exp
r = 161F67FA7D66D931B1B743EFA1E66F141324C3A3AF7C5A32D124007AF44BEABA
test result: ok
real 0m4.949s
user 0m4.699s
sys 0m0.053s
saintdeMacBook-Pro:bn saint$ time ./a.out gmn_exp
r = F0A72A00F0DB40E177BF56EE177EC88D11BD928AE097973060CFDBDFDDB04146
test result: ok
real 0m4.775s
user 0m4.615s
sys 0m0.040s
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
未经本人同意，禁止转载！