_basecase or _sec? [

Niels Möller 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 mailing list