Add extensive comments on the safegcd algorithm and implementation

[secp256k1.git] / src / modinv64.h

diff --git a/src/modinv64.h b/src/modinv64.h
index e70fea0d60336236b75bc860889eff244ae4e1c9..da506dfa9f722e2bc697209a7aeaf2ec574318b9 100644 (file)
--- a/src/modinv64.h
+++ b/src/modinv64.h
@@ -17,19 +17,30 @@
 #error "modinv64 requires 128-bit wide multiplication support"
 #endif
 
+/* A signed 62-bit limb representation of integers.
+ *
+ * Its value is sum(v[i] * 2^(62*i), i=0..4). */
 typedef struct {
     int64_t v[5];
 } secp256k1_modinv64_signed62;
 
 typedef struct {
-    /* The modulus in signed62 notation. */
+    /* The modulus in signed62 notation, must be odd and in [3, 2^256]. */
     secp256k1_modinv64_signed62 modulus;
 
     /* modulus^{-1} mod 2^62 */
     uint64_t modulus_inv62;
 } secp256k1_modinv64_modinfo;
 
-static void secp256k1_modinv64(secp256k1_modinv64_signed62 *x, const secp256k1_modinv64_modinfo *modinfo);
+/* Replace x with its modular inverse mod modinfo->modulus. x must be in range [0, modulus).
+ * If x is zero, the result will be zero as well. If not, the inverse must exist (i.e., the gcd of
+ * x and modulus must be 1). These rules are automatically satisfied if the modulus is prime.
+ *
+ * On output, all of x's limbs will be in [0, 2^62).
+ */
 static void secp256k1_modinv64_var(secp256k1_modinv64_signed62 *x, const secp256k1_modinv64_modinfo *modinfo);
 
+/* Same as secp256k1_modinv64_var, but constant time in x (not in the modulus). */
+static void secp256k1_modinv64(secp256k1_modinv64_signed62 *x, const secp256k1_modinv64_modinfo *modinfo);
+
 #endif /* SECP256K1_MODINV64_H */