Torbjorn Granlund <t...@gmplib.org> writes: > I quick guess is that the exponent is fixed for powm, not a function of > the input size.
Ah, its hardcoded to always use 6 limbs. If I change it to use the same size as b and m, results are a bit different: $ ./speed -s 1-64 -c -r mpn_gcdext mpn_sec_invert mpz_powm_sec overhead 5.43 cycles, precision 10000 units of 6.25e-10 secs, CPU freq 1600.00 MHz mpn_gcdext mpn_sec_invert mpz_powm_sec 1 #1393.53 9.2563 2.8281 2 #3700.83 8.4530 2.8537 3 #5628.82 9.2296 4.7198 4 #7387.08 9.8705 6.5449 5 #9270.67 12.2271 9.4494 6 #11102.89 13.2985 11.9077 7 #12923.54 14.2668 14.8305 8 #14985.50 14.9848 17.2423 9 #16826.96 17.1405 21.4808 10 #18998.00 17.9614 24.7252 11 #20390.00 19.6006 29.7402 12 #23244.21 19.9373 32.0728 13 #24235.58 22.4859 39.6380 14 #26027.70 23.5316 44.4109 15 #29157.89 23.7497 47.7260 16 #30368.62 26.6497 53.3113 17 #32534.43 28.4042 60.1591 18 #33580.67 29.1482 69.0387 19 #34424.60 31.2023 78.6099 20 #36470.00 32.4313 84.8543 21 #36405.25 35.8625 99.2162 22 #41335.25 33.8338 97.9815 23 #39861.67 38.2781 116.4425 24 #41421.67 39.4835 124.2736 25 #44087.67 41.0079 138.0154 26 #48386.33 39.9403 139.1569 27 #40868.00 50.5410 184.1573 So if you know that the modulo is prime (or has some other type of known factorization), using powm actually beats sec_invert for sizes up to 6 limbs. I still puzzled why the ratio between sec_invert and gcdext doesn't approach some constant (I'd expect the ratio to start growing again for sizes above the threshold for subquadratic gcdext). Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel