尽快使用 OpenSSL 的 BIGNUM 拆分数字

Question

我正在为任意精度数字使用 OpenSSL 的 BIGNUM 库。

我需要将一个号码分成两部分。我需要一个数字中的前 n 位 [0, n-1]（我指的是 n 个最低有效位），以及另一个数字中的其余位 [n, end]。

我的有效代码是这个

void number_split(BIGNUM * first_n_bits, BIGNUM * the_rest, BIGNUM * number, long n) {
    int i = 0;

    BN_copy(first_n_bits, number);

    int bits = BN_num_bits(first_n_bits);

    while(bits > n) {
        BN_clear_bit(first_n_bits, --bits);
    }

    if(BN_num_bits(number) > n) {
        BN_rshift(the_rest, number, n);
    } else {
        BN_copy(the_rest, zero);
    }
}

我确定这个函数是影响我的应用程序执行时间的最大因素之一，所以让它快一点对我有很大帮助。

似乎可以改进的部分是 while 循环，我在其中一次清除一个最高有效位。我原以为 BIGNIM 会有一个函数可以更有效地完成它，但我找不到它。

那么，我该怎么做才能让它更快？

Answer 1

您可以使用 BN_mask_bits() 函数，这应该比逐位循环更快。

// BN_num_bits(num) must be >= n
void number_split(BIGNUM *low_bits, BIGNUM *high_bits, BIGNUM *num, long n) {
  BN_copy(low_bits, num);
  BN_mask_bits(low_bits, n);
  BN_rshift(high_bits, num, n);
}

如果有可能 BN_num_bits(num) < n 则添加检查：

void number_split(BIGNUM *low_bits, BIGNUM *high_bits, BIGNUM *num, long n) {
  BN_copy(low_bits, num);
  if(BN_num_bits(num) <= n) {
    BN_copy(high_bits, zero);
  } else {
    BN_mask_bits(low_bits, n);
    BN_rshift(high_bits, num, n);
  }
}

尽快使用 OpenSSL 的 BIGNUM 拆分数字

split a number using OpenSSL's BIGNUM as quickly as possible

c

openssl

bignum