Seth Troisi <brain...@gmail.com> writes: > Yes I've tried that too. It was the same exact speed, so I started to > profile the function, which hasn't been easy. > I think the vast majority (98%+) of the function is spent in calls to > mpz_rabinmiller.
Good to have some profile numbers! Then microoptimizations elsewhere will not make any significant difference. 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. Or speed up detection of composites in mpz_millerrabin, unclear how. 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 if there's something clever I'm missing, it could be used to speed up mpz_millerrabin. And I'm not sure how well we currently do small-base modexp in gmp. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
