# 算法实现
模逆算法，对于素域来说，
void gm_bn_inv(gm_bn_t r, const gm_bn_t a, const gm_bn_t m) {
gm_bn_t e;
gm_i_bn_sub(e, m, GM_BN_TWO);
gm_bn_exp(r, a, e, m);
}
1
2
3
4
5
2
3
4
5
# 优化
对参数p的模逆，大家可以参考gmssl-v3-dev的优化算法进行优化，当然对于移动端使用来说，目前的算法效率完全够用了。
另外大家也可以参照：https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion (opens new window)，这里提到的优化方法进行优化。
其实原理就是把模幂展开，将一部分计算进行合并，减少模乘及模平方的次数，来达到优化效果。因为参数p及参数n都是固定的，所以可以展开，寻找最优算法。
另外，最简单可做的优化就是事先计算好m-2的值。
# 单元测试
main函数增加：
TEST_BN_ALG("gmp_inv",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"9DDD52AF95B748A553D1B1E106627F901CD453F067A0D50202C672130C90F607",
"BFA4C3D86516875A89E9CD9123288DB4510188032D6EE254EBAF282C905A9A00");
TEST_BN_ALG("gmn_inv",
"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
"9DDD52AF95B748A553D1B1E106627F901CD453F067A0D50202C672130C90F607",
"7F1CBEE6FBB9F2C2309A2E889A7FB21DE461013281C15DC939286F04EB9416AC");
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
test_bn函数增加：
// 这里求逆后进行了异或，这是为了避免循环多次都在来回求逆，达不到测试算法正确性的目的，有一定性能损耗
else if(strcmp(alg, "inv") == 0){ // 1万
gm_bn_to_mont(bnr, bna, m);
for (i = 0; i < 10000; i++) {
gm_bn_inv(bnr, bnr, m);
gm_bn_from_mont(bnr, bnr, m);
for(j = 0; j < 8; j++) {
bnr[j] = bnr[j] ^ bnb[j];
}
gm_bn_to_mont(bnr, bnr, m);
}
gm_bn_from_mont(bnr, bnr, m);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
算法效率：
saintdeMacBook-Pro:bn saint$ time ./a.out gmp_inv
r = BFA4C3D86516875A89E9CD9123288DB4510188032D6EE254EBAF282C905A9A00
test result: ok
real 0m6.011s
user 0m5.901s
sys 0m0.039s
saintdeMacBook-Pro:bn saint$ time ./a.out gmn_inv
r = 7F1CBEE6FBB9F2C2309A2E889A7FB21DE461013281C15DC939286F04EB9416AC
test result: ok
real 0m5.494s
user 0m5.395s
sys 0m0.036s
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
未经本人同意，禁止转载！