Re: Faster table compute in mpn_sec_powm

"Marco Bodrato" writes: I unified definitions... Correctly, I hope! LGTM, thanks! -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel

Re: Faster table compute in mpn_sec_powm

Ciao, Il Lun, 26 Marzo 2018 11:21 am, Torbjörn Granlund ha scritto: > I assume SQR_BASECASE_THRESHOLD should be checked for both definitions > of mpn_local_sqr. I unified definitions... Correctly, I hope! https://gmplib.org/repo/gmp/rev/c5c1f6d537f4 Ĝis, m -- http://bodrato.it/papers/

Re: Faster table compute in mpn_sec_powm

*** *** 116,128 size. */ #define mpn_local_sqr(rp,up,n,tp) mpn_sqr_basecase(rp,up,n) #else /* Else use mpn_sqr_basecase for its allowed sizes, else mpn_mul_basecase. */ #define mpn_local_sqr(rp,up,n,tp) \ do {

Re: Faster table compute in mpn_sec_powm

"Marco Bodrato" writes: May I suggest: [snip] Right. That was not introduced now, but an old inefficiency. :-( -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org

Re: Faster table compute in mpn_sec_powm

Ciao, Il Sab, 24 Marzo 2018 3:37 pm, Torbjörn Granlund ha scritto: > B^(2j) = (B^j)^2 (i.e., even values of i) > B^(2j+1) = (B^(2j))*B (i.e., odd values of i) > I haven't benchmarked this change, but it is clearly never a slowdown. maybe a slowdown on the few systems with a

Re: Faster table compute in mpn_sec_powm

B^(2j) = (B^j)^2 (i.e., even values of i) B^(2j+1) = (B^(2j))*B (i.e., odd values of i) I pushed a set of changes implementing this: https://gmplib.org/repo/gmp/raw-rev/186ea964d61f https://gmplib.org/repo/gmp/raw-rev/a6967ea18b2f https://gmplib.org/repo/gmp/raw-rev/289ab13bc3fe

Re: Faster table compute in mpn_sec_powm

= (B^j)^2 (i.e., even values of i) B^(2j+1) = (B^(2j))*B (i.e., odd values of i) as that implies the algorithm. (For mpn_sec_powm, it will translate to doing one mpn_sqr_basecase call for even indices, one mpn_mul_basecase for odd.) (I forgot to reply to the list the first time.) If

Re: Faster table compute in mpn_sec_powm

Bradley Lucier writes: If you're filling the entire table, I don't see how this would be faster. (E.g., if B=10 and you're calculating the entries of a table from 1 to 10,000.) Squaring is much faster than general multiplication. But of one is to compute a table

Re: Faster table compute in mpn_sec_powm

t...@gmplib.org (Torbjörn Granlund) writes: > In the side-channel silent GMP mpn_sec_powm we compute a table of powers > of the base B, from B^0 to B^k-1 for some table size k. [...] > I.e., for even powers we do a squaring, while for odd numbers we do like > before. That's a nice

Re: Faster table compute in mpn_sec_powm

On Tue, Mar 20, 2018 at 04:13:54PM +0100, Paul Zimmermann wrote: >Torbjörn, > > > B^(2j) = (B^j)^2 (i.e., even values of i) > > B^(2j+1) = (B^(2j))*B (i.e., odd values of i) > > this is a classical trick we use at several places in MPFR, and we mention > in Modern Computer

Re: Faster table compute in mpn_sec_powm

paul zimmermann writes: this is a classical trick we use at several places in MPFR, and we mention in Modern Computer Algebra (page 142). Does someone has an earlier reference for that trick? Only a later; I invented it today at 14:00 UTC. :-D -- Torbjörn

Re: Faster table compute in mpn_sec_powm

For odd values of i Instead of this B^(2j+1) = (B^(j-1))*B Shouldn't be this? B^(2j+1) = (B^j)^2*B Fran. El mar, 20/3/18, Torbjörn Granlund <t...@gmplib.org> escribió: Asunto: Faster table compute in mpn_sec_powm Para: gmp-devel@gmpl

Faster table compute in mpn_sec_powm

In the side-channel silent GMP mpn_sec_powm we compute a table of powers of the base B, from B^0 to B^k-1 for some table size k. We do this simple by using the recusrion B^k = B^k*B. I now realised this can be sped up very easily: B^(2j) = (B^j)^2 (i.e., even values of i) B^(2j+1) = (B

Re: mpn_sec_powm

ni...@lysator.liu.se (Niels Möller) writes: Given the current implementation, it's natural. But we could document that it is required that any left over bits in the top limb must be zero. Would that be better? My take on this is that asking users to keep that zero isn't a requirement

Re: mpn_sec_powm

Torbjorn Granlund t...@gmplib.org writes: The exponent size argument docs implies that bits in the leading limb beyond the bit count argument are to be ignored. I am not sure that is a wise promise. Given the current implementation, it's natural. But we could document that it is required

Re: mpn_sec_powm

Torbjorn Granlund t...@gmplib.org writes: Please use something else than ebits, since that sounds like the arguments contains bits with individual meaning. IIRC enb would follow conventions used elsewhere in the manual. Naming is hard ;-) The docs for mpn_sec_invert use nbcnt (I guess that's

Re: mpn_sec_powm

ni...@lysator.liu.se (Niels Möller) writes: Maybe one problem is that to make a fair comparison between window sizes k and k+1, the exponent bit size should be divisible by both k and k+1. I'm testing the below patch. Output from four consecutive runs: #define POWM_SEC_TABLE

Re: mpn_sec_powm

ni...@lysator.liu.se (Niels Möller) writes: Torbjorn Granlund t...@gmplib.org writes: Please use something else than ebits, since that sounds like the arguments contains bits with individual meaning. IIRC enb would follow conventions used elsewhere in the manual. Naming is

Re: mpn_sec_powm

ni...@lysator.liu.se (Niels Möller) writes: After some discussion with Torbjörn, I intend to change mpn_sec_powm to take the exponent size argument in bits, rather than limbs (because the current code may leak high bit of the exponent, which can cause serious problems for some applications

mpn_sec_powm

After some discussion with Torbjörn, I intend to change mpn_sec_powm to take the exponent size argument in bits, rather than limbs (because the current code may leak high bit of the exponent, which can cause serious problems for some applications, e.g., dsa signatures). But first, I'd like to fix