Ciao, Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto: > Seth Troisi <brain...@gmail.com> writes:
>> I think the vast majority (98%+) of the function is spent in calls to >> mpz_rabinmiller. > To get better speed, we'd need to either increase the size of the prime > table used for sieving considerably, say by a factor of 2, 5 or 10. Spending more time in sieving and reducing the number of calls surely is a good idea. > I think I've seen comments in the literature saying that 2^e mod m is > "obviously" more efficient than general modular exponentiation. But as > far as I can tell, b^e mod m with small b needs essentially one modular > squaring per bit in the exponent, including the special case b = 2. But One modular squaring and some products ... > And I'm not sure how well we currently do small-base modexp in gmp. We basically do not do anything special. So that small-base or large-base will take the same time. With the special case b=2 one may save a few operation seeding the process with a 2-power smaller than the modulus, but this is a little saving. Moreover one may avoid the windowing on the exponent (we currently pre-compute b^3, b^5, b^7... so that we need fewer products) and use a shift by a single bit every time a multiplication times the base is needed. Since we use a REDC-representation, implementing this is not completely obvious, but anyway it shoul not be too difficult. This means writing a special function for b=2, not for more general small bases. Currently I do not have the time to, anyone? Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
