modinv32.h (2047B)
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_MODINV32_H 8 #define SECP256K1_MODINV32_H 9 10 #include "util.h" 11 12 /* A signed 30-bit limb representation of integers. 13 * 14 * Its value is sum(v[i] * 2^(30*i), i=0..8). */ 15 typedef struct { 16 int32_t v[9]; 17 } haskellsecp256k1_v0_1_0_modinv32_signed30; 18 19 typedef struct { 20 /* The modulus in signed30 notation, must be odd and in [3, 2^256]. */ 21 haskellsecp256k1_v0_1_0_modinv32_signed30 modulus; 22 23 /* modulus^{-1} mod 2^30 */ 24 uint32_t modulus_inv30; 25 } haskellsecp256k1_v0_1_0_modinv32_modinfo; 26 27 /* Replace x with its modular inverse mod modinfo->modulus. x must be in range [0, modulus). 28 * If x is zero, the result will be zero as well. If not, the inverse must exist (i.e., the gcd of 29 * x and modulus must be 1). These rules are automatically satisfied if the modulus is prime. 30 * 31 * On output, all of x's limbs will be in [0, 2^30). 32 */ 33 static void haskellsecp256k1_v0_1_0_modinv32_var(haskellsecp256k1_v0_1_0_modinv32_signed30 *x, const haskellsecp256k1_v0_1_0_modinv32_modinfo *modinfo); 34 35 /* Same as haskellsecp256k1_v0_1_0_modinv32_var, but constant time in x (not in the modulus). */ 36 static void haskellsecp256k1_v0_1_0_modinv32(haskellsecp256k1_v0_1_0_modinv32_signed30 *x, const haskellsecp256k1_v0_1_0_modinv32_modinfo *modinfo); 37 38 /* Compute the Jacobi symbol for (x | modinfo->modulus). x must be coprime with modulus (and thus 39 * cannot be 0, as modulus >= 3). All limbs of x must be non-negative. Returns 0 if the result 40 * cannot be computed. */ 41 static int haskellsecp256k1_v0_1_0_jacobi32_maybe_var(const haskellsecp256k1_v0_1_0_modinv32_signed30 *x, const haskellsecp256k1_v0_1_0_modinv32_modinfo *modinfo); 42 43 #endif /* SECP256K1_MODINV32_H */