_basecase or _sec? [
nisse at lysator.liu.se
Sun Mar 3 21:13:48 CET 2013
bodrato at mail.dm.unipi.it writes:
> Uhm... Why are all this _basecase functions needed? To have them running
> in predictable time (only dependent on sizes, not on actual operands)?
For mul and sqr: yes, and also to avoid memory allocation.
For gcdext: No, there the point is to have O(n) storage independent on
values of various thresholds. It's *not* going to have data independent
timing. (Now, I guess this isn't as true as I'd like it to be with the
current code; current mpn_gcdext_lehmer_n will call the general mpn_mul
and mpn_tdiv functions for unlikely inputs, which may allocate memory.
Maybe it shouldn't).
And also, to reduce overhead and code size for applications that use
only numbers of moderate size. Say I do ecc operations on some embedded
device with little memory, and all the bignums are less than about 1000
bits, then there's no need to even link in the toom routines.
> If this is the reason, let's call them _sec.
Naming is difficult. But _sec is not appropriate for all basecase
functions. I think the idea of the currrent _sec suffix is to use it
only on functions that do *additional* work in order to get data
independent timing and memory access pattern, like powm_sec and the
recent div_sec routines.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel