[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-discuss
Subject:    Extend Sliding Window Table
From:       EvaOrLew Baxter <lewandeva () hotmail ! com>
Date:       2021-04-26 11:38:31
Message-ID: MW3PR13MB39804E0ACBC477D643B438C9A8429 () MW3PR13MB3980 ! namprd13 ! prod ! outlook ! com
[Download RAW message or body]

I see that powlo.c and powm.c have tables used to choose the best k-ary sliding \
window for modular exponentiation. The table ends at 28161, so if the number of bits \
in the exponent is more than 28161 it always chooses k=10.

My application has exponents from about 74000 to 340000 bits and my (non-gmp) \
experiments show that k= 11 or k=12 is better than k=10. The improvement is minor \
(about 0.1% to 0.8%).

Is it safe for me to modify both powlo.c and powm.c to add entries into the table?

(I initially installed libgmp3-dev, but then built gmp and got a big improvement. One \
calculation of x^y mod z with 30000 digits takes 52 sec compared to 88 sec -- many \
thanks Torbjorn!)

If I modify the c files, do I now only need to 'make' and also 'make install'?

As for the best k, depending on bit size, is there some math used to optimize k, or \
did you do it experimentally?

Would you consider adding best k values in a future release of gmp?

Thanks
Lewis


_______________________________________________
gmp-discuss mailing list
gmp-discuss@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-discuss


[prev in list] [next in list] [prev in thread] [next in thread]