poulpy/math/src/ring/impl_u64/ring.rs
math/src/ring/impl_u64/ring.rsRaw
1use crate::ring::Ring;
2use crate::dft::ntt::Table;
3use crate::modulus::prime::Prime;
4use crate::modulus::montgomery::Montgomery;
5use crate::modulus::barrett::Barrett;
6use crate::poly::Poly;
7use crate::modulus::{REDUCEMOD, BARRETT};
8use crate::modulus::VectorOperations;
9use num_bigint::BigInt;
10use num_traits::ToPrimitive;
11use crate::CHUNK;
12
13impl Ring<u64>{
14 pub fn new(n:usize, q_base:u64, q_power:usize) -> Self{
15 let prime: Prime<u64> = Prime::<u64>::new(q_base, q_power);
16 Self {
17 n: n,
18 modulus: prime.clone(),
19 dft: Box::new(Table::<u64>::new(prime, (2 * n) as u64)),
20 }
21 }
22
23 pub fn from_bigint(&self, coeffs: &[BigInt], step:usize, a: &mut Poly<u64>){
24 assert!(step <= a.n(), "invalid step: step={} > a.n()={}", step, a.n());
25 assert!(coeffs.len() <= a.n() / step, "invalid coeffs: coeffs.len()={} > a.n()/step={}", coeffs.len(), a.n()/step);
26 let q_big: BigInt = BigInt::from(self.modulus.q);
27 a.0.iter_mut().step_by(step).enumerate().for_each(|(i, v)| *v = (&coeffs[i] % &q_big).to_u64().unwrap());
28 }
29}
30
31impl Ring<u64>{
32 pub fn ntt_inplace<const LAZY:bool>(&self, poly: &mut Poly<u64>){
33 match LAZY{
34 true => self.dft.forward_inplace_lazy(&mut poly.0),
35 false => self.dft.forward_inplace(&mut poly.0)
36 }
37 }
38
39 pub fn intt_inplace<const LAZY:bool>(&self, poly: &mut Poly<u64>){
40 match LAZY{
41 true => self.dft.backward_inplace_lazy(&mut poly.0),
42 false => self.dft.backward_inplace(&mut poly.0)
43 }
44 }
45
46 pub fn ntt<const LAZY:bool>(&self, poly_in: &Poly<u64>, poly_out: &mut Poly<u64>){
47 poly_out.0.copy_from_slice(&poly_in.0);
48 match LAZY{
49 true => self.dft.forward_inplace_lazy(&mut poly_out.0),
50 false => self.dft.forward_inplace(&mut poly_out.0)
51 }
52 }
53
54 pub fn intt<const LAZY:bool>(&self, poly_in: &Poly<u64>, poly_out: &mut Poly<u64>){
55 poly_out.0.copy_from_slice(&poly_in.0);
56 match LAZY{
57 true => self.dft.backward_inplace_lazy(&mut poly_out.0),
58 false => self.dft.backward_inplace(&mut poly_out.0)
59 }
60 }
61}
62
63impl Ring<u64>{
64
65 #[inline(always)]
66 pub fn add_inplace<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>){
67 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
68 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
69 self.modulus.va_add_vb_into_vb::<CHUNK, REDUCE>(&a.0, &mut b.0);
70 }
71
72 #[inline(always)]
73 pub fn add<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &Poly<u64>, c: &mut Poly<u64>){
74 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
75 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
76 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
77 self.modulus.va_add_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
78 }
79
80 #[inline(always)]
81 pub fn add_scalar_inplace<const REDUCE: REDUCEMOD>(&self, a: &u64, b: &mut Poly<u64>){
82 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
83 self.modulus.sa_add_vb_into_vb::<CHUNK, REDUCE>(a, &mut b.0);
84 }
85
86 #[inline(always)]
87 pub fn add_scalar<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &u64, c: &mut Poly<u64>){
88 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
89 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
90 self.modulus.va_add_sb_into_vc::<CHUNK, REDUCE>(&a.0, b, &mut c.0);
91 }
92
93 #[inline(always)]
94 pub fn sub_inplace<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>){
95 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
96 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
97 self.modulus.va_sub_vb_into_vb::<CHUNK, REDUCE>(&a.0, &mut b.0);
98 }
99
100 #[inline(always)]
101 pub fn sub<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &Poly<u64>, c: &mut Poly<u64>){
102 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
103 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
104 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
105 self.modulus.va_sub_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
106 }
107
108 #[inline(always)]
109 pub fn neg<const REDUCE: REDUCEMOD>(&self, a: &Poly<u64>, b: &mut Poly<u64>){
110 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
111 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
112 self.modulus.va_neg_into_vb::<CHUNK, REDUCE>(&a.0, &mut b.0);
113 }
114
115 #[inline(always)]
116 pub fn neg_inplace<const REDUCE: REDUCEMOD>(&self, a: &mut Poly<u64>){
117 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
118 self.modulus.va_neg_into_va::<CHUNK, REDUCE>(&mut a.0);
119 }
120
121 #[inline(always)]
122 pub fn mul_montgomery_external<const REDUCE:REDUCEMOD>(&self, a:&Poly<Montgomery<u64>>, b:&Poly<u64>, c: &mut Poly<u64>){
123 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
124 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
125 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
126 self.modulus.va_mont_mul_vb_into_vc::<CHUNK, REDUCE>(&a.0, &b.0, &mut c.0);
127 }
128
129 #[inline(always)]
130 pub fn mul_montgomery_external_inplace<const REDUCE:REDUCEMOD>(&self, a:&Poly<Montgomery<u64>>, b:&mut Poly<u64>){
131 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
132 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
133 self.modulus.va_mont_mul_vb_into_vb::<CHUNK, REDUCE>(&a.0, &mut b.0);
134 }
135
136 #[inline(always)]
137 pub fn mul_scalar<const REDUCE:REDUCEMOD>(&self, a:&Poly<u64>, b: &u64, c:&mut Poly<u64>){
138 debug_assert!(a.n() == self.n(), "b.n()={} != n={}", a.n(), self.n());
139 debug_assert!(c.n() == self.n(), "c.n()={} != n={}", c.n(), self.n());
140 self.modulus.sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(&self.modulus.barrett.prepare(*b), &a.0, &mut c.0);
141 }
142
143 #[inline(always)]
144 pub fn mul_scalar_inplace<const REDUCE:REDUCEMOD>(&self, a:&u64, b:&mut Poly<u64>){
145 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
146 self.modulus.sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(&self.modulus.barrett.prepare(self.modulus.barrett.reduce::<BARRETT>(a)), &mut b.0);
147 }
148
149 #[inline(always)]
150 pub fn mul_scalar_barrett_inplace<const REDUCE:REDUCEMOD>(&self, a:&Barrett<u64>, b:&mut Poly<u64>){
151 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
152 self.modulus.sa_barrett_mul_vb_into_vb::<CHUNK, REDUCE>(a, &mut b.0);
153 }
154
155 #[inline(always)]
156 pub fn mul_scalar_barrett<const REDUCE:REDUCEMOD>(&self, a:&Barrett<u64>, b: &Poly<u64>, c:&mut Poly<u64>){
157 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
158 self.modulus.sa_barrett_mul_vb_into_vc::<CHUNK, REDUCE>(a, &b.0, &mut c.0);
159 }
160
161 #[inline(always)]
162 pub fn sum_aqqmb_prod_c_scalar_barrett<const REDUCE:REDUCEMOD>(&self, a: &Poly<u64>, b: &Poly<u64>, c: &Barrett<u64>, d: &mut Poly<u64>){
163 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
164 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
165 debug_assert!(d.n() == self.n(), "d.n()={} != n={}", d.n(), self.n());
166 self.modulus.va_sub_vb_mul_sc_into_vd::<CHUNK, REDUCE>(&a.0, &b.0, c, &mut d.0);
167 }
168
169 #[inline(always)]
170 pub fn sum_aqqmb_prod_c_scalar_barrett_inplace<const REDUCE:REDUCEMOD>(&self, a: &Poly<u64>, c: &Barrett<u64>, b: &mut Poly<u64>){
171 debug_assert!(a.n() == self.n(), "a.n()={} != n={}", a.n(), self.n());
172 debug_assert!(b.n() == self.n(), "b.n()={} != n={}", b.n(), self.n());
173 self.modulus.va_sub_vb_mul_sc_into_vb::<CHUNK, REDUCE>(&a.0, c, &mut b.0);
174 }
175}