Torbjörn Granlund <t...@gmplib.org> writes: > That count is a proven "upper bound" of the numbver of iterations. Does > the paper discuss how tight it is, i.e., is it close to a "lower bound" > of the required number of iterations.
As an upper bound, I think it's rather tight at least for smallish sizes, since proof includes an exhastive search up to some small limit on bit size, and the results from that guide the approach for the general proof. (It's rather complex, I don't get all the details). Much more unclear to me how close it might be to the typical or average number of iterations needed. > Comparing to the existing side-channel-silent inversion code would > impress more, I think. That would be a very relevant benchmark, yes. Omitted in this version just because interface is a bit different from what's used in the prototype. > What percentage of Ec scalar mul is used for the final inversion? Not > much, I suppose. After a quick look at my benchmark numbers, if one compares the time for A. inversion modulo the field prime, and B. scalar multiplication using the fixed generator point, and with output in projective or jacobian coordinates (i.e., inverse free), then ratio A/B is in the range 10% (smaller curves) to 16% for ed448. > Does Nettle use exponentiation there today, or > mpn_sec_invert? Currently uses exponentiation for the field inverse, and nettle's version of sec_invert for inverses mod the group order, as needed by ecdsa. Except for the somewhat obscure gost curves (Russian standards), where sec_invert is used for all inverses, and A/B for gost-gc512a is almost 30%. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
