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  } secp256k1_modinv32_signed30;
18  
19  typedef struct {
20      /* The modulus in signed30 notation, must be odd and in [3, 2^256]. */
21      secp256k1_modinv32_signed30 modulus;
22  
23      /* modulus^{-1} mod 2^30 */
24      uint32_t modulus_inv30;
25  } secp256k1_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 secp256k1_modinv32_var(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo);
34  
35  /* Same as secp256k1_modinv32_var, but constant time in x (not in the modulus). */
36  static void secp256k1_modinv32(secp256k1_modinv32_signed30 *x, const secp256k1_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 secp256k1_jacobi32_maybe_var(const secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo);
42  
43  #endif /* SECP256K1_MODINV32_H */