1pub mod prime;
  2pub mod barrett;
  3pub mod montgomery;
  4pub mod impl_u64;
  5
  6pub type REDUCEMOD = u8;
  7
  8pub const NONE: REDUCEMOD = 0;
  9pub const ONCE: REDUCEMOD = 1;
 10pub const TWICE: REDUCEMOD = 2;
 11pub const FOURTIMES: REDUCEMOD = 3;
 12pub const BARRETT: REDUCEMOD = 4;
 13pub const BARRETTLAZY: REDUCEMOD = 5;
 14
 15pub trait WordOps<O>{
 16    fn log2(self) -> O;
 17    fn reverse_bits_msb(self, n:u32) -> O;
 18    fn mask(self) -> O;
 19}
 20
 21impl WordOps<u64> for u64{
 22    #[inline(always)]
 23    fn log2(self) -> u64{
 24        (u64::BITS - (self-1).leading_zeros()) as _
 25    }
 26    #[inline(always)]
 27    fn reverse_bits_msb(self, n: u32) -> u64{
 28        self.reverse_bits() >> (usize::BITS - n)
 29    }
 30    #[inline(always)]
 31    fn mask(self) -> u64{
 32        (1<<self.log2())-1
 33    }
 34}
 35
 36impl WordOps<usize> for usize{
 37    #[inline(always)]
 38    fn log2(self) -> usize{
 39        (usize::BITS - (self-1).leading_zeros()) as _
 40    }
 41    #[inline(always)]
 42    fn reverse_bits_msb(self, n: u32) -> usize{
 43        self.reverse_bits() >> (usize::BITS - n)
 44    }
 45    #[inline(always)]
 46    fn mask(self) -> usize{
 47        (1<<self.log2())-1
 48    }
 49}
 50
 51pub trait ReduceOnce<O>{
 52    /// Assigns self-q to self if self >= q in constant time.
 53    /// User must ensure that 2q fits in O.
 54    fn reduce_once_constant_time_assign(&mut self, q: O);
 55    /// Returns self-q if self >= q else self in constant time.
 56    /// /// User must ensure that 2q fits in O.
 57    fn reduce_once_constant_time(&self, q:O) -> O;
 58    /// Assigns self-q to self if self >= q.
 59    /// /// User must ensure that 2q fits in O.
 60    fn reduce_once_assign(&mut self, q: O);
 61    /// Returns self-q if self >= q else self.
 62    /// /// User must ensure that 2q fits in O.
 63    fn reduce_once(&self, q:O) -> O;
 64}
 65
 66pub trait ScalarOperations<O>{
 67
 68    // Applies a parameterized modular reduction.
 69    fn sa_reduce_into_sa<const REDUCE:REDUCEMOD>(&self, x: &mut O);
 70
 71    // Assigns a + b to c.
 72    fn sa_add_sb_into_sc<const REDUCE:REDUCEMOD>(&self, a: &O, b:&O, c: &mut O);
 73
 74    // Assigns a + b to b.
 75    fn sa_add_sb_into_sb<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut O);
 76
 77    // Assigns a - b to c.
 78    fn sa_sub_sb_into_sc<const REDUCE:REDUCEMOD>(&self, a: &O, b:&O, c: &mut O);
 79
 80    // Assigns b - a to b.
 81    fn sa_sub_sb_into_sb<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut O);
 82
 83    // Assigns -a to a.
 84    fn sa_neg_into_sa<const REDUCE:REDUCEMOD>(&self, a:&mut O);
 85
 86    // Assigns -a to b.
 87    fn sa_neg_into_sb<const REDUCE:REDUCEMOD>(&self, a: &O, b:&mut O);
 88
 89    // Assigns a * 2^64 to b.
 90    fn sa_prep_mont_into_sb<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut montgomery::Montgomery<O>);
 91
 92    // Assigns a * b to c.
 93    fn sa_mont_mul_sb_into_sc<const REDUCE:REDUCEMOD>(&self, a:&montgomery::Montgomery<O>, b:&O, c: &mut O);
 94
 95    // Assigns a * b to b.
 96    fn sa_mont_mul_sb_into_sb<const REDUCE:REDUCEMOD>(&self, a:&montgomery::Montgomery<O>, b:&mut O);
 97
 98    // Assigns a * b to c.
 99    fn sa_barrett_mul_sb_into_sc<const REDUCE:REDUCEMOD>(&self, a: &barrett::Barrett<O>, b:&O, c: &mut O);
100
101    // Assigns a * b to b.
102    fn sa_barrett_mul_sb_into_sb<const REDUCE:REDUCEMOD>(&self, a:&barrett::Barrett<O>, b:&mut O);
103
104    // Assigns (a + 2q - b) * c to d.
105    fn sa_sub_sb_mul_sc_into_sd<const REDUCE:REDUCEMOD>(&self, a: &O, b: &O, c: &barrett::Barrett<O>, d: &mut O);
106
107    // Assigns (a + 2q - b) * c to b.
108    fn sa_sub_sb_mul_sc_into_sb<const REDUCE:REDUCEMOD>(&self, a: &u64, c: &barrett::Barrett<u64>, b: &mut u64);
109}
110
111pub trait VectorOperations<O>{
112
113    // Applies a parameterized modular reduction.
114    fn va_reduce_into_va<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, x: &mut [O]);
115
116    // ADD
117    // Assigns a[i] + b[i] to c[i]
118    fn va_add_vb_into_vc<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b:&[O], c: &mut [O]);
119
120    // Assigns a[i] + b[i] to b[i]
121    fn va_add_vb_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
122
123    // Assigns a[i] + b to c[i]
124    fn va_add_sb_into_vc<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b:&O, c:&mut [O]);
125
126    // Assigns b[i] + a to b[i]
127    fn sa_add_vb_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a:&O, b:&mut [O]);
128
129    // SUB
130    // Assigns a[i] - b[i] to b[i]
131    fn va_sub_vb_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
132
133    // Assigns a[i] - b[i] to c[i]
134    fn va_sub_vb_into_vc<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b:&[O], c: &mut [O]);
135
136    // NEG
137    // Assigns -a[i] to a[i].
138    fn va_neg_into_va<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &mut [O]);
139
140    // Assigns -a[i] to a[i].
141    fn va_neg_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
142
143    // MUL MONTGOMERY
144    // Assigns a * 2^64 to b.
145    fn va_prep_mont_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [montgomery::Montgomery<O>]);
146
147    // Assigns a[i] * b[i] to c[i].
148    fn va_mont_mul_vb_into_vc<const CHUNK:usize,const REDUCE:REDUCEMOD>(&self, a:&[montgomery::Montgomery<O>], b:&[O], c: &mut [O]);
149
150    // Assigns a[i] * b[i] to b[i].
151    fn va_mont_mul_vb_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a:&[montgomery::Montgomery<O>], b:&mut [O]);
152
153    // MUL BARRETT
154    // Assigns a * b[i] to b[i].
155    fn sa_barrett_mul_vb_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a:& barrett::Barrett<u64>, b:&mut [u64]);
156
157    // Assigns a * b[i] to c[i].
158    fn sa_barrett_mul_vb_into_vc<const CHUNK:usize,const REDUCE:REDUCEMOD>(&self, a:& barrett::Barrett<u64>, b:&[u64], c: &mut [u64]);
159
160    // OTHERS
161    // Assigns (a[i] + 2q - b[i]) * c to d[i].
162    fn va_sub_vb_mul_sc_into_vd<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[u64], b: &[u64], c: &barrett::Barrett<u64>, d: &mut [u64]);
163
164    // Assigns (a[i] + 2q - b[i]) * c to b[i].
165    fn va_sub_vb_mul_sc_into_vb<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[u64], c: &barrett::Barrett<u64>, b: &mut [u64]);
166}
167
168
169
170