1//! Bls12-377 scalar field.
  2///
  3/// Roots of unity computed from modulus and R using this sage code:
  4///
  5/// ```ignore
  6/// q = 8444461749428370424248824938781546531375899335154063827935233455917409239041
  7/// R = 6014086494747379908336260804527802945383293308637734276299549080986809532403 # Montgomery R
  8/// s = 47
  9/// o = q - 1
 10/// F = GF(q)
 11/// g = F.multiplicative_generator()
 12/// g = F.multiplicative_generator()
 13/// assert g.multiplicative_order() == o
 14/// g2 = g ** (o/2**s)
 15/// assert g2.multiplicative_order() == 2**s
 16/// def into_chunks(val, width, n):
 17///     return [int(int(val) // (2 ** (width * i)) % 2 ** width) for i in range(n)]
 18/// print("Gen: ", g * R % q)
 19/// print("Gen: ", into_chunks(g * R % q, 64, 4))
 20/// print("2-adic gen: ", into_chunks(g2 * R % q, 64, 4))
 21/// ```
 22use ark_ff::{
 23    biginteger::{BigInt, BigInteger256 as BigInteger},
 24    fields::*,
 25};
 26pub type Fr = Fp256<FrParameters>;
 27
 28pub struct FrParameters;
 29
 30impl Fp256Parameters for FrParameters {}
 31impl FftParameters for FrParameters {
 32    type BigInt = BigInteger;
 33
 34    const TWO_ADICITY: u32 = 47;
 35
 36    #[rustfmt::skip]
 37    const TWO_ADIC_ROOT_OF_UNITY: BigInteger = BigInt::new([
 38        12646347781564978760u64,
 39        6783048705277173164u64,
 40        268534165941069093u64,
 41        1121515446318641358u64,
 42    ]);
 43}
 44impl FpParameters for FrParameters {
 45    /// MODULUS = 8444461749428370424248824938781546531375899335154063827935233455917409239041
 46    #[rustfmt::skip]
 47    const MODULUS: BigInteger = BigInt::new([
 48        725501752471715841u64,
 49        6461107452199829505u64,
 50        6968279316240510977u64,
 51        1345280370688173398u64,
 52    ]);
 53
 54    const MODULUS_BITS: u32 = 253;
 55
 56    const CAPACITY: u32 = Self::MODULUS_BITS - 1;
 57
 58    const REPR_SHAVE_BITS: u32 = 3;
 59
 60    /// R = 6014086494747379908336260804527802945383293308637734276299549080986809532403
 61    #[rustfmt::skip]
 62    const R: BigInteger = BigInt::new([
 63        9015221291577245683u64,
 64        8239323489949974514u64,
 65        1646089257421115374u64,
 66        958099254763297437u64,
 67    ]);
 68
 69    #[rustfmt::skip]
 70    const R2: BigInteger = BigInt::new([
 71        2726216793283724667u64,
 72        14712177743343147295u64,
 73        12091039717619697043u64,
 74        81024008013859129u64,
 75    ]);
 76
 77    const INV: u64 = 725501752471715839u64;
 78
 79    /// GENERATOR = 22
 80    /// Encoded in Montgomery form, so the value is
 81    /// (22 * R) % q =
 82    /// 5642976643016801619665363617888466827793962762719196659561577942948671127251
 83    #[rustfmt::skip]
 84    const GENERATOR: BigInteger = BigInt::new([
 85        2984901390528151251u64,
 86        10561528701063790279u64,
 87        5476750214495080041u64,
 88        898978044469942640u64,
 89    ]);
 90
 91    /// (r - 1)/2 =
 92    /// 4222230874714185212124412469390773265687949667577031913967616727958704619520
 93    #[rustfmt::skip]
 94    const MODULUS_MINUS_ONE_DIV_TWO: BigInteger = BigInt::new([
 95        0x8508c00000000000,
 96        0xacd53b7f68000000,
 97        0x305a268f2e1bd800,
 98        0x955b2af4d1652ab,
 99    ]);
100
101    // T and T_MINUS_ONE_DIV_TWO, where r - 1 = 2^s * t
102    // For T coprime to 2
103
104    /// t = (r - 1) / 2^s =
105    /// 60001509534603559531609739528203892656505753216962260608619555
106    #[rustfmt::skip]
107    const T: BigInteger = BigInt::new([
108        0xedfda00000021423,
109        0x9a3cb86f6002b354,
110        0xcabd34594aacc168,
111        0x2556,
112    ]);
113
114    /// (t - 1) / 2 =
115    /// 30000754767301779765804869764101946328252876608481130304309777
116    #[rustfmt::skip]
117    const T_MINUS_ONE_DIV_TWO: BigInteger = BigInt::new([
118        0x76fed00000010a11,
119        0x4d1e5c37b00159aa,
120        0x655e9a2ca55660b4,
121        0x12ab,
122    ]);
123}