Closed fjarri closed 1 year ago
Patch coverage: 100.00
% and project coverage change: +0.01
:tada:
Comparison is base (
4a29760
) 98.61% compared to head (8739568
) 98.63%.
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.
Option<usize>
in random prime generation functions, to avoid repetition of the size in most cases (where it is equal to the Uint size)MR is the first check that's being run after the sieve, so this can noticeably increase the performance. For example, for the case of
U256
and a 128 bit bound the speedup ofsafe_prime()
is 3.5x (but still 3x slower than U128 with 128 bits).An example use case: in CGGMP21 scheme, the selected primes
p
,q
for the Paillier encryption must be big enough forp * q
to cover the range of squared secp256k1 scalars. This means thatbits(p * q) > 512
. Naturally, for testing purposes one would go with the minimum size, so 257-bit primes andU320
type.Theoretically, the bound can be used in the Lucas test as well, but it only operates with Montgomery multiplication. The performance dependance in
pow_bounded_exp()
is fine-grained enough for the position of the bound within one limb to matter (namely, the step is equal to the window size - 4 bits), but it is not the case for multiplication (whose performance changes with every added limb). If one knows that some limb is not going to be used it is probably easier to just use a differentUint
type. One can argue though that having a bound in Montgomery multiplication allows for using a single type (e.g.U2048
) for tests and production, only changing the size bound, without much loss of performance. That would greatly simplify the code. Adding bounds to the Lucas test would require support for bounded Montgomery operations incrypto_bigint
.