modinv64.h (2151B)
1 /*********************************************************************** 2 * Copyright (c) 2020 Peter Dettman * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 5 **********************************************************************/ 6 7 #ifndef SECP256K1_MODINV64_H 8 #define SECP256K1_MODINV64_H 9 10 #include "util.h" 11 12 #ifndef SECP256K1_WIDEMUL_INT128 13 #error "modinv64 requires 128-bit wide multiplication support" 14 #endif 15 16 /* A signed 62-bit limb representation of integers. 17 * 18 * Its value is sum(v[i] * 2^(62*i), i=0..4). */ 19 typedef struct { 20 int64_t v[5]; 21 } haskellsecp256k1_v0_1_0_modinv64_signed62; 22 23 typedef struct { 24 /* The modulus in signed62 notation, must be odd and in [3, 2^256]. */ 25 haskellsecp256k1_v0_1_0_modinv64_signed62 modulus; 26 27 /* modulus^{-1} mod 2^62 */ 28 uint64_t modulus_inv62; 29 } haskellsecp256k1_v0_1_0_modinv64_modinfo; 30 31 /* Replace x with its modular inverse mod modinfo->modulus. x must be in range [0, modulus). 32 * If x is zero, the result will be zero as well. If not, the inverse must exist (i.e., the gcd of 33 * x and modulus must be 1). These rules are automatically satisfied if the modulus is prime. 34 * 35 * On output, all of x's limbs will be in [0, 2^62). 36 */ 37 static void haskellsecp256k1_v0_1_0_modinv64_var(haskellsecp256k1_v0_1_0_modinv64_signed62 *x, const haskellsecp256k1_v0_1_0_modinv64_modinfo *modinfo); 38 39 /* Same as haskellsecp256k1_v0_1_0_modinv64_var, but constant time in x (not in the modulus). */ 40 static void haskellsecp256k1_v0_1_0_modinv64(haskellsecp256k1_v0_1_0_modinv64_signed62 *x, const haskellsecp256k1_v0_1_0_modinv64_modinfo *modinfo); 41 42 /* Compute the Jacobi symbol for (x | modinfo->modulus). x must be coprime with modulus (and thus 43 * cannot be 0, as modulus >= 3). All limbs of x must be non-negative. Returns 0 if the result 44 * cannot be computed. */ 45 static int haskellsecp256k1_v0_1_0_jacobi64_maybe_var(const haskellsecp256k1_v0_1_0_modinv64_signed62 *x, const haskellsecp256k1_v0_1_0_modinv64_modinfo *modinfo); 46 47 #endif /* SECP256K1_MODINV64_H */