From a34fccb435d68391089a8564b31cbdf7e9efd2d7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Niels=20M=C3=B6ller?= Date: Mon, 19 Oct 2020 19:55:40 +0200 Subject: [PATCH] Comment fixes for ecc_secp192r1_inv. --- ecc-secp192r1.c | 40 +++++++++++++++++++++++++++++----------- 1 file changed, 29 insertions(+), 11 deletions(-) diff --git a/ecc-secp192r1.c b/ecc-secp192r1.c index 14eb4ff1..ec6b2bb4 100644 --- a/ecc-secp192r1.c +++ b/ecc-secp192r1.c @@ -112,9 +112,10 @@ ecc_secp192r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp) #define ECC_SECP192R1_INV_ITCH (4*ECC_LIMB_SIZE) -static void ecc_secp192r1_inv (const struct ecc_modulo *p, - mp_limb_t *rp, const mp_limb_t *ap, - mp_limb_t *scratch) +static void +ecc_secp192r1_inv (const struct ecc_modulo *p, + mp_limb_t *rp, const mp_limb_t *ap, + mp_limb_t *scratch) { #define t0 scratch #define t1 (scratch + 2*ECC_LIMB_SIZE) @@ -130,7 +131,7 @@ static void ecc_secp192r1_inv (const struct ecc_modulo *p, /* Addition chain p - 2 = 2^{192} - 2^{64} - 3 - = 1 + 2^{192} - 2^{64} - 4 + = 1 + 2^{192} - 2^{64} - 4 = 1 + 2^2 (2^{190} - 2^{62} - 1) = 1 + 2^2 (2^{62} - 1 + 2^{190} - 2^63) = 1 + 2^2 (2^{62} - 1 + 2^{63}(2^{127} - 1)) @@ -139,13 +140,30 @@ static void ecc_secp192r1_inv (const struct ecc_modulo *p, = 1 + 2^2 (2^{62} - 1 + 2^{63}(1 + 2 (2^{63} + 1)(1 + 2(2^{62} - 1)))) 2^{62} - 1 = (2^{31}+1)(2^{31}-1) - = (2^{31}+1)(1 + 2(1 + 2^{30} - 1)) - = (2^{31}+1)(1 + 2(1 + (2^{15}+1)(2^15-1)) - = (2^{31}+1)(1 + 2(1 + (2^{15}+1)(1 + 2(1 + (2^{14}-1))) - = (2^{31}+1)(1 + 2(1 + (2^{15}+1)(1 + 2(1 + (2^7+1)(2^7-1)))) - = (2^{31}+1)(1 + 2(1 + (2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(2^3-1))))) - = (2^{31}+1)(1 + 2(1 + (2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(1 + 2 (2+1)))))) - + = (2^{31}+1)(1 + 2(2^{30} - 1)) + = (2^{31}+1)(1 + 2(2^{15}+1)(2^15-1)) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^{14}-1)))) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(2^7-1)))) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(2^3-1))))) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(1 + 2 (2+1)))))) + + This addition chain needs 191 squarings and 14 multiplies. + + Could be improved sligthly as: + + a^7 = 1 + 2 * (2 + 1) + 2^{62} - 1 = (2^{31}+1)(2^{31}-1) + = (2^{31}+1)(1 + 2(2^{30} - 1)) + = (2^{31}+1)(1 + 2(2^{15}+1)(2^15-1)) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^{14}-1)))) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(2^7-1)))) + = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(2^3-1))))) + 2^{65} - 1 = 2^3 (2^{62} - 1) + 2^3 - 1 + 2^{127} - 1 = 2^{62} (2^{65} - 1) + 2^{62} - 1 + p - 2 = 1 + 2^2 (2^{62} - 1 + 2^{63}(2^{127} - 1)) + + This needs 191 squarings and 13 multiplies, i.e., saving one + multiply, at the cost of additional temporary storage for a^7. */ ecc_mod_sqr (p, rp, ap); /* a^2 */ -- 2.47.2