MPHELL  5.0.0
mphell-amns.c
Go to the documentation of this file.
1 /*
2  MPHELL-5.0
3  Author(s): The MPHELL team
4 
5  (C) Copyright 2015-2021 - Institut Fourier / Univ. Grenoble Alpes (France)
6 
7  This file is part of the MPHELL Library.
8  MPHELL is free software: you can redistribute it and/or modify
9  it under the terms of the GNU Lesser General Public License as published by
10  the Free Software Foundation, version 3 of the License.
11 
12  MPHELL is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU Lesser General Public License for more details.
16 
17  You should have received a copy of the GNU Lesser General Public License
18  along with MPHELL. If not, see <http://www.gnu.org/licenses/>.
19 */
20 
26 #include "mphell-amns.h"
27 
28 #if defined(__clang__) && __clang__> 3 && MPHELL_USE_OPTIMISATION == 1
29  #define PRAGMA_UNROLL _Pragma("clang loop unroll(full)")
30 #elif defined(__GNUC__) && __GNUC__> 7 && MPHELL_USE_OPTIMISATION == 1
31  #define PRAGMA_UNROLL _Pragma("GCC unroll n")
32 #else
33  #define PRAGMA_UNROLL
34 #endif
35 
36 /*********************************TEMPLATE DECLARATION*********************************/
37 
38 /*
39  * Template are use to compile 1 version of these functions for each degree n
40  * This is done because when n is not known at compile time the compiler cannot
41  * do a good optimisation of loops (unrolling, ...)
42  */
43 
44 #define TEMPLATE_amns_elt_add_declare(sl) \
45  void amns_elt_add##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS); \
46 
47 TEMPLATE_amns_elt_add_declare(2)
48 TEMPLATE_amns_elt_add_declare(3)
49 TEMPLATE_amns_elt_add_declare(4)
50 TEMPLATE_amns_elt_add_declare(5)
51 TEMPLATE_amns_elt_add_declare(6)
52 TEMPLATE_amns_elt_add_declare(7)
53 TEMPLATE_amns_elt_add_declare(8)
54 TEMPLATE_amns_elt_add_declare(9)
55 TEMPLATE_amns_elt_add_declare(10)
56 TEMPLATE_amns_elt_add_declare(11)
57 TEMPLATE_amns_elt_add_declare(12)
58 TEMPLATE_amns_elt_add_declare(13)
59 TEMPLATE_amns_elt_add_declare(14)
60 TEMPLATE_amns_elt_add_declare(15)
61 TEMPLATE_amns_elt_add_declare(16)
62 TEMPLATE_amns_elt_add_declare(17)
63 TEMPLATE_amns_elt_add_declare(18)
64 TEMPLATE_amns_elt_add_declare(19)
65 TEMPLATE_amns_elt_add_declare(20)
66 TEMPLATE_amns_elt_add_declare(21)
67 TEMPLATE_amns_elt_add_declare(22)
68 TEMPLATE_amns_elt_add_declare(23)
69 TEMPLATE_amns_elt_add_declare(24)
70 TEMPLATE_amns_elt_add_declare(25)
71 
72 #undef TEMPLATE_amns_elt_add_declare
73 
74 void amns_elt_add_generic (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS);
75 
76 #define TEMPLATE_amns_elt_sub_declare(sl) \
77  void amns_elt_sub##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS); \
78 
79 TEMPLATE_amns_elt_sub_declare(2)
80 TEMPLATE_amns_elt_sub_declare(3)
81 TEMPLATE_amns_elt_sub_declare(4)
82 TEMPLATE_amns_elt_sub_declare(5)
83 TEMPLATE_amns_elt_sub_declare(6)
84 TEMPLATE_amns_elt_sub_declare(7)
85 TEMPLATE_amns_elt_sub_declare(8)
86 TEMPLATE_amns_elt_sub_declare(9)
87 TEMPLATE_amns_elt_sub_declare(10)
88 TEMPLATE_amns_elt_sub_declare(11)
89 TEMPLATE_amns_elt_sub_declare(12)
90 TEMPLATE_amns_elt_sub_declare(13)
91 TEMPLATE_amns_elt_sub_declare(14)
92 TEMPLATE_amns_elt_sub_declare(15)
93 TEMPLATE_amns_elt_sub_declare(16)
94 TEMPLATE_amns_elt_sub_declare(17)
95 TEMPLATE_amns_elt_sub_declare(18)
96 TEMPLATE_amns_elt_sub_declare(19)
97 TEMPLATE_amns_elt_sub_declare(20)
98 TEMPLATE_amns_elt_sub_declare(21)
99 TEMPLATE_amns_elt_sub_declare(22)
100 TEMPLATE_amns_elt_sub_declare(23)
101 TEMPLATE_amns_elt_sub_declare(24)
102 TEMPLATE_amns_elt_sub_declare(25)
103 
104 #undef TEMPLATE_amns_elt_sub_declare
105 
106 void amns_elt_sub_generic (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS);
107 
108 #define TEMPLATE_amns_elt_neg_declare(sl) \
109  void amns_elt_neg##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS); \
110 
111 TEMPLATE_amns_elt_neg_declare(2)
112 TEMPLATE_amns_elt_neg_declare(3)
113 TEMPLATE_amns_elt_neg_declare(4)
114 TEMPLATE_amns_elt_neg_declare(5)
115 TEMPLATE_amns_elt_neg_declare(6)
116 TEMPLATE_amns_elt_neg_declare(7)
117 TEMPLATE_amns_elt_neg_declare(8)
118 TEMPLATE_amns_elt_neg_declare(9)
119 TEMPLATE_amns_elt_neg_declare(10)
120 TEMPLATE_amns_elt_neg_declare(11)
121 TEMPLATE_amns_elt_neg_declare(12)
122 TEMPLATE_amns_elt_neg_declare(13)
123 TEMPLATE_amns_elt_neg_declare(14)
124 TEMPLATE_amns_elt_neg_declare(15)
125 TEMPLATE_amns_elt_neg_declare(16)
126 TEMPLATE_amns_elt_neg_declare(17)
127 TEMPLATE_amns_elt_neg_declare(18)
128 TEMPLATE_amns_elt_neg_declare(19)
129 TEMPLATE_amns_elt_neg_declare(20)
130 TEMPLATE_amns_elt_neg_declare(21)
131 TEMPLATE_amns_elt_neg_declare(22)
132 TEMPLATE_amns_elt_neg_declare(23)
133 TEMPLATE_amns_elt_neg_declare(24)
134 TEMPLATE_amns_elt_neg_declare(25)
135 
136 #undef TEMPLATE_amns_elt_neg_declare
137 
138 void amns_elt_neg_generic (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS);
139 
140 #define TEMPLATE_amns_elt_mul_declare(sl) \
141  void amns_elt_mul##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS); \
142 
143 TEMPLATE_amns_elt_mul_declare(2)
144 TEMPLATE_amns_elt_mul_declare(3)
145 TEMPLATE_amns_elt_mul_declare(4)
146 TEMPLATE_amns_elt_mul_declare(5)
147 TEMPLATE_amns_elt_mul_declare(6)
148 TEMPLATE_amns_elt_mul_declare(7)
149 TEMPLATE_amns_elt_mul_declare(8)
150 TEMPLATE_amns_elt_mul_declare(9)
151 TEMPLATE_amns_elt_mul_declare(10)
152 TEMPLATE_amns_elt_mul_declare(11)
153 TEMPLATE_amns_elt_mul_declare(12)
154 TEMPLATE_amns_elt_mul_declare(13)
155 TEMPLATE_amns_elt_mul_declare(14)
156 TEMPLATE_amns_elt_mul_declare(15)
157 TEMPLATE_amns_elt_mul_declare(16)
158 TEMPLATE_amns_elt_mul_declare(17)
159 TEMPLATE_amns_elt_mul_declare(18)
160 TEMPLATE_amns_elt_mul_declare(19)
161 TEMPLATE_amns_elt_mul_declare(20)
162 TEMPLATE_amns_elt_mul_declare(21)
163 TEMPLATE_amns_elt_mul_declare(22)
164 TEMPLATE_amns_elt_mul_declare(23)
165 TEMPLATE_amns_elt_mul_declare(24)
166 TEMPLATE_amns_elt_mul_declare(25)
167 
168 #undef TEMPLATE_amns_elt_mul_declare
169 
170 #define TEMPLATE_amns_elt_mul_shift_p_declare(sl) \
171  void amns_elt_mul_shift_p##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS); \
172 
173 TEMPLATE_amns_elt_mul_shift_p_declare(2)
174 TEMPLATE_amns_elt_mul_shift_p_declare(3)
175 TEMPLATE_amns_elt_mul_shift_p_declare(4)
176 TEMPLATE_amns_elt_mul_shift_p_declare(5)
177 TEMPLATE_amns_elt_mul_shift_p_declare(6)
178 TEMPLATE_amns_elt_mul_shift_p_declare(7)
179 TEMPLATE_amns_elt_mul_shift_p_declare(8)
180 TEMPLATE_amns_elt_mul_shift_p_declare(9)
181 TEMPLATE_amns_elt_mul_shift_p_declare(10)
182 TEMPLATE_amns_elt_mul_shift_p_declare(11)
183 TEMPLATE_amns_elt_mul_shift_p_declare(12)
184 TEMPLATE_amns_elt_mul_shift_p_declare(13)
185 TEMPLATE_amns_elt_mul_shift_p_declare(14)
186 TEMPLATE_amns_elt_mul_shift_p_declare(15)
187 TEMPLATE_amns_elt_mul_shift_p_declare(16)
188 TEMPLATE_amns_elt_mul_shift_p_declare(17)
189 TEMPLATE_amns_elt_mul_shift_p_declare(18)
190 TEMPLATE_amns_elt_mul_shift_p_declare(19)
191 TEMPLATE_amns_elt_mul_shift_p_declare(20)
192 TEMPLATE_amns_elt_mul_shift_p_declare(21)
193 TEMPLATE_amns_elt_mul_shift_p_declare(22)
194 TEMPLATE_amns_elt_mul_shift_p_declare(23)
195 TEMPLATE_amns_elt_mul_shift_p_declare(24)
196 TEMPLATE_amns_elt_mul_shift_p_declare(25)
197 
198 #undef TEMPLATE_amns_elt_mul_shift_p_declare
199 
200 #define TEMPLATE_amns_elt_mul_shift_n_declare(sl) \
201  void amns_elt_mul_shift_n##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS); \
202 
203 TEMPLATE_amns_elt_mul_shift_n_declare(2)
204 TEMPLATE_amns_elt_mul_shift_n_declare(3)
205 TEMPLATE_amns_elt_mul_shift_n_declare(4)
206 TEMPLATE_amns_elt_mul_shift_n_declare(5)
207 TEMPLATE_amns_elt_mul_shift_n_declare(6)
208 TEMPLATE_amns_elt_mul_shift_n_declare(7)
209 TEMPLATE_amns_elt_mul_shift_n_declare(8)
210 TEMPLATE_amns_elt_mul_shift_n_declare(9)
211 TEMPLATE_amns_elt_mul_shift_n_declare(10)
212 TEMPLATE_amns_elt_mul_shift_n_declare(11)
213 TEMPLATE_amns_elt_mul_shift_n_declare(12)
214 TEMPLATE_amns_elt_mul_shift_n_declare(13)
215 TEMPLATE_amns_elt_mul_shift_n_declare(14)
216 TEMPLATE_amns_elt_mul_shift_n_declare(15)
217 TEMPLATE_amns_elt_mul_shift_n_declare(16)
218 TEMPLATE_amns_elt_mul_shift_n_declare(17)
219 TEMPLATE_amns_elt_mul_shift_n_declare(18)
220 TEMPLATE_amns_elt_mul_shift_n_declare(19)
221 TEMPLATE_amns_elt_mul_shift_n_declare(20)
222 TEMPLATE_amns_elt_mul_shift_n_declare(21)
223 TEMPLATE_amns_elt_mul_shift_n_declare(22)
224 TEMPLATE_amns_elt_mul_shift_n_declare(23)
225 TEMPLATE_amns_elt_mul_shift_n_declare(24)
226 TEMPLATE_amns_elt_mul_shift_n_declare(25)
227 
228 #undef TEMPLATE_amns_elt_mul_shift_n_declare
229 
230 void amns_elt_mul_generic (amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS);
231 
232 #define TEMPLATE_amns_elt_sqr_declare(sl) \
233  void amns_elt_sqr##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS); \
234 
235 TEMPLATE_amns_elt_sqr_declare(2)
236 TEMPLATE_amns_elt_sqr_declare(3)
237 TEMPLATE_amns_elt_sqr_declare(4)
238 TEMPLATE_amns_elt_sqr_declare(5)
239 TEMPLATE_amns_elt_sqr_declare(6)
240 TEMPLATE_amns_elt_sqr_declare(7)
241 TEMPLATE_amns_elt_sqr_declare(8)
242 TEMPLATE_amns_elt_sqr_declare(9)
243 TEMPLATE_amns_elt_sqr_declare(10)
244 TEMPLATE_amns_elt_sqr_declare(11)
245 TEMPLATE_amns_elt_sqr_declare(12)
246 TEMPLATE_amns_elt_sqr_declare(13)
247 TEMPLATE_amns_elt_sqr_declare(14)
248 TEMPLATE_amns_elt_sqr_declare(15)
249 TEMPLATE_amns_elt_sqr_declare(16)
250 TEMPLATE_amns_elt_sqr_declare(17)
251 TEMPLATE_amns_elt_sqr_declare(18)
252 TEMPLATE_amns_elt_sqr_declare(19)
253 TEMPLATE_amns_elt_sqr_declare(20)
254 TEMPLATE_amns_elt_sqr_declare(21)
255 TEMPLATE_amns_elt_sqr_declare(22)
256 TEMPLATE_amns_elt_sqr_declare(23)
257 TEMPLATE_amns_elt_sqr_declare(24)
258 TEMPLATE_amns_elt_sqr_declare(25)
259 
260 #undef TEMPLATE_amns_elt_sqr_declare
261 
262 #define TEMPLATE_amns_elt_sqr_shift_p_declare(sl) \
263  void amns_elt_sqr_shift_p##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS); \
264 
265 TEMPLATE_amns_elt_sqr_shift_p_declare(2)
266 TEMPLATE_amns_elt_sqr_shift_p_declare(3)
267 TEMPLATE_amns_elt_sqr_shift_p_declare(4)
268 TEMPLATE_amns_elt_sqr_shift_p_declare(5)
269 TEMPLATE_amns_elt_sqr_shift_p_declare(6)
270 TEMPLATE_amns_elt_sqr_shift_p_declare(7)
271 TEMPLATE_amns_elt_sqr_shift_p_declare(8)
272 TEMPLATE_amns_elt_sqr_shift_p_declare(9)
273 TEMPLATE_amns_elt_sqr_shift_p_declare(10)
274 TEMPLATE_amns_elt_sqr_shift_p_declare(11)
275 TEMPLATE_amns_elt_sqr_shift_p_declare(12)
276 TEMPLATE_amns_elt_sqr_shift_p_declare(13)
277 TEMPLATE_amns_elt_sqr_shift_p_declare(14)
278 TEMPLATE_amns_elt_sqr_shift_p_declare(15)
279 TEMPLATE_amns_elt_sqr_shift_p_declare(16)
280 TEMPLATE_amns_elt_sqr_shift_p_declare(17)
281 TEMPLATE_amns_elt_sqr_shift_p_declare(18)
282 TEMPLATE_amns_elt_sqr_shift_p_declare(19)
283 TEMPLATE_amns_elt_sqr_shift_p_declare(20)
284 TEMPLATE_amns_elt_sqr_shift_p_declare(21)
285 TEMPLATE_amns_elt_sqr_shift_p_declare(22)
286 TEMPLATE_amns_elt_sqr_shift_p_declare(23)
287 TEMPLATE_amns_elt_sqr_shift_p_declare(24)
288 TEMPLATE_amns_elt_sqr_shift_p_declare(25)
289 
290 #undef TEMPLATE_amns_elt_sqr_shift_p_declare
291 
292 #define TEMPLATE_amns_elt_sqr_shift_n_declare(sl) \
293  void amns_elt_sqr_shift_n##sl (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS); \
294 
295 TEMPLATE_amns_elt_sqr_shift_n_declare(2)
296 TEMPLATE_amns_elt_sqr_shift_n_declare(3)
297 TEMPLATE_amns_elt_sqr_shift_n_declare(4)
298 TEMPLATE_amns_elt_sqr_shift_n_declare(5)
299 TEMPLATE_amns_elt_sqr_shift_n_declare(6)
300 TEMPLATE_amns_elt_sqr_shift_n_declare(7)
301 TEMPLATE_amns_elt_sqr_shift_n_declare(8)
302 TEMPLATE_amns_elt_sqr_shift_n_declare(9)
303 TEMPLATE_amns_elt_sqr_shift_n_declare(10)
304 TEMPLATE_amns_elt_sqr_shift_n_declare(11)
305 TEMPLATE_amns_elt_sqr_shift_n_declare(12)
306 TEMPLATE_amns_elt_sqr_shift_n_declare(13)
307 TEMPLATE_amns_elt_sqr_shift_n_declare(14)
308 TEMPLATE_amns_elt_sqr_shift_n_declare(15)
309 TEMPLATE_amns_elt_sqr_shift_n_declare(16)
310 TEMPLATE_amns_elt_sqr_shift_n_declare(17)
311 TEMPLATE_amns_elt_sqr_shift_n_declare(18)
312 TEMPLATE_amns_elt_sqr_shift_n_declare(19)
313 TEMPLATE_amns_elt_sqr_shift_n_declare(20)
314 TEMPLATE_amns_elt_sqr_shift_n_declare(21)
315 TEMPLATE_amns_elt_sqr_shift_n_declare(22)
316 TEMPLATE_amns_elt_sqr_shift_n_declare(23)
317 TEMPLATE_amns_elt_sqr_shift_n_declare(24)
318 TEMPLATE_amns_elt_sqr_shift_n_declare(25)
319 
320 #undef TEMPLATE_amns_elt_sqr_shift_n_declare
321 
322 void amns_elt_sqr_generic (amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS);
323 
324 #define TEMPLATE_amns_internal_red_declare(sl) \
325  void amns_internal_red##sl(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS); \
326 
327 TEMPLATE_amns_internal_red_declare(2)
328 TEMPLATE_amns_internal_red_declare(3)
329 TEMPLATE_amns_internal_red_declare(4)
330 TEMPLATE_amns_internal_red_declare(5)
331 TEMPLATE_amns_internal_red_declare(6)
332 TEMPLATE_amns_internal_red_declare(7)
333 TEMPLATE_amns_internal_red_declare(8)
334 TEMPLATE_amns_internal_red_declare(9)
335 TEMPLATE_amns_internal_red_declare(10)
336 TEMPLATE_amns_internal_red_declare(11)
337 TEMPLATE_amns_internal_red_declare(12)
338 TEMPLATE_amns_internal_red_declare(13)
339 TEMPLATE_amns_internal_red_declare(14)
340 TEMPLATE_amns_internal_red_declare(15)
341 TEMPLATE_amns_internal_red_declare(16)
342 TEMPLATE_amns_internal_red_declare(17)
343 TEMPLATE_amns_internal_red_declare(18)
344 TEMPLATE_amns_internal_red_declare(19)
345 TEMPLATE_amns_internal_red_declare(20)
346 TEMPLATE_amns_internal_red_declare(21)
347 TEMPLATE_amns_internal_red_declare(22)
348 TEMPLATE_amns_internal_red_declare(23)
349 TEMPLATE_amns_internal_red_declare(24)
350 TEMPLATE_amns_internal_red_declare(25)
351 
352 #undef TEMPLATE_amns_internal_red_declare
353 
354 void amns_internal_red_generic(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS);
355 
356 #define TEMPLATE_amns_elt_is_reduced_declare(sl) \
357  static inline bool amns_elt_is_reduced##sl (amns_elt_srcptr a, amns_srcptr AMNS); \
358 
359 TEMPLATE_amns_elt_is_reduced_declare(2)
360 TEMPLATE_amns_elt_is_reduced_declare(3)
361 TEMPLATE_amns_elt_is_reduced_declare(4)
362 TEMPLATE_amns_elt_is_reduced_declare(5)
363 TEMPLATE_amns_elt_is_reduced_declare(6)
364 TEMPLATE_amns_elt_is_reduced_declare(7)
365 TEMPLATE_amns_elt_is_reduced_declare(8)
366 TEMPLATE_amns_elt_is_reduced_declare(9)
367 TEMPLATE_amns_elt_is_reduced_declare(10)
368 TEMPLATE_amns_elt_is_reduced_declare(11)
369 TEMPLATE_amns_elt_is_reduced_declare(12)
370 TEMPLATE_amns_elt_is_reduced_declare(13)
371 TEMPLATE_amns_elt_is_reduced_declare(14)
372 TEMPLATE_amns_elt_is_reduced_declare(15)
373 TEMPLATE_amns_elt_is_reduced_declare(16)
374 TEMPLATE_amns_elt_is_reduced_declare(17)
375 TEMPLATE_amns_elt_is_reduced_declare(18)
376 TEMPLATE_amns_elt_is_reduced_declare(19)
377 TEMPLATE_amns_elt_is_reduced_declare(20)
378 TEMPLATE_amns_elt_is_reduced_declare(21)
379 TEMPLATE_amns_elt_is_reduced_declare(22)
380 TEMPLATE_amns_elt_is_reduced_declare(23)
381 TEMPLATE_amns_elt_is_reduced_declare(24)
382 TEMPLATE_amns_elt_is_reduced_declare(25)
383 
384 #undef TEMPLATE_amns_elt_is_reduced_declare
385 
386 static inline bool amns_elt_is_reduced_generic (amns_elt_srcptr a, amns_srcptr AMNS);
387 
388 
389 /**************************************ALLOCATION**************************************/
390 
391 void amns_alloc(amns_ptr * AMNS, uint8_t n, number_srcptr p)
392 {
393  uint16_t i;
394 
395  (*AMNS)=(amns_ptr)malloc(sizeof(amns_t));
396 
397  number_init(&((*AMNS)->p), number_block_size(p));
398  (*AMNS)->p_size = number_log2(p);
399 
400  number_init(&((*AMNS)->gamma), number_block_size(p));
401 
402  (*AMNS)->n = n;
403  (*AMNS)->E = (amns_block *)malloc((n+1) * sizeof(amns_block));
404 
405  (*AMNS)->Mti = (amns_elt *)malloc(n * sizeof(amns_elt));
406  for(i=0; i<n; i++)
407  {
408  amns_elt_alloc(&((*AMNS)->Mti[i]), *AMNS);
409  }
410 
411  (*AMNS)->Mtiprime = (amns_elt *)malloc(n * sizeof(amns_elt));
412  for(i=0; i<n; i++)
413  {
414  amns_elt_alloc(&((*AMNS)->Mtiprime[i]), *AMNS);
415  }
416 
417  (*AMNS)->Ti = (amns_elt *)malloc(n*sizeof(amns_elt));
418  for(i=0; i<n; i++)
419  {
420  amns_elt_alloc(((*AMNS)->Ti)+i, *AMNS);
421  }
422 
423  (*AMNS)->gi = (number *)malloc(n*sizeof(number));
424  for(i=0; i<n; i++)
425  {
426  number_init(((*AMNS)->gi)+i, bits_to_nblock((*AMNS)->p_size));
427  }
428 
429  /* Pools creation */
430  (*AMNS)->i_1 = 0;
431  for(i=0; i<POOL_SIZE_AMNS; i++)
432  {
433  amns_elt_alloc(((*AMNS)->pool_1)+i, *AMNS);
434  }
435 #if MPHELL_USE_MULTITHREADING == 1
436  (*AMNS)->i_2 = 0;
437  for(i=0; i<POOL_SIZE_AMNS; i++)
438  {
439  amns_elt_alloc(((*AMNS)->pool_2)+i, *AMNS);
440  }
441 #endif
442 }
443 
444 void amns_free(amns_ptr * AMNS)
445 {
446  uint16_t i;
447  uint8_t n = (*AMNS)->n;
448  /* Pools free */
449  (*AMNS)->i_1 = 0;
450  for(i=0; i<POOL_SIZE_AMNS; i++)
451  {
452  amns_elt_free(((*AMNS)->pool_1)+i);
453  }
454 #if MPHELL_USE_MULTITHREADING == 1
455  (*AMNS)->i_2 = 0;
456  for(i=0; i<POOL_SIZE_AMNS; i++)
457  {
458  amns_elt_free(((*AMNS)->pool_2)+i);
459  }
460 #endif
461 
462  number_free(&((*AMNS)->p));
463  number_free(&((*AMNS)->gamma));
464 
465  for(i=0; i<n; i++)
466  {
467  amns_elt_free(((*AMNS)->Mti)+i);
468  }
469  for(i=0; i<n; i++)
470  {
471  amns_elt_free(((*AMNS)->Mtiprime)+i);
472  }
473 
474  for(i=0; i<n; i++)
475  {
476  amns_elt_free(((*AMNS)->Ti)+i);
477  }
478 
479  for(i=0; i<n; i++)
480  {
481  number_free(((*AMNS)->gi)+i);
482  }
483 
484  free((*AMNS)->E);
485 
486  free((*AMNS)->Mti);
487  free((*AMNS)->Mtiprime);
488 
489  free((*AMNS)->Ti);
490  free((*AMNS)->gi);
491 
492  free(*AMNS);
493  *AMNS = NULL;
494 }
495 
496 void amns_elt_alloc(amns_elt * dst, amns_srcptr AMNS)
497 {
498  *dst = (amns_elt)malloc(sizeof(amns_block) * AMNS->n);
499 }
500 
501 void amns_elt_free(amns_elt * dst)
502 {
503  free(*dst);
504  *dst = NULL;
505 }
506 
507 
508 /*****************************************PRINT****************************************/
509 
510 void amns_print_bloc(amns_block b)
511 {
512 #if MPHELL_USE_AMNS_32 == 1
513  printf("%d", b);
514 #else
515  printf("%ld", b);
516 #endif
517 }
518 
524 void amns_print_bloc_ul(amns_ulong b)
525 {
526 #if MPHELL_USE_AMNS_32 == 1
527  printf("%u", b);
528 #else
529  printf("%lu", b);
530 #endif
531 }
532 
533 void amns_print_elt_raw(const amns_block * x, uint8_t size)
534 {
535  printf("[");
536  uint8_t i;
537  for(i=0; i<size-1; i++)
538  {
539  amns_print_bloc(x[i]); printf("\t");
540  }
541  amns_print_bloc(x[i]); printf("]");
542 }
543 
550 void amns_print_elt_raw_ul(const amns_ulong * x, uint8_t size)
551 {
552  printf("[");
553  uint8_t i;
554  for(i=0; i<size-1; i++)
555  {
556  amns_print_bloc_ul(x[i]); printf("\t");
557  }
558  amns_print_bloc_ul(x[i]); printf("]");
559 }
560 
561 void amns_print_elt(amns_elt_srcptr x, amns_srcptr AMNS)
562 {
563  amns_print_elt_raw(x, AMNS->n);
564 }
565 
572 void amns_print_elt_ul(const amns_ulong * x, amns_srcptr AMNS)
573 {
574  amns_print_elt_raw_ul(x, AMNS->n);
575 }
576 
577 void amns_print_AMNS(amns_srcptr AMNS)
578 {
579  printf("p = "); number_print(AMNS->p, 10); printf("\n");
580  printf("p_size = %u\n", AMNS->p_size);
581  printf("n = %u\n", AMNS->n);
582  printf("rho used = %u\n", AMNS->rho);
583  printf("max_digit = "); amns_print_bloc(AMNS->max_digit); printf("\n");
584  printf("min_digit = "); amns_print_bloc(AMNS->min_digit); printf("\n");
585  printf("E = "); amns_print_elt_raw(AMNS->E, AMNS->n+1); printf("\n");
586  printf("lambda = "); amns_print_bloc(AMNS->lambda); printf("\n");
587  printf("lambda_bits = %u\n", AMNS->lambda_bit);
588  printf("k = %u\n", AMNS->k);
589  printf("gamma = "); number_print(AMNS->gamma, 10); printf("\n");
590  printf("gamma_size = %u\n\n", AMNS->gamma_size);
591 
592  uint8_t j;
593 
594  for(j=0; j<AMNS->n; j++)
595  {
596  printf("Mti[%u] = ", j); amns_print_elt(AMNS->Mti[j], AMNS); printf("\n");
597  }
598  printf("\n");
599 
600  for(j=0; j<AMNS->n; j++)
601  {
602  printf("Mtiprime[%u] = ", j); amns_print_elt(AMNS->Mtiprime[j], AMNS); printf("\n");
603  }
604  printf("\n");
605 
606 #if MPHELL_USE_DEBUG == 1
607 
608  for(j=0; j<AMNS->n; j++)
609  {
610  printf("Ti[%u] = ", j); amns_print_elt(AMNS->Ti[j], AMNS); printf("\n");
611  }
612  printf("\n");
613 
614  for(j=0; j<AMNS->n; j++)
615  {
616  printf("gi[%u] = ", j); number_print(AMNS->gi[j], 10); printf("\n");
617  }
618  printf("\n");
619 #endif
620 }
621 
622 void amns_print_stat(amns_srcptr AMNS)
623 {
624 #if MPHELL_USE_DEBUG == 1
625  printf("Statistics: \n");
626  printf("nb_add = %d \n", AMNS->nb_add);
627  printf("nb_sub = %d \n", AMNS->nb_sub);
628  printf("nb_mul = %d \n", AMNS->nb_mul);
629  printf("nb_add_red = %d \n", AMNS->nb_add_red);
630  printf("nb_sub_red = %d \n", AMNS->nb_sub_red);
631  printf("nb_mul_red = %d \n", AMNS->nb_mul_red);
632 #endif
633 }
634 
635 
636 /****************************************HELPER****************************************/
637 
645 uint8_t amns_calculate_max_coeff_size(amns_elt_srcptr a, amns_srcptr AMNS)
646 {
647  const uint8_t n = AMNS->n;
648  uint8_t i;
649  amns_block m = 0;
650  for(i = 0; i<n; i++)
651  {
652  if((a[i]>m))
653  {
654  m = a[i];
655  }
656  else if(a[i] < -m)
657  {
658  m = - a[i];
659  }
660  }
661  return floor(log(m)/log(2))+1;
662 }
663 
671 amns_block amns_calculate_max_coeff(amns_elt_srcptr a, amns_srcptr AMNS)
672 {
673  const uint8_t n = AMNS->n;
674  uint8_t i;
675  amns_block m = 0;
676  for(i = 0; i<n; i++)
677  {
678  if((a[i]>m))
679  {
680  m = a[i];
681  }
682  else if(a[i] < -m)
683  {
684  m = - a[i];
685  }
686  }
687  return m;
688 }
689 
697 void amns_internal_red_generic(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS)
698 {
699  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */
700  const uint8_t n = AMNS->n;
701  uint8_t i, j;
702 
703  /* Q = V * Mprime mod(E, phi) */
704 
705  amns_block Q[n];
706  for(i=0; i<n; i++)
707  {
708  Q[i]=((amns_block)V[0])*AMNS->Mtiprime[i][0];
709  for(j=1; j<n; j++)
710  {
711  Q[i]+=((amns_block)V[j])*AMNS->Mtiprime[i][j];
712  }
713  }
714 
715  /* T = Q * M mod(E) */
716 
717  amns_llong T[n];
718  for(i=0; i<n; i++)
719  {
720  T[i]=(amns_llong)Q[0]*AMNS->Mti[i][0];
721  for(j=1; j<n; j++)
722  {
723  T[i]+=(amns_llong)Q[j]*AMNS->Mti[i][j];
724  }
725  /* S = (V + T)/phi */
726  S[i]=(T[i]+V[i])>>AMNS_WORD_SIZE;
727 
728  }
729 
730  MPHELL_ASSERT(amns_calculate_max_coeff(S, AMNS) < AMNS->max_digit, "amns_internal_red, ||dst||_infiny >= max_digit\n");
731 }
732 
740 void amns_internal_red(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS)
741 {
742  AMNS->amns_internal_red(S, V, AMNS);
743 }
744 
745 #define TEMPLATE_amns_internal_red(sl) \
746  void \
747  amns_internal_red##sl(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS) \
748  { \
749  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
750  const uint8_t n = sl; \
751  int8_t i, j; \
752  \
753  /* Q = V * Mprime mod(E, phi) */ \
754  \
755  amns_block Q[n]; \
756  PRAGMA_UNROLL \
757  for(i=0; i<n; i++) \
758  { \
759  Q[i]=((amns_block)V[0])*AMNS->Mtiprime[i][0]; \
760  PRAGMA_UNROLL \
761  for(j=1; j<n; j++) \
762  { \
763  Q[i]+=((amns_block)V[j])*AMNS->Mtiprime[i][j]; \
764  } \
765  } \
766  \
767  /* T = Q * M mod(E) */ \
768  \
769  amns_llong T[n]; \
770  PRAGMA_UNROLL \
771  for(i=0; i<n; i++) \
772  { \
773  T[i]=(amns_llong)Q[0]*AMNS->Mti[i][0]; \
774  PRAGMA_UNROLL \
775  for(j=1; j<n; j++) \
776  { \
777  T[i]+=(amns_llong)Q[j]*AMNS->Mti[i][j]; \
778  } \
779  /* S = (V + T)/phi */ \
780  S[i]=(T[i]+V[i])>>AMNS_WORD_SIZE; \
781  } \
782  MPHELL_ASSERT(amns_calculate_max_coeff(S, AMNS) < AMNS->max_digit, "amns_internal_red, ||dst||_infiny >= max_digit\n"); \
783 } \
784 
785 TEMPLATE_amns_internal_red(2)
786 TEMPLATE_amns_internal_red(3)
787 TEMPLATE_amns_internal_red(4)
788 TEMPLATE_amns_internal_red(5)
789 TEMPLATE_amns_internal_red(6)
790 TEMPLATE_amns_internal_red(7)
791 TEMPLATE_amns_internal_red(8)
792 TEMPLATE_amns_internal_red(9)
793 TEMPLATE_amns_internal_red(10)
794 TEMPLATE_amns_internal_red(11)
795 TEMPLATE_amns_internal_red(12)
796 TEMPLATE_amns_internal_red(13)
797 TEMPLATE_amns_internal_red(14)
798 TEMPLATE_amns_internal_red(15)
799 TEMPLATE_amns_internal_red(16)
800 TEMPLATE_amns_internal_red(17)
801 TEMPLATE_amns_internal_red(18)
802 TEMPLATE_amns_internal_red(19)
803 TEMPLATE_amns_internal_red(20)
804 TEMPLATE_amns_internal_red(21)
805 TEMPLATE_amns_internal_red(22)
806 TEMPLATE_amns_internal_red(23)
807 TEMPLATE_amns_internal_red(24)
808 TEMPLATE_amns_internal_red(25)
809 
810 #undef TEMPLATE_amns_internal_red
811 
812 
813 #if MPHELL_USE_AMNS_32 == 0
814 void internal_reduction_nist521_64(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS)
815 {
816  uint64_t tmp_q[10];
817  amns_llong tmp_zero[10];
818 
819  tmp_q[0] = (uint64_t)V[0] + ((((uint64_t)V[9] << 53)));
820  tmp_q[1] = ((uint64_t)V[0] << 52) + (uint64_t)V[1];
821  tmp_q[2] = ((uint64_t)V[1] << 52) + (uint64_t)V[2];
822  tmp_q[3] = ((uint64_t)V[2] << 52) + (uint64_t)V[3];
823  tmp_q[4] = ((uint64_t)V[3] << 52) + (uint64_t)V[4];
824  tmp_q[5] = ((uint64_t)V[4] << 52) + (uint64_t)V[5];
825  tmp_q[6] = ((uint64_t)V[5] << 52) + (uint64_t)V[6];
826  tmp_q[7] = ((uint64_t)V[6] << 52) + (uint64_t)V[7];
827  tmp_q[8] = ((uint64_t)V[7] << 52) + (uint64_t)V[8];
828  tmp_q[9] = ((uint64_t)V[8] << 52) + (uint64_t)V[9];
829 
830  tmp_zero[0] = -(amns_llong)tmp_q[0] + ((((amns_llong)tmp_q[9] << 53)));
831  tmp_zero[1] = ((amns_llong)tmp_q[0] << 52) - (amns_llong)tmp_q[1];
832  tmp_zero[2] = ((amns_llong)tmp_q[1] << 52) - (amns_llong)tmp_q[2];
833  tmp_zero[3] = ((amns_llong)tmp_q[2] << 52) - (amns_llong)tmp_q[3];
834  tmp_zero[4] = ((amns_llong)tmp_q[3] << 52) - (amns_llong)tmp_q[4];
835  tmp_zero[5] = ((amns_llong)tmp_q[4] << 52) - (amns_llong)tmp_q[5];
836  tmp_zero[6] = ((amns_llong)tmp_q[5] << 52) - (amns_llong)tmp_q[6];
837  tmp_zero[7] = ((amns_llong)tmp_q[6] << 52) - (amns_llong)tmp_q[7];
838  tmp_zero[8] = ((amns_llong)tmp_q[7] << 52) - (amns_llong)tmp_q[8];
839  tmp_zero[9] = ((amns_llong)tmp_q[8] << 52) - (amns_llong)tmp_q[9];
840 
841  S[0] = (V[0] + tmp_zero[0]) >> 64;
842  S[1] = (V[1] + tmp_zero[1]) >> 64;
843  S[2] = (V[2] + tmp_zero[2]) >> 64;
844  S[3] = (V[3] + tmp_zero[3]) >> 64;
845  S[4] = (V[4] + tmp_zero[4]) >> 64;
846  S[5] = (V[5] + tmp_zero[5]) >> 64;
847  S[6] = (V[6] + tmp_zero[6]) >> 64;
848  S[7] = (V[7] + tmp_zero[7]) >> 64;
849  S[8] = (V[8] + tmp_zero[8]) >> 64;
850  S[9] = (V[9] + tmp_zero[9]) >> 64;
851 }
852 #else
853 void internal_reduction_nist521_32(amns_elt_ptr S, amns_llong * V, amns_srcptr AMNS)
854 {
855  uint64_t tmp_q[10];
856  amns_llong tmp_zero[10];
857 
858  tmp_q[0] = (uint32_t)V[0] + ((((uint32_t)V[7] << 24)));
859  tmp_q[1] = (uint32_t)V[1] + ((((uint32_t)V[8] << 24)));
860  tmp_q[2] = (uint32_t)V[2] + ((((uint32_t)V[9] << 24)));
861  tmp_q[3] = (uint32_t)V[3] + ((((uint32_t)V[10] << 24)));
862  tmp_q[4] = (uint32_t)V[4] + ((((uint32_t)V[11] << 24)));
863  tmp_q[5] = (uint32_t)V[5] + ((((uint32_t)V[12] << 24)));
864  tmp_q[6] = (uint32_t)V[6] + ((((uint32_t)V[13] << 24)));
865  tmp_q[7] = (uint32_t)V[7] + ((((uint32_t)V[14] << 24)));
866  tmp_q[8] = (uint32_t)V[8] + ((((uint32_t)V[15] << 24)));
867  tmp_q[9] = (uint32_t)V[9] + ((((uint32_t)V[16] << 24)));
868  tmp_q[10] = (uint32_t)V[10] + ((((uint32_t)V[17] << 24)));
869  tmp_q[11] = (uint32_t)V[11] + ((((uint32_t)V[18] << 24)));
870  tmp_q[12] = (uint32_t)V[12] + ((((uint32_t)V[19] << 24)));
871  tmp_q[13] = (uint32_t)V[13] + ((((uint32_t)V[20] << 24)));
872  tmp_q[14] = (uint32_t)V[14] + ((((uint32_t)V[21] << 24)));
873  tmp_q[15] = ((uint32_t)V[0] << 23) + (uint32_t)V[15];
874  tmp_q[16] = ((uint32_t)V[1] << 23) + (uint32_t)V[16];
875  tmp_q[17] = ((uint32_t)V[2] << 23) + (uint32_t)V[17];
876  tmp_q[18] = ((uint32_t)V[3] << 23) + (uint32_t)V[18];
877  tmp_q[19] = ((uint32_t)V[4] << 23) + (uint32_t)V[19];
878  tmp_q[20] = ((uint32_t)V[5] << 23) + (uint32_t)V[20];
879  tmp_q[21] = ((uint32_t)V[6] << 23) + (uint32_t)V[21];
880 
881  /* ~ computation of : tmp_q*red_int_coeff mod(X^n - c) */
882  tmp_zero[0] = -(amns_llong)tmp_q[0] + ((((amns_llong)tmp_q[7] << 24)));
883  tmp_zero[1] = -(amns_llong)tmp_q[1] + ((((amns_llong)tmp_q[8] << 24)));
884  tmp_zero[2] = -(amns_llong)tmp_q[2] + ((((amns_llong)tmp_q[9] << 24)));
885  tmp_zero[3] = -(amns_llong)tmp_q[3] + ((((amns_llong)tmp_q[10] << 24)));
886  tmp_zero[4] = -(amns_llong)tmp_q[4] + ((((amns_llong)tmp_q[11] << 24)));
887  tmp_zero[5] = -(amns_llong)tmp_q[5] + ((((amns_llong)tmp_q[12] << 24)));
888  tmp_zero[6] = -(amns_llong)tmp_q[6] + ((((amns_llong)tmp_q[13] << 24)));
889  tmp_zero[7] = -(amns_llong)tmp_q[7] + ((((amns_llong)tmp_q[14] << 24)));
890  tmp_zero[8] = -(amns_llong)tmp_q[8] + ((((amns_llong)tmp_q[15] << 24)));
891  tmp_zero[9] = -(amns_llong)tmp_q[9] + ((((amns_llong)tmp_q[16] << 24)));
892  tmp_zero[10] = -(amns_llong)tmp_q[10] + ((((amns_llong)tmp_q[17] << 24)));
893  tmp_zero[11] = -(amns_llong)tmp_q[11] + ((((amns_llong)tmp_q[18] << 24)));
894  tmp_zero[12] = -(amns_llong)tmp_q[12] + ((((amns_llong)tmp_q[19] << 24)));
895  tmp_zero[13] = -(amns_llong)tmp_q[13] + ((((amns_llong)tmp_q[20] << 24)));
896  tmp_zero[14] = -(amns_llong)tmp_q[14] + ((((amns_llong)tmp_q[21] << 24)));
897  tmp_zero[15] = ((amns_llong)tmp_q[0] << 23) - (amns_llong)tmp_q[15];
898  tmp_zero[16] = ((amns_llong)tmp_q[1] << 23) - (amns_llong)tmp_q[16];
899  tmp_zero[17] = ((amns_llong)tmp_q[2] << 23) - (amns_llong)tmp_q[17];
900  tmp_zero[18] = ((amns_llong)tmp_q[3] << 23) - (amns_llong)tmp_q[18];
901  tmp_zero[19] = ((amns_llong)tmp_q[4] << 23) - (amns_llong)tmp_q[19];
902  tmp_zero[20] = ((amns_llong)tmp_q[5] << 23) - (amns_llong)tmp_q[20];
903  tmp_zero[21] = ((amns_llong)tmp_q[6] << 23) - (amns_llong)tmp_q[21];
904 
905  /* ~ computation of : (V + tmp_zero)/mont_phi */
906  S[0] = (V[0] + tmp_zero[0]) >> 32;
907  S[1] = (V[1] + tmp_zero[1]) >> 32;
908  S[2] = (V[2] + tmp_zero[2]) >> 32;
909  S[3] = (V[3] + tmp_zero[3]) >> 32;
910  S[4] = (V[4] + tmp_zero[4]) >> 32;
911  S[5] = (V[5] + tmp_zero[5]) >> 32;
912  S[6] = (V[6] + tmp_zero[6]) >> 32;
913  S[7] = (V[7] + tmp_zero[7]) >> 32;
914  S[8] = (V[8] + tmp_zero[8]) >> 32;
915  S[9] = (V[9] + tmp_zero[9]) >> 32;
916  S[10] = (V[10] + tmp_zero[10]) >> 32;
917  S[11] = (V[11] + tmp_zero[11]) >> 32;
918  S[12] = (V[12] + tmp_zero[12]) >> 32;
919  S[13] = (V[13] + tmp_zero[13]) >> 32;
920  S[14] = (V[14] + tmp_zero[14]) >> 32;
921  S[15] = (V[15] + tmp_zero[15]) >> 32;
922  S[16] = (V[16] + tmp_zero[16]) >> 32;
923  S[17] = (V[17] + tmp_zero[17]) >> 32;
924  S[18] = (V[18] + tmp_zero[18]) >> 32;
925  S[19] = (V[19] + tmp_zero[19]) >> 32;
926  S[20] = (V[20] + tmp_zero[20]) >> 32;
927  S[21] = (V[21] + tmp_zero[21]) >> 32;
928 }
929 #endif
930 
935 void set_fast_internal_reduction_nist521(amns_ptr AMNS)
936 {
937 #if MPHELL_USE_AMNS_32 == 0
938  AMNS->amns_internal_red=&internal_reduction_nist521_64;
939 #else
940  AMNS->amns_internal_red=&internal_reduction_nist521_32;
941 #endif
942 }
943 
944 
951 void amns_internal_red_exact(amns_elt_ptr dst, amns_srcptr AMNS)
952 {
953  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */
954  const uint8_t n = AMNS->n;
955  int8_t i;
956 
957  amns_llong tmp[n];
958 
959  for(i=0; i<n; i++)
960  {
961  tmp[i] = (amns_llong) dst[i];
962  }
963 
964  amns_elt T;
965  amns_elt_get_pool_elt(&T, AMNS, STACK_1);
966 
967  amns_internal_red(T, tmp, AMNS);
968  amns_elt_mul(dst, T, AMNS->Ti[0], AMNS);
969 
970  amns_elt_relax_pool_elt(&T, AMNS, STACK_1);
971 
972  MPHELL_ASSERT(amns_calculate_max_coeff(dst, AMNS) < AMNS->max_digit, "amns_internal_red, ||dst||_infiny >= max_digit\n");
973 }
974 
975 
983 void amns_calcule_Ti(amns_ptr AMNS, const amns_block * P0, const amns_block * P1)
984 {
985  const uint8_t n = AMNS->n;
986  uint8_t i;
987 
988  /* Copy P0 and P1 (given by the user) */
989  amns_elt_copy(AMNS->Ti[0], P0, AMNS);
990  amns_elt_copy(AMNS->Ti[1], P1, AMNS);
991 
992  /* Calculate tmp = rho * phi */
993 
994  amns_llong p1[n];
995 
996  for(i=0; i<n; i++)
997  {
998  p1[i] = (amns_llong) P1[i];
999  }
1000 
1001  amns_elt tmp;
1002  amns_elt_get_pool_elt(&tmp, AMNS, STACK_1);
1003  amns_internal_red(tmp, p1, AMNS);
1004 
1005  /* Calcul Ti[i] ; i>1 */
1006 
1007  for(i = 1; i<n-1; i++)
1008  {
1009  /* Ti[i+1] = tmp * Ti[i] */
1010  amns_elt_mul(AMNS->Ti[i+1], tmp, AMNS->Ti[i], AMNS);
1011  }
1012  amns_elt_relax_pool_elt(&tmp, AMNS, STACK_1);
1013 }
1014 
1020 void amns_calcule_gi(amns_ptr AMNS)
1021 {
1022  const uint8_t n = AMNS->n;
1023  uint8_t i;
1024  for(i = 0; i < 2; i++)
1025  {
1026  number_powm_ui(AMNS->gi[i], AMNS->gamma, i, AMNS->p, STACK_1);
1027  }
1028  for(i = 2; i < n; i++)
1029  {
1030  number_mul_mod(AMNS->gi[i], AMNS->gamma, AMNS->gi[i-1], AMNS->p, STACK_1);
1031  }
1032 }
1033 
1040 void amns_calcule_Mi(amns_ptr AMNS, const amns_block * M)
1041 {
1042  const uint8_t n = AMNS->n;
1043  amns_block Mi[n][n];
1044  int8_t i, j;
1045  for(i=0; i<n; i++)
1046  {
1047  for(j=0; j<n; j++)
1048  {
1049  if(j-i >= 0)
1050  {
1051  Mi[i][j]=M[j-i];
1052  }
1053  else
1054  {
1055  Mi[i][j]=M[n+j-i] * AMNS->lambda;
1056  }
1057  }
1058  }
1059 
1060  for(i=0; i<n; i++)
1061  {
1062  for(j=0; j<n; j++)
1063  {
1064  AMNS->Mti[i][j]=Mi[j][i];
1065  }
1066  }
1067 }
1068 
1075 void amns_calcule_Miprime(amns_ptr AMNS, const amns_block * Mprime)
1076 {
1077  const uint8_t n = AMNS->n;
1078  amns_block Miprime[n][n];
1079  int8_t i, j;
1080  for(i=0; i<n; i++)
1081  {
1082  for(j=0; j<n; j++)
1083  {
1084  if(j-i >= 0)
1085  {
1086  Miprime[i][j]=Mprime[j-i];
1087  }
1088  else
1089  {
1090  Miprime[i][j]=Mprime[n+j-i] * AMNS->lambda;
1091  }
1092  }
1093  }
1094 
1095  for(i=0; i<n; i++)
1096  {
1097  for(j=0; j<n; j++)
1098  {
1099  AMNS->Mtiprime[i][j]=Miprime[j][i];
1100  }
1101  }
1102 }
1103 
1112 static inline bool amns_elt_is_reduced_generic(amns_elt_srcptr a, amns_srcptr AMNS)
1113 {
1114  const uint8_t n = AMNS->n;
1115  uint8_t i;
1116 
1117  for(i=0; i<n; i++)
1118  {
1119  if((a[i] >= AMNS->max_digit_delta) || (a[i] <= AMNS->min_digit_delta))
1120  {
1121  return false;
1122  }
1123  }
1124  return true;
1125 }
1126 
1127 #define TEMPLATE_amns_elt_is_reduced(sl) \
1128  static inline bool \
1129  amns_elt_is_reduced##sl(amns_elt_srcptr a, amns_srcptr AMNS) \
1130  { \
1131  const uint8_t n = sl; \
1132  uint8_t i; \
1133  \
1134  for(i=0; i<n; i++) \
1135  { \
1136  if((a[i] >= AMNS->max_digit_delta) || (a[i] <= AMNS->min_digit_delta)) \
1137  { \
1138  return false; \
1139  } \
1140  } \
1141  return true; \
1142  } \
1143 
1144 TEMPLATE_amns_elt_is_reduced(2)
1145 TEMPLATE_amns_elt_is_reduced(3)
1146 TEMPLATE_amns_elt_is_reduced(4)
1147 TEMPLATE_amns_elt_is_reduced(5)
1148 TEMPLATE_amns_elt_is_reduced(6)
1149 TEMPLATE_amns_elt_is_reduced(7)
1150 TEMPLATE_amns_elt_is_reduced(8)
1151 TEMPLATE_amns_elt_is_reduced(9)
1152 TEMPLATE_amns_elt_is_reduced(10)
1153 TEMPLATE_amns_elt_is_reduced(11)
1154 TEMPLATE_amns_elt_is_reduced(12)
1155 TEMPLATE_amns_elt_is_reduced(13)
1156 TEMPLATE_amns_elt_is_reduced(14)
1157 TEMPLATE_amns_elt_is_reduced(15)
1158 TEMPLATE_amns_elt_is_reduced(16)
1159 TEMPLATE_amns_elt_is_reduced(17)
1160 TEMPLATE_amns_elt_is_reduced(18)
1161 TEMPLATE_amns_elt_is_reduced(19)
1162 TEMPLATE_amns_elt_is_reduced(20)
1163 TEMPLATE_amns_elt_is_reduced(21)
1164 TEMPLATE_amns_elt_is_reduced(22)
1165 TEMPLATE_amns_elt_is_reduced(23)
1166 TEMPLATE_amns_elt_is_reduced(24)
1167 TEMPLATE_amns_elt_is_reduced(25)
1168 
1169 #undef TEMPLATE_amns_elt_is_reduced
1170 
1171 static inline bool amns_elt_is_reduced(amns_elt_srcptr a, amns_srcptr AMNS)
1172 {
1173  return AMNS->amns_elt_is_reduced(a, AMNS);
1174 }
1175 
1183 void amns_elt_copy_ul_2_amns(amns_elt dst, const amns_ulong * a, amns_srcptr AMNS)
1184 {
1185  const uint8_t n = AMNS->n;
1186  uint8_t i;
1187 
1188  for (i=0; i<n; i++)
1189  {
1190  dst[i] = (amns_block)a[i];
1191  }
1192 }
1193 
1194 /************************************INITIALISATION************************************/
1195 
1202 void amns_elt_read_sep(amns_block * x, char * str)
1203 {
1204  uint8_t i=0;
1205  char str1[strlen(str)+1];
1206  strcpy(str1, str);
1207  char delim[] = ", ";
1208  char * token = strtok(str1, delim);
1209 
1210  while(token != NULL)
1211  {
1212 #if MPHELL_USE_AMNS_32 == 1
1213  x[i++] = atoi(token);
1214 #else
1215  x[i++] = atoll(token);
1216 #endif
1217  token = strtok(NULL, delim);
1218  }
1219 }
1220 
1227 void amns_elt_read_sep_ul(amns_ulong * x, char * str)
1228 {
1229  uint8_t i=0;
1230  char str1[strlen(str)+1];
1231  strcpy(str1, str);
1232  char delim[] = ", ";
1233  char * token = strtok(str1, delim);
1234 
1235  while(token != NULL)
1236  {
1237  x[i++] = strtoul(token, NULL, 10);
1238  token = strtok(NULL, delim);
1239  }
1240 }
1241 
1242 void amns_alloc_init_str(amns_ptr * AMNS, char * str, number p)
1243 {
1244  char str1[strlen(str)];
1245  strcpy(str1, str+1); /* Remove the first '[' */
1246  char * str2 = str1;
1247  char delim1[] = ",";
1248  char delim2[] = "]";
1249  char * token;
1250 
1251  uint8_t n, rho, nb_add_max;
1252 
1253  /* Get NB_ADD_MAX */
1254  token = strtok(str2, delim1);
1255  str2+=strlen(token)+2;
1256  nb_add_max = atoi(token);
1257  /* Get Degree */
1258  token = strtok(str2, delim1);
1259  str2+=strlen(token)+2;
1260  n = atoi(token);
1261 
1262  amns_block E[n+1];
1263  amns_block M[n];
1264  amns_ulong Mprime[n];
1265  amns_block P0[n];
1266  amns_block P1[n];
1267  number gamma;
1268 
1269  amns_alloc(AMNS, n, p);
1270  number_init(&gamma, (*AMNS)->p_size);
1271 
1272  /* Get E */
1273  str2 ++; /* Skip the '[' */
1274  token = strtok(str2, delim2);
1275  str2+=strlen(token)+2;
1276  amns_elt_read_sep(E, token);
1277  /* Get rho */
1278  str2++;
1279  token = strtok(str2, delim1);
1280  str2+=strlen(token)+2;
1281  rho = atoi(token);
1282  /* Get gamma */
1283  token = strtok(str2, delim1);
1284  str2+=strlen(token)+2;
1285  number_set_str(gamma, token, 10);
1286  /* Get M */
1287  str2++; /* Skip the '[' */
1288  token = strtok(str2, delim2);
1289  str2+=strlen(token)+2;
1290  amns_elt_read_sep(M, token);
1291  /* Get M' */
1292  str2+=2; /* Skip the '[' */
1293  token = strtok(str2, delim2);
1294  str2+=strlen(token)+2;
1295  amns_elt_read_sep_ul(Mprime, token);
1296  /* Get P0 */
1297  str2+=2; /* Skip the '[' */
1298  token = strtok(str2, delim2);
1299  str2+=strlen(token)+2;
1300  amns_elt_read_sep(P0, token);
1301  /* Get P1 */
1302  str2+=2; /* Skip the '[' */
1303  token = strtok(str2, delim2);
1304  str2+=strlen(token)+2;
1305  amns_elt_read_sep(P1, token);
1306 
1307  amns_init(*AMNS, E, P0, P1, M, Mprime, p, gamma, rho, nb_add_max);
1308  number_free(&gamma);
1309 }
1310 
1316 uint8_t previous_power_2 (uint8_t x)
1317 {
1318  x = x | (x >> 1);
1319  x = x | (x >> 2);
1320  x = x | (x >> 4);
1321  return x - (x >> 1);
1322 }
1323 
1324 void amns_init(amns_ptr AMNS, const amns_block * E, const amns_block * P0, const amns_block *P1, const amns_block *M, const amns_ulong *Mprime, number_srcptr p, number gamma, uint8_t rho, uint8_t nb_add_max)
1325 {
1326  uint8_t i;
1327 
1328  AMNS->amns_block_size = (8*sizeof(amns_block));
1329 
1330  AMNS->max_amns_block = ((amns_ullong)1<<(sizeof(amns_llong)*8-1))-1;
1331 
1332  number_copy(AMNS->p, p);
1333  number_copy(AMNS->gamma, gamma);
1334 
1335  AMNS->gamma_size = number_log2(gamma);
1336 
1337  for (i=0; i<AMNS->n+1; i++)
1338  {
1339  AMNS->E[i] = E[i];
1340  }
1341 
1342  /* Calculate k */
1343  AMNS->k = 0;
1344 
1345  for (i=AMNS->n-1; i >= 0; i--)
1346  {
1347  if(E[i] == 0)
1348  {
1349  AMNS->k++;
1350  }
1351  else
1352  {
1353  break;
1354  }
1355  }
1356  AMNS->k = (AMNS->n-1)-AMNS->k;
1357 
1358  /* If k == 0, define lambda to switch the external reduction procedure */
1359 
1360  AMNS->lambda = 0;
1361  AMNS->lambda_bit = 0;
1362  AMNS->lambda_sign = false;
1363  if(AMNS->k == 0)
1364  {
1365  AMNS->lambda = -E[0];
1366  if(AMNS->lambda > 0)
1367  {
1368  AMNS->lambda_sign = true;
1369  }
1370  if((AMNS->lambda & (AMNS->lambda - 1)) == 0)
1371  {
1372  /* lambda is a power of 2 */
1373  AMNS->lambda_bit = (uint8_t)(log(AMNS->lambda)/log(2));
1374  }
1375  }
1376 
1377  switch(AMNS->n)
1378  {
1379  case 2:
1380  AMNS->amns_elt_add=&amns_elt_add2;
1381  AMNS->amns_elt_sub=&amns_elt_sub2;
1382  AMNS->amns_elt_neg=&amns_elt_neg2;
1383  if(AMNS->lambda_bit == 1)
1384  {
1385  if(AMNS->lambda_sign==true)
1386  {
1387  AMNS->amns_elt_mul=&amns_elt_mul_shift_p2;
1388  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p2;
1389  }
1390  else
1391  {
1392  AMNS->amns_elt_mul=&amns_elt_mul_shift_n2;
1393  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n2;
1394  }
1395  }
1396  else
1397  {
1398  AMNS->amns_elt_mul=&amns_elt_mul2;
1399  AMNS->amns_elt_sqr=&amns_elt_sqr2;
1400  }
1401  AMNS->amns_internal_red=&amns_internal_red2;
1402  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced2;
1403  break;
1404  case 3:
1405  AMNS->amns_elt_add=&amns_elt_add3;
1406  AMNS->amns_elt_sub=&amns_elt_sub3;
1407  AMNS->amns_elt_neg=&amns_elt_neg3;
1408  if(AMNS->lambda_bit == 1)
1409  {
1410  if(AMNS->lambda_sign==true)
1411  {
1412  AMNS->amns_elt_mul=&amns_elt_mul_shift_p3;
1413  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p3;
1414  }
1415  else
1416  {
1417  AMNS->amns_elt_mul=&amns_elt_mul_shift_n3;
1418  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n3;
1419  }
1420  }
1421  else
1422  {
1423  AMNS->amns_elt_mul=&amns_elt_mul3;
1424  AMNS->amns_elt_sqr=&amns_elt_sqr3;
1425  }
1426  AMNS->amns_internal_red=&amns_internal_red3;
1427  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced3;
1428  break;
1429  case 4:
1430  AMNS->amns_elt_add=&amns_elt_add4;
1431  AMNS->amns_elt_sub=&amns_elt_sub4;
1432  AMNS->amns_elt_neg=&amns_elt_neg4;
1433  if(AMNS->lambda_bit == 1)
1434  {
1435  if(AMNS->lambda_sign==true)
1436  {
1437  AMNS->amns_elt_mul=&amns_elt_mul_shift_p4;
1438  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p4;
1439  }
1440  else
1441  {
1442  AMNS->amns_elt_mul=&amns_elt_mul_shift_n4;
1443  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n4;
1444  }
1445  }
1446  else
1447  {
1448  AMNS->amns_elt_mul=&amns_elt_mul4;
1449  AMNS->amns_elt_sqr=&amns_elt_sqr4;
1450  }
1451  AMNS->amns_internal_red=&amns_internal_red4;
1452  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced4;
1453  break;
1454  case 5:
1455  AMNS->amns_elt_add=&amns_elt_add5;
1456  AMNS->amns_elt_sub=&amns_elt_sub5;
1457  AMNS->amns_elt_neg=&amns_elt_neg5;
1458  if(AMNS->lambda_bit == 1)
1459  {
1460  if(AMNS->lambda_sign==true)
1461  {
1462  AMNS->amns_elt_mul=&amns_elt_mul_shift_p5;
1463  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p5;
1464  }
1465  else
1466  {
1467  AMNS->amns_elt_mul=&amns_elt_mul_shift_n5;
1468  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n5;
1469  }
1470  }
1471  else
1472  {
1473  AMNS->amns_elt_mul=&amns_elt_mul5;
1474  AMNS->amns_elt_sqr=&amns_elt_sqr5;
1475  }
1476  AMNS->amns_internal_red=&amns_internal_red5;
1477  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced5;
1478  break;
1479  case 6:
1480  AMNS->amns_elt_add=&amns_elt_add6;
1481  AMNS->amns_elt_sub=&amns_elt_sub6;
1482  AMNS->amns_elt_neg=&amns_elt_neg6;
1483  if(AMNS->lambda_bit == 1)
1484  {
1485  if(AMNS->lambda_sign==true)
1486  {
1487  AMNS->amns_elt_mul=&amns_elt_mul_shift_p6;
1488  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p6;
1489  }
1490  else
1491  {
1492  AMNS->amns_elt_mul=&amns_elt_mul_shift_n6;
1493  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n6;
1494  }
1495  }
1496  else
1497  {
1498  AMNS->amns_elt_mul=&amns_elt_mul6;
1499  AMNS->amns_elt_sqr=&amns_elt_sqr6;
1500  }
1501  AMNS->amns_internal_red=&amns_internal_red6;
1502  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced6;
1503  break;
1504  case 7:
1505  AMNS->amns_elt_add=&amns_elt_add7;
1506  AMNS->amns_elt_sub=&amns_elt_sub7;
1507  AMNS->amns_elt_neg=&amns_elt_neg7;
1508  if(AMNS->lambda_bit == 1)
1509  {
1510  if(AMNS->lambda_sign==true)
1511  {
1512  AMNS->amns_elt_mul=&amns_elt_mul_shift_p7;
1513  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p7;
1514  }
1515  else
1516  {
1517  AMNS->amns_elt_mul=&amns_elt_mul_shift_n7;
1518  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n7;
1519  }
1520  }
1521  else
1522  {
1523  AMNS->amns_elt_mul=&amns_elt_mul7;
1524  AMNS->amns_elt_sqr=&amns_elt_sqr7;
1525  }
1526  AMNS->amns_internal_red=&amns_internal_red7;
1527  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced7;
1528  break;
1529  case 8:
1530  AMNS->amns_elt_add=&amns_elt_add8;
1531  AMNS->amns_elt_sub=&amns_elt_sub8;
1532  AMNS->amns_elt_neg=&amns_elt_neg8;
1533  if(AMNS->lambda_bit == 1)
1534  {
1535  if(AMNS->lambda_sign==true)
1536  {
1537  AMNS->amns_elt_mul=&amns_elt_mul_shift_p8;
1538  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p8;
1539  }
1540  else
1541  {
1542  AMNS->amns_elt_mul=&amns_elt_mul_shift_n8;
1543  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n8;
1544  }
1545  }
1546  else
1547  {
1548  AMNS->amns_elt_mul=&amns_elt_mul8;
1549  AMNS->amns_elt_sqr=&amns_elt_sqr8;
1550  }
1551  AMNS->amns_internal_red=&amns_internal_red8;
1552  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced8;
1553  break;
1554  case 9:
1555  AMNS->amns_elt_add=&amns_elt_add9;
1556  AMNS->amns_elt_sub=&amns_elt_sub9;
1557  AMNS->amns_elt_neg=&amns_elt_neg9;
1558  if(AMNS->lambda_bit == 1)
1559  {
1560  if(AMNS->lambda_sign==true)
1561  {
1562  AMNS->amns_elt_mul=&amns_elt_mul_shift_p9;
1563  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p9;
1564  }
1565  else
1566  {
1567  AMNS->amns_elt_mul=&amns_elt_mul_shift_n9;
1568  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n9;
1569  }
1570  }
1571  else
1572  {
1573  AMNS->amns_elt_mul=&amns_elt_mul9;
1574  AMNS->amns_elt_sqr=&amns_elt_sqr9;
1575  }
1576  AMNS->amns_internal_red=&amns_internal_red9;
1577  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced9;
1578  break;
1579  case 10:
1580  AMNS->amns_elt_add=&amns_elt_add10;
1581  AMNS->amns_elt_sub=&amns_elt_sub10;
1582  AMNS->amns_elt_neg=&amns_elt_neg10;
1583  if(AMNS->lambda_bit == 1)
1584  {
1585  if(AMNS->lambda_sign==true)
1586  {
1587  AMNS->amns_elt_mul=&amns_elt_mul_shift_p10;
1588  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p10;
1589  }
1590  else
1591  {
1592  AMNS->amns_elt_mul=&amns_elt_mul_shift_n10;
1593  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n10;
1594  }
1595  }
1596  else
1597  {
1598  AMNS->amns_elt_mul=&amns_elt_mul10;
1599  AMNS->amns_elt_sqr=&amns_elt_sqr10;
1600  }
1601  AMNS->amns_internal_red=&amns_internal_red10;
1602  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced10;
1603  break;
1604  case 11:
1605  AMNS->amns_elt_add=&amns_elt_add11;
1606  AMNS->amns_elt_sub=&amns_elt_sub11;
1607  AMNS->amns_elt_neg=&amns_elt_neg11;
1608  if(AMNS->lambda_bit == 1)
1609  {
1610  if(AMNS->lambda_sign==true)
1611  {
1612  AMNS->amns_elt_mul=&amns_elt_mul_shift_p11;
1613  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p11;
1614  }
1615  else
1616  {
1617  AMNS->amns_elt_mul=&amns_elt_mul_shift_n11;
1618  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n11;
1619  }
1620  }
1621  else
1622  {
1623  AMNS->amns_elt_mul=&amns_elt_mul11;
1624  AMNS->amns_elt_sqr=&amns_elt_sqr11;
1625  }
1626  AMNS->amns_internal_red=&amns_internal_red11;
1627  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced11;
1628  break;
1629  case 12:
1630  AMNS->amns_elt_add=&amns_elt_add12;
1631  AMNS->amns_elt_sub=&amns_elt_sub12;
1632  AMNS->amns_elt_neg=&amns_elt_neg12;
1633  if(AMNS->lambda_bit == 1)
1634  {
1635  if(AMNS->lambda_sign==true)
1636  {
1637  AMNS->amns_elt_mul=&amns_elt_mul_shift_p12;
1638  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p12;
1639  }
1640  else
1641  {
1642  AMNS->amns_elt_mul=&amns_elt_mul_shift_n12;
1643  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n12;
1644  }
1645  }
1646  else
1647  {
1648  AMNS->amns_elt_mul=&amns_elt_mul12;
1649  AMNS->amns_elt_sqr=&amns_elt_sqr12;
1650  }
1651  AMNS->amns_internal_red=&amns_internal_red12;
1652  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced12;
1653  break;
1654  case 13:
1655  AMNS->amns_elt_add=&amns_elt_add13;
1656  AMNS->amns_elt_sub=&amns_elt_sub13;
1657  AMNS->amns_elt_neg=&amns_elt_neg13;
1658  if(AMNS->lambda_bit == 1)
1659  {
1660  if(AMNS->lambda_sign==true)
1661  {
1662  AMNS->amns_elt_mul=&amns_elt_mul_shift_p13;
1663  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p13;
1664  }
1665  else
1666  {
1667  AMNS->amns_elt_mul=&amns_elt_mul_shift_n13;
1668  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n13;
1669  }
1670  }
1671  else
1672  {
1673  AMNS->amns_elt_mul=&amns_elt_mul13;
1674  AMNS->amns_elt_sqr=&amns_elt_sqr13;
1675  }
1676  AMNS->amns_internal_red=&amns_internal_red13;
1677  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced13;
1678  break;
1679  case 14:
1680  AMNS->amns_elt_add=&amns_elt_add14;
1681  AMNS->amns_elt_sub=&amns_elt_sub14;
1682  AMNS->amns_elt_neg=&amns_elt_neg14;
1683  if(AMNS->lambda_bit == 1)
1684  {
1685  if(AMNS->lambda_sign==true)
1686  {
1687  AMNS->amns_elt_mul=&amns_elt_mul_shift_p14;
1688  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p14;
1689  }
1690  else
1691  {
1692  AMNS->amns_elt_mul=&amns_elt_mul_shift_n14;
1693  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n14;
1694  }
1695  }
1696  else
1697  {
1698  AMNS->amns_elt_mul=&amns_elt_mul14;
1699  AMNS->amns_elt_sqr=&amns_elt_sqr14;
1700  }
1701  AMNS->amns_internal_red=&amns_internal_red14;
1702  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced14;
1703  break;
1704  case 15:
1705  AMNS->amns_elt_add=&amns_elt_add15;
1706  AMNS->amns_elt_sub=&amns_elt_sub15;
1707  AMNS->amns_elt_neg=&amns_elt_neg15;
1708  if(AMNS->lambda_bit == 1)
1709  {
1710  if(AMNS->lambda_sign==true)
1711  {
1712  AMNS->amns_elt_mul=&amns_elt_mul_shift_p15;
1713  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p15;
1714  }
1715  else
1716  {
1717  AMNS->amns_elt_mul=&amns_elt_mul_shift_n15;
1718  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n15;
1719  }
1720  }
1721  else
1722  {
1723  AMNS->amns_elt_mul=&amns_elt_mul15;
1724  AMNS->amns_elt_sqr=&amns_elt_sqr15;
1725  }
1726  AMNS->amns_internal_red=&amns_internal_red15;
1727  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced15;
1728  break;
1729  case 16:
1730  AMNS->amns_elt_add=&amns_elt_add16;
1731  AMNS->amns_elt_sub=&amns_elt_sub16;
1732  AMNS->amns_elt_neg=&amns_elt_neg16;
1733  if(AMNS->lambda_bit == 1)
1734  {
1735  if(AMNS->lambda_sign==true)
1736  {
1737  AMNS->amns_elt_mul=&amns_elt_mul_shift_p16;
1738  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p16;
1739  }
1740  else
1741  {
1742  AMNS->amns_elt_mul=&amns_elt_mul_shift_n16;
1743  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n16;
1744  }
1745  }
1746  else
1747  {
1748  AMNS->amns_elt_mul=&amns_elt_mul16;
1749  AMNS->amns_elt_sqr=&amns_elt_sqr16;
1750  }
1751  AMNS->amns_internal_red=&amns_internal_red16;
1752  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced16;
1753  break;
1754  case 17:
1755  AMNS->amns_elt_add=&amns_elt_add17;
1756  AMNS->amns_elt_sub=&amns_elt_sub17;
1757  AMNS->amns_elt_neg=&amns_elt_neg17;
1758  if(AMNS->lambda_bit == 1)
1759  {
1760  if(AMNS->lambda_sign==true)
1761  {
1762  AMNS->amns_elt_mul=&amns_elt_mul_shift_p17;
1763  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p17;
1764  }
1765  else
1766  {
1767  AMNS->amns_elt_mul=&amns_elt_mul_shift_n17;
1768  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n17;
1769  }
1770  }
1771  else
1772  {
1773  AMNS->amns_elt_mul=&amns_elt_mul17;
1774  AMNS->amns_elt_sqr=&amns_elt_sqr17;
1775  }
1776  AMNS->amns_internal_red=&amns_internal_red17;
1777  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced17;
1778  break;
1779  case 18:
1780  AMNS->amns_elt_add=&amns_elt_add18;
1781  AMNS->amns_elt_sub=&amns_elt_sub18;
1782  AMNS->amns_elt_neg=&amns_elt_neg18;
1783  if(AMNS->lambda_bit == 1)
1784  {
1785  if(AMNS->lambda_sign==true)
1786  {
1787  AMNS->amns_elt_mul=&amns_elt_mul_shift_p18;
1788  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p18;
1789  }
1790  else
1791  {
1792  AMNS->amns_elt_mul=&amns_elt_mul_shift_n18;
1793  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n18;
1794  }
1795  }
1796  else
1797  {
1798  AMNS->amns_elt_mul=&amns_elt_mul18;
1799  AMNS->amns_elt_sqr=&amns_elt_sqr18;
1800  }
1801  AMNS->amns_internal_red=&amns_internal_red18;
1802  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced18;
1803  break;
1804  case 19:
1805  AMNS->amns_elt_add=&amns_elt_add19;
1806  AMNS->amns_elt_sub=&amns_elt_sub19;
1807  AMNS->amns_elt_neg=&amns_elt_neg19;
1808  if(AMNS->lambda_bit == 1)
1809  {
1810  if(AMNS->lambda_sign==true)
1811  {
1812  AMNS->amns_elt_mul=&amns_elt_mul_shift_p19;
1813  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p19;
1814  }
1815  else
1816  {
1817  AMNS->amns_elt_mul=&amns_elt_mul_shift_n19;
1818  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n19;
1819  }
1820  }
1821  else
1822  {
1823  AMNS->amns_elt_mul=&amns_elt_mul19;
1824  AMNS->amns_elt_sqr=&amns_elt_sqr19;
1825  }
1826  AMNS->amns_internal_red=&amns_internal_red19;
1827  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced19;
1828  break;
1829  case 20:
1830  AMNS->amns_elt_add=&amns_elt_add20;
1831  AMNS->amns_elt_sub=&amns_elt_sub20;
1832  AMNS->amns_elt_neg=&amns_elt_neg20;
1833  if(AMNS->lambda_bit == 1)
1834  {
1835  if(AMNS->lambda_sign==true)
1836  {
1837  AMNS->amns_elt_mul=&amns_elt_mul_shift_p20;
1838  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p20;
1839  }
1840  else
1841  {
1842  AMNS->amns_elt_mul=&amns_elt_mul_shift_n20;
1843  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n20;
1844  }
1845  }
1846  else
1847  {
1848  AMNS->amns_elt_mul=&amns_elt_mul20;
1849  AMNS->amns_elt_sqr=&amns_elt_sqr20;
1850  }
1851  AMNS->amns_internal_red=&amns_internal_red20;
1852  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced20;
1853  break;
1854  case 21:
1855  AMNS->amns_elt_add=&amns_elt_add21;
1856  AMNS->amns_elt_sub=&amns_elt_sub21;
1857  AMNS->amns_elt_neg=&amns_elt_neg21;
1858  if(AMNS->lambda_bit == 1)
1859  {
1860  if(AMNS->lambda_sign==true)
1861  {
1862  AMNS->amns_elt_mul=&amns_elt_mul_shift_p21;
1863  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p21;
1864  }
1865  else
1866  {
1867  AMNS->amns_elt_mul=&amns_elt_mul_shift_n21;
1868  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n21;
1869  }
1870  }
1871  else
1872  {
1873  AMNS->amns_elt_mul=&amns_elt_mul21;
1874  AMNS->amns_elt_sqr=&amns_elt_sqr21;
1875  }
1876  AMNS->amns_internal_red=&amns_internal_red21;
1877  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced21;
1878  break;
1879  case 22:
1880  AMNS->amns_elt_add=&amns_elt_add22;
1881  AMNS->amns_elt_sub=&amns_elt_sub22;
1882  AMNS->amns_elt_neg=&amns_elt_neg22;
1883  if(AMNS->lambda_bit == 1)
1884  {
1885  if(AMNS->lambda_sign==true)
1886  {
1887  AMNS->amns_elt_mul=&amns_elt_mul_shift_p22;
1888  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p22;
1889  }
1890  else
1891  {
1892  AMNS->amns_elt_mul=&amns_elt_mul_shift_n22;
1893  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n22;
1894  }
1895  }
1896  else
1897  {
1898  AMNS->amns_elt_mul=&amns_elt_mul22;
1899  AMNS->amns_elt_sqr=&amns_elt_sqr22;
1900  }
1901  AMNS->amns_internal_red=&amns_internal_red22;
1902  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced22;
1903  break;
1904  case 23:
1905  AMNS->amns_elt_add=&amns_elt_add23;
1906  AMNS->amns_elt_sub=&amns_elt_sub23;
1907  AMNS->amns_elt_neg=&amns_elt_neg23;
1908  if(AMNS->lambda_bit == 1)
1909  {
1910  if(AMNS->lambda_sign==true)
1911  {
1912  AMNS->amns_elt_mul=&amns_elt_mul_shift_p23;
1913  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p23;
1914  }
1915  else
1916  {
1917  AMNS->amns_elt_mul=&amns_elt_mul_shift_n23;
1918  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n23;
1919  }
1920  }
1921  else
1922  {
1923  AMNS->amns_elt_mul=&amns_elt_mul23;
1924  AMNS->amns_elt_sqr=&amns_elt_sqr23;
1925  }
1926  AMNS->amns_internal_red=&amns_internal_red23;
1927  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced23;
1928  break;
1929  case 24:
1930  AMNS->amns_elt_add=&amns_elt_add24;
1931  AMNS->amns_elt_sub=&amns_elt_sub24;
1932  AMNS->amns_elt_neg=&amns_elt_neg24;
1933  if(AMNS->lambda_bit == 1)
1934  {
1935  if(AMNS->lambda_sign==true)
1936  {
1937  AMNS->amns_elt_mul=&amns_elt_mul_shift_p24;
1938  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p24;
1939  }
1940  else
1941  {
1942  AMNS->amns_elt_mul=&amns_elt_mul_shift_n24;
1943  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n24;
1944  }
1945  }
1946  else
1947  {
1948  AMNS->amns_elt_mul=&amns_elt_mul24;
1949  AMNS->amns_elt_sqr=&amns_elt_sqr24;
1950  }
1951  AMNS->amns_internal_red=&amns_internal_red24;
1952  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced24;
1953  break;
1954  case 25:
1955  AMNS->amns_elt_add=&amns_elt_add25;
1956  AMNS->amns_elt_sub=&amns_elt_sub25;
1957  AMNS->amns_elt_neg=&amns_elt_neg25;
1958  if(AMNS->lambda_bit == 1)
1959  {
1960  if(AMNS->lambda_sign==true)
1961  {
1962  AMNS->amns_elt_mul=&amns_elt_mul_shift_p25;
1963  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_p25;
1964  }
1965  else
1966  {
1967  AMNS->amns_elt_mul=&amns_elt_mul_shift_n25;
1968  AMNS->amns_elt_sqr=&amns_elt_sqr_shift_n25;
1969  }
1970  }
1971  else
1972  {
1973  AMNS->amns_elt_mul=&amns_elt_mul25;
1974  AMNS->amns_elt_sqr=&amns_elt_sqr25;
1975  }
1976  AMNS->amns_internal_red=&amns_internal_red25;
1977  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced25;
1978  break;
1979  default:
1980  printf("Set up a default for templates ptr\n");
1981  AMNS->amns_elt_add=&amns_elt_add_generic;
1982  AMNS->amns_elt_sub=&amns_elt_sub_generic;
1983  AMNS->amns_elt_neg=&amns_elt_neg_generic;
1984  AMNS->amns_elt_mul=&amns_elt_mul_generic;
1985  AMNS->amns_elt_sqr=&amns_elt_sqr_generic;
1986  AMNS->amns_internal_red=&amns_internal_red_generic;
1987  AMNS->amns_elt_is_reduced=&amns_elt_is_reduced_generic;
1988  }
1989 
1990  /* Copy rho */
1991  AMNS->rho = rho;
1992 
1993  /* Copy nb_add_max */
1994  AMNS->nb_add_max = nb_add_max;
1995 
1996  /* For conversion AMNS -> Binary */
1997  amns_calcule_gi(AMNS);
1998 
1999  AMNS->max_digit = ((amns_block)1<<rho);
2000  AMNS->min_digit = -AMNS->max_digit;
2001 
2002  /* Calculate the power of 2 under nb_add_max */
2003  uint8_t d = previous_power_2(nb_add_max+1);
2004 
2005  if(d>1)
2006  {
2007  AMNS->max_digit_delta = AMNS->max_digit * d;
2008  AMNS->min_digit_delta = AMNS->min_digit * d;
2009  }
2010  else
2011  {
2012  AMNS->max_digit_delta = AMNS->max_digit;
2013  AMNS->min_digit_delta = AMNS->min_digit;
2014  }
2015 
2016  /* For internal reduction */
2017 
2018  amns_elt Mprime_signed;
2019  amns_elt_alloc(&Mprime_signed, AMNS);
2020  amns_elt_copy_ul_2_amns(Mprime_signed, Mprime, AMNS);
2021 
2022  amns_calcule_Mi(AMNS, M);
2023  amns_calcule_Miprime(AMNS, Mprime_signed);
2024  amns_elt_free(&Mprime_signed);
2025 
2026  /* For conversion Binary -> AMNS */
2027  amns_calcule_Ti(AMNS, P0, P1);
2028 
2029 #if MPHELL_USE_DEBUG == 1
2030  AMNS->nb_add=0;
2031  AMNS->nb_sub=0;
2032  AMNS->nb_mul=0;
2033  AMNS->nb_add_red=0;
2034  AMNS->nb_sub_red=0;
2035  AMNS->nb_mul_red=0;
2036 #endif
2037 }
2038 
2039 void amns_init_stat(amns_ptr AMNS)
2040 {
2041 #if MPHELL_USE_DEBUG == 1
2042  AMNS->nb_add=0;
2043  AMNS->nb_sub=0;
2044  AMNS->nb_mul=0;
2045  AMNS->nb_add_red=0;
2046  AMNS->nb_sub_red=0;
2047  AMNS->nb_mul_red=0;
2048 #endif
2049 }
2050 
2051 /******************************************IO******************************************/
2052 
2053 void amns_elt_write(amns_block * x, uint8_t size, char * str)
2054 {
2055  uint8_t i;
2056  int s = 0;
2057  char * ptr = str;
2058  for(i=0; i<size; i++)
2059  {
2060 #if MPHELL_USE_AMNS_32 == 1
2061  s = sprintf(ptr, "%d\t", x[i]);
2062 #else
2063  s = sprintf(ptr, "%ld\t", x[i]);
2064 #endif
2065  ptr+=s;
2066  }
2067 }
2068 
2069 void amns_elt_read(amns_block * x, char * str)
2070 {
2071  uint8_t i=0;
2072  char str1[strlen(str)+1];
2073  strcpy(str1, str);
2074  char delim[] = "\t";
2075  char * token = strtok(str1, delim);
2076 
2077  while(token != NULL)
2078  {
2079 #if MPHELL_USE_AMNS_32 == 1
2080  x[i++] = atoi(token);
2081 #else
2082  x[i++] = atoll(token);
2083 #endif
2084  token = strtok(NULL, delim);
2085  }
2086 }
2087 
2088 void amns_elt_read_ul(amns_ulong * x, char * str)
2089 {
2090  uint8_t i=0;
2091  char str1[strlen(str)+1];
2092  strcpy(str1, str);
2093  char delim[] = "\t";
2094  char * token = strtok(str1, delim);
2095 
2096  while(token != NULL)
2097  {
2098  x[i++] = strtoul(token, NULL, 10);
2099  token = strtok(NULL, delim);
2100  }
2101 }
2102 
2103 void amns_elt_set_zero(amns_elt_ptr dst, amns_srcptr AMNS)
2104 {
2105  const uint8_t n = AMNS->n;
2106  uint8_t i;
2107  for (i=0; i<n; i++)
2108  {
2109  dst[i]=0;
2110  }
2111 }
2112 
2113 
2114 /**************************************CONVERSION**************************************/
2115 
2124 void amns_mul_scalar_llong(amns_llong * dst, amns_elt_srcptr a, amns_ulong b, amns_srcptr AMNS)
2125 {
2126  const uint8_t n = AMNS->n;
2127  uint8_t i;
2128 
2129  for(i=0; i<n; i++)
2130  {
2131  dst[i]=(amns_llong)a[i]*b;
2132  }
2133 }
2134 
2143 void amns_add_llong(amns_llong * dst, amns_llong * a, amns_llong * b, amns_srcptr AMNS)
2144 {
2145  const uint8_t n = AMNS->n;
2146  uint8_t i;
2147 
2148  for(i=0; i<n; i++)
2149  {
2150  dst[i]=a[i]+b[i];
2151  }
2152 }
2153 
2154 void binary_to_amns(number_srcptr a, amns_elt_ptr dst, amns_srcptr AMNS)
2155 {
2156  const uint8_t n = AMNS->n;
2157  number q;
2158  number_init(&q, bits_to_nblock(AMNS->p_size));
2159 
2160  amns_llong tmp[n];
2161  amns_llong v[n];
2162  memset(v, 0, n*sizeof(amns_llong));
2163 
2164  uint8_t i = 0;
2165  block res[n];
2166  memset(res, 0, n*sizeof(block));
2167  i=0;
2168 
2169  /* d = 2^rho */
2170  block d = 1UL << AMNS->rho;
2171  number_copy(q, a);
2172  while(number_isdiff_ui(q, 0))
2173  {
2174  number_divmod_ui(q, res+i, q, d);
2175  i++;
2176  }
2177 
2178  for(i=0; i < n; i++)
2179  {
2180  amns_mul_scalar_llong(tmp, AMNS->Ti[i], res[i], AMNS);
2181  amns_add_llong(v, v, tmp, AMNS);
2182  }
2183 
2184  amns_internal_red(dst, v, AMNS);
2185 
2186  number_free(&q);
2187 }
2188 
2189 void binary_ui_to_amns(block a, amns_elt_ptr dst, amns_srcptr AMNS)
2190 {
2191  const uint8_t n = AMNS->n;
2192 
2193  amns_llong tmp[n];
2194  amns_llong v[n];
2195  memset(v, 0, n*sizeof(amns_llong));
2196 
2197  uint8_t i = 0;
2198  block res[n];
2199  memset(res, 0, n*sizeof(block));
2200  i=0;
2201 
2202  /* d = 2^rho */
2203  block d = 1UL << AMNS->rho;
2204  block b = a;
2205  block q;
2206  while(b != 0)
2207  {
2208  q=(b/d);
2209  res[i]=b-(q*d);
2210  b=q;
2211  i++;
2212  }
2213 
2214  for(i=0; i < n; i++)
2215  {
2216  amns_mul_scalar_llong(tmp, AMNS->Ti[i], res[i], AMNS);
2217  amns_add_llong(v, v, tmp, AMNS);
2218  }
2219 
2220  amns_internal_red(dst, v, AMNS);
2221 }
2222 
2223 void amns_to_binary(const amns_elt_srcptr a, number_ptr dst, amns_srcptr AMNS)
2224 {
2225  const uint8_t n = AMNS->n;
2226  uint8_t i;
2227 
2228  amns_elt tmp;
2229  amns_elt_get_pool_elt(&tmp, AMNS, STACK_1);
2230 
2231  amns_llong v[n];
2232 
2233  for(i=0; i<n; i++)
2234  {
2235  v[i] = (amns_llong) a[i];
2236  }
2237 
2238  /* To go out from the Montgomery domain */
2239  amns_internal_red(tmp, v, AMNS);
2240 
2241  number_set_ui(dst, 0);
2242  for (i=0; i<n; i++)
2243  {
2244  if(tmp[i]>=0)
2245  {
2246  number_addmul_ui(dst, AMNS->gi[i], (block)tmp[i]);
2247  }
2248  else
2249  {
2250  number_submul_ui(dst, AMNS->gi[i], (block)(-tmp[i]));
2251  }
2252  }
2253  number_mod(dst, dst, AMNS->p);
2254 
2255  amns_elt_relax_pool_elt(&tmp, AMNS, STACK_1);
2256 }
2257 
2258 
2259 /***************************************COMPARISON**************************************/
2260 
2261 bool amns_elt_is_zero(amns_elt_srcptr src, amns_srcptr AMNS)
2262 {
2263  number n1;
2264  number_tmp_alloc(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2265  amns_to_binary(src, n1, AMNS);
2266  int8_t res = number_isequal_ui(n1, 0);
2267  number_tmp_free(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2268  return res;
2269 }
2270 
2271 bool amns_elt_isequal(amns_elt_srcptr src1, amns_elt_srcptr src2, amns_srcptr AMNS)
2272 {
2273  number n1, n2;
2274  number_tmp_alloc(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2275  number_tmp_alloc(&n2, bits_to_nblock(AMNS->p_size), STACK_1);
2276  amns_to_binary(src1, n1, AMNS);
2277  amns_to_binary(src2, n2, AMNS);
2278  int8_t res = number_isequal(n1, n2);
2279  number_tmp_free(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2280  number_tmp_free(&n2, bits_to_nblock(AMNS->p_size), STACK_1);
2281  return res;
2282 }
2283 
2284 int8_t amns_elt_cmp(amns_elt_srcptr src1, amns_elt_srcptr src2, amns_srcptr AMNS)
2285 {
2286  number n1, n2;
2287  number_tmp_alloc(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2288  number_tmp_alloc(&n2, bits_to_nblock(AMNS->p_size), STACK_1);
2289  amns_to_binary(src1, n1, AMNS);
2290  amns_to_binary(src2, n2, AMNS);
2291  int8_t res = number_cmp(n1, n2);
2292  number_tmp_free(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2293  number_tmp_free(&n2, bits_to_nblock(AMNS->p_size), STACK_1);
2294  return res;
2295 }
2296 
2297 int8_t amns_elt_cmp_ui(amns_elt_srcptr src1, block src2, amns_srcptr AMNS)
2298 {
2299  number n1;
2300  number_tmp_alloc(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2301  amns_to_binary(src1, n1, AMNS);
2302  int8_t res = number_cmp_ui(n1, src2);
2303  number_tmp_free(&n1, bits_to_nblock(AMNS->p_size), STACK_1);
2304  return res;
2305 }
2306 
2307 
2308 /***************************************ARITHMETIC**************************************/
2309 
2310 void amns_elt_copy(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
2311 {
2312  const uint8_t n = AMNS->n;
2313  uint8_t i;
2314 
2315  for (i=0; i<n; i++)
2316  {
2317  dst[i] = a[i];
2318  }
2319 }
2320 
2329 void amns_elt_add_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2330 {
2331 #if MPHELL_USE_DEBUG == 1
2332  ((amns_ptr)AMNS)->nb_add++;
2333 #endif
2334  /* Polynomial Addition */
2335  const uint8_t n = AMNS->n;
2336  uint8_t i;
2337 
2338  for(i=0; i<n; i++)
2339  {
2340  dst[i]=a[i]+b[i];
2341  }
2342 
2343  /* Internal reduction (coeffs) */
2344 
2345  if(!amns_elt_is_reduced(dst, AMNS))
2346  {
2347 #if MPHELL_USE_DEBUG == 1
2348  ((amns_ptr)AMNS)->nb_add_red++;
2349 #endif
2350  amns_internal_red_exact(dst, AMNS);
2351  }
2352 }
2353 
2354 void amns_elt_add(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2355 {
2356  AMNS->amns_elt_add(dst, a, b, AMNS);
2357 }
2358 
2359 #define TEMPLATE_amns_elt_add(sl) \
2360  void \
2361  amns_elt_add##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS) \
2362  { \
2363  /* Polynomial Addition */ \
2364  const uint8_t n = sl; \
2365  uint8_t i; \
2366  \
2367  PRAGMA_UNROLL \
2368  for(i=0; i<n; i++) \
2369  { \
2370  dst[i]=a[i]+b[i]; \
2371  } \
2372  \
2373  /* Internal reduction (coeffs) */ \
2374  \
2375  if(!amns_elt_is_reduced(dst, AMNS)) \
2376  { \
2377  amns_internal_red_exact(dst, AMNS); \
2378  } \
2379  } \
2380 
2381 TEMPLATE_amns_elt_add(2)
2382 TEMPLATE_amns_elt_add(3)
2383 TEMPLATE_amns_elt_add(4)
2384 TEMPLATE_amns_elt_add(5)
2385 TEMPLATE_amns_elt_add(6)
2386 TEMPLATE_amns_elt_add(7)
2387 TEMPLATE_amns_elt_add(8)
2388 TEMPLATE_amns_elt_add(9)
2389 TEMPLATE_amns_elt_add(10)
2390 TEMPLATE_amns_elt_add(11)
2391 TEMPLATE_amns_elt_add(12)
2392 TEMPLATE_amns_elt_add(13)
2393 TEMPLATE_amns_elt_add(14)
2394 TEMPLATE_amns_elt_add(15)
2395 TEMPLATE_amns_elt_add(16)
2396 TEMPLATE_amns_elt_add(17)
2397 TEMPLATE_amns_elt_add(18)
2398 TEMPLATE_amns_elt_add(19)
2399 TEMPLATE_amns_elt_add(20)
2400 TEMPLATE_amns_elt_add(21)
2401 TEMPLATE_amns_elt_add(22)
2402 TEMPLATE_amns_elt_add(23)
2403 TEMPLATE_amns_elt_add(24)
2404 TEMPLATE_amns_elt_add(25)
2405 
2406 #undef TEMPLATE_amns_elt_add
2407 
2415 void amns_elt_neg_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
2416 {
2417  /* Polynomial Negation */
2418  const uint8_t n = AMNS->n;
2419  uint8_t i;
2420 
2421  for(i=0; i<n; i++)
2422  {
2423  dst[i]=-a[i];
2424  }
2425 }
2426 
2427 void amns_elt_neg(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
2428 {
2429  AMNS->amns_elt_neg(dst, a, AMNS);
2430 }
2431 
2432 #define TEMPLATE_amns_elt_neg(sl) \
2433  void \
2434  amns_elt_neg##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS) \
2435  { \
2436  /* Polynomial Negation */ \
2437  const uint8_t n = sl; \
2438  uint8_t i; \
2439  \
2440  PRAGMA_UNROLL \
2441  for(i=0; i<n; i++) \
2442  { \
2443  dst[i]=-a[i]; \
2444  } \
2445  } \
2446 
2447 TEMPLATE_amns_elt_neg(2)
2448 TEMPLATE_amns_elt_neg(3)
2449 TEMPLATE_amns_elt_neg(4)
2450 TEMPLATE_amns_elt_neg(5)
2451 TEMPLATE_amns_elt_neg(6)
2452 TEMPLATE_amns_elt_neg(7)
2453 TEMPLATE_amns_elt_neg(8)
2454 TEMPLATE_amns_elt_neg(9)
2455 TEMPLATE_amns_elt_neg(10)
2456 TEMPLATE_amns_elt_neg(11)
2457 TEMPLATE_amns_elt_neg(12)
2458 TEMPLATE_amns_elt_neg(13)
2459 TEMPLATE_amns_elt_neg(14)
2460 TEMPLATE_amns_elt_neg(15)
2461 TEMPLATE_amns_elt_neg(16)
2462 TEMPLATE_amns_elt_neg(17)
2463 TEMPLATE_amns_elt_neg(18)
2464 TEMPLATE_amns_elt_neg(19)
2465 TEMPLATE_amns_elt_neg(20)
2466 TEMPLATE_amns_elt_neg(21)
2467 TEMPLATE_amns_elt_neg(22)
2468 TEMPLATE_amns_elt_neg(23)
2469 TEMPLATE_amns_elt_neg(24)
2470 TEMPLATE_amns_elt_neg(25)
2471 
2472 #undef TEMPLATE_amns_elt_neg
2473 
2482 void amns_elt_sub_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2483 {
2484 #if MPHELL_USE_DEBUG == 1
2485  ((amns_ptr)AMNS)->nb_sub++;
2486 #endif
2487  /* Polynomial Substraction */
2488  const uint8_t n = AMNS->n;
2489  uint8_t i;
2490 
2491  for(i=0; i<n; i++)
2492  {
2493  dst[i]=a[i]-b[i];
2494  }
2495 
2496  /* Internal reduction (coeffs) */
2497 
2498  if(!amns_elt_is_reduced(dst, AMNS))
2499  {
2500 #if MPHELL_USE_DEBUG == 1
2501  ((amns_ptr)AMNS)->nb_sub_red++;
2502 #endif
2503  amns_internal_red_exact(dst, AMNS);
2504  }
2505 }
2506 
2507 void amns_elt_sub(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2508 {
2509  AMNS->amns_elt_sub(dst, a, b, AMNS);
2510 }
2511 
2512 #define TEMPLATE_amns_elt_sub(sl) \
2513  void \
2514  amns_elt_sub##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS) \
2515  { \
2516  /* Polynomial Substraction */ \
2517  const uint8_t n = sl; \
2518  uint8_t i; \
2519  \
2520  PRAGMA_UNROLL \
2521  for(i=0; i<n; i++) \
2522  { \
2523  dst[i]=a[i]-b[i]; \
2524  } \
2525  \
2526  /* Internal reduction (coeffs) */ \
2527  \
2528  if(!amns_elt_is_reduced(dst, AMNS)) \
2529  { \
2530  amns_internal_red_exact(dst, AMNS); \
2531  } \
2532  } \
2533 
2534 TEMPLATE_amns_elt_sub(2)
2535 TEMPLATE_amns_elt_sub(3)
2536 TEMPLATE_amns_elt_sub(4)
2537 TEMPLATE_amns_elt_sub(5)
2538 TEMPLATE_amns_elt_sub(6)
2539 TEMPLATE_amns_elt_sub(7)
2540 TEMPLATE_amns_elt_sub(8)
2541 TEMPLATE_amns_elt_sub(9)
2542 TEMPLATE_amns_elt_sub(10)
2543 TEMPLATE_amns_elt_sub(11)
2544 TEMPLATE_amns_elt_sub(12)
2545 TEMPLATE_amns_elt_sub(13)
2546 TEMPLATE_amns_elt_sub(14)
2547 TEMPLATE_amns_elt_sub(15)
2548 TEMPLATE_amns_elt_sub(16)
2549 TEMPLATE_amns_elt_sub(17)
2550 TEMPLATE_amns_elt_sub(18)
2551 TEMPLATE_amns_elt_sub(19)
2552 TEMPLATE_amns_elt_sub(20)
2553 TEMPLATE_amns_elt_sub(21)
2554 TEMPLATE_amns_elt_sub(22)
2555 TEMPLATE_amns_elt_sub(23)
2556 TEMPLATE_amns_elt_sub(24)
2557 TEMPLATE_amns_elt_sub(25)
2558 
2559 
2560 #undef TEMPLATE_amns_elt_sub
2561 
2570 void amns_elt_mul_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2571 {
2572 #if MPHELL_USE_DEBUG == 1
2573  ((amns_ptr)AMNS)->nb_mul++;
2574 #endif
2575  const uint8_t n = AMNS->n;
2576  int8_t i, j;
2577  amns_llong tm[n];
2578 
2579  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n");
2580  MPHELL_ASSERT(amns_calculate_max_coeff(b, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(b) > rho_max\n");
2581 
2582  /* Polynomial Multiplication */
2583 
2584  if(AMNS->lambda_bit == 1)
2585  {
2586  for(i=0; i<n-1; i++)
2587  {
2588  tm[i]=((amns_llong)a[i+1]*b[n-1]);
2589  for (j=i+2; j<n; j++)
2590  {
2591  tm[i]+=((amns_llong)a[j]*b[(n+i)-j]);
2592  }
2593  tm[i] <<= AMNS->lambda_bit;
2594  for (j=0; j<=i; j++)
2595  {
2596  tm[i]+=(amns_llong)a[j]*b[i-j];
2597  }
2598  }
2599  tm[n-1]=(amns_llong)a[0]*b[n-1];
2600  for (j=1; j<n; j++)
2601  {
2602  tm[n-1]+=(amns_llong)a[j]*b[(n-1)-j];
2603  }
2604  }
2605  else
2606  {
2607  for(i=0; i<n-1; i++)
2608  {
2609  tm[i]=((amns_llong)a[i+1]*b[n-1]);
2610  for (j=i+2; j<n; j++)
2611  {
2612  tm[i]+=((amns_llong)a[j]*b[(n+i)-j]);
2613  }
2614  tm[i] *= AMNS->lambda;
2615  for (j=0; j<=i; j++)
2616  {
2617  tm[i]+=(amns_llong)a[j]*b[i-j];
2618  }
2619  }
2620  tm[n-1]=(amns_llong)a[0]*b[n-1];
2621  for (j=1; j<n; j++)
2622  {
2623  tm[n-1]+=(amns_llong)a[j]*b[(n-1)-j];
2624  }
2625  }
2626 
2627  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */
2628 
2629 #if MPHELL_USE_DEBUG == 1
2630  ((amns_ptr)AMNS)->nb_mul_red++;
2631 #endif
2632 
2633  amns_internal_red(dst, tm, AMNS);
2634 }
2635 
2636 #define TEMPLATE_amns_elt_mul(sl) \
2637  void \
2638  amns_elt_mul##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS) \
2639  { \
2640  const uint8_t n = sl; \
2641  uint8_t i, j; \
2642  amns_llong tm[n]; \
2643  \
2644  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
2645  MPHELL_ASSERT(amns_calculate_max_coeff(b, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(b) > rho_max\n"); \
2646  \
2647  /* Polynomial Multiplication */ \
2648  \
2649  PRAGMA_UNROLL \
2650  for(i=0; i<n-1; i++) \
2651  { \
2652  tm[i]=((amns_llong)a[i+1]*b[n-1]); \
2653  PRAGMA_UNROLL \
2654  for (j=i+2; j<n; j++) \
2655  { \
2656  tm[i]+=((amns_llong)a[j]*b[(n+i)-j]); \
2657  } \
2658  tm[i] *= AMNS->lambda; \
2659  PRAGMA_UNROLL \
2660  for (j=0; j<=i; j++) \
2661  { \
2662  tm[i]+=(amns_llong)a[j]*b[i-j]; \
2663  } \
2664  } \
2665  tm[n-1]=(amns_llong)a[0]*b[n-1]; \
2666  PRAGMA_UNROLL \
2667  for (j=1; j<n; j++) \
2668  { \
2669  tm[n-1]+=(amns_llong)a[j]*b[(n-1)-j]; \
2670  } \
2671  \
2672  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
2673  \
2674  amns_internal_red(dst, tm, AMNS); \
2675  } \
2676 
2677 TEMPLATE_amns_elt_mul(2)
2678 TEMPLATE_amns_elt_mul(3)
2679 TEMPLATE_amns_elt_mul(4)
2680 TEMPLATE_amns_elt_mul(5)
2681 TEMPLATE_amns_elt_mul(6)
2682 TEMPLATE_amns_elt_mul(7)
2683 TEMPLATE_amns_elt_mul(8)
2684 TEMPLATE_amns_elt_mul(9)
2685 TEMPLATE_amns_elt_mul(10)
2686 TEMPLATE_amns_elt_mul(11)
2687 TEMPLATE_amns_elt_mul(12)
2688 TEMPLATE_amns_elt_mul(13)
2689 TEMPLATE_amns_elt_mul(14)
2690 TEMPLATE_amns_elt_mul(15)
2691 TEMPLATE_amns_elt_mul(16)
2692 TEMPLATE_amns_elt_mul(17)
2693 TEMPLATE_amns_elt_mul(18)
2694 TEMPLATE_amns_elt_mul(19)
2695 TEMPLATE_amns_elt_mul(20)
2696 TEMPLATE_amns_elt_mul(21)
2697 TEMPLATE_amns_elt_mul(22)
2698 TEMPLATE_amns_elt_mul(23)
2699 TEMPLATE_amns_elt_mul(24)
2700 TEMPLATE_amns_elt_mul(25)
2701 
2702 #undef TEMPLATE_amns_elt_mul
2703 
2704 #define TEMPLATE_amns_elt_mul_shift_p(sl) \
2705  void \
2706  amns_elt_mul_shift_p##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS) \
2707  { \
2708  const uint8_t n = sl; \
2709  uint8_t i, j; \
2710  amns_llong tm[n]; \
2711  \
2712  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
2713  MPHELL_ASSERT(amns_calculate_max_coeff(b, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(b) > rho_max\n"); \
2714  \
2715  /* Polynomial Multiplication */ \
2716  \
2717  PRAGMA_UNROLL \
2718  for(i=0; i<n-1; i++) \
2719  { \
2720  tm[i]=((amns_llong)a[i+1]*b[n-1]); \
2721  PRAGMA_UNROLL \
2722  for (j=i+2; j<n; j++) \
2723  { \
2724  tm[i]+=((amns_llong)a[j]*b[(n+i)-j]); \
2725  } \
2726  tm[i] <<= 1; \
2727  PRAGMA_UNROLL \
2728  for (j=0; j<=i; j++) \
2729  { \
2730  tm[i]+=(amns_llong)a[j]*b[i-j]; \
2731  } \
2732  } \
2733  tm[n-1]=(amns_llong)a[0]*b[n-1]; \
2734  PRAGMA_UNROLL \
2735  for (j=1; j<n; j++) \
2736  { \
2737  tm[n-1]+=(amns_llong)a[j]*b[(n-1)-j]; \
2738  } \
2739  \
2740  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
2741  \
2742  amns_internal_red(dst, tm, AMNS); \
2743  } \
2744 
2745 TEMPLATE_amns_elt_mul_shift_p(2)
2746 TEMPLATE_amns_elt_mul_shift_p(3)
2747 TEMPLATE_amns_elt_mul_shift_p(4)
2748 TEMPLATE_amns_elt_mul_shift_p(5)
2749 TEMPLATE_amns_elt_mul_shift_p(6)
2750 TEMPLATE_amns_elt_mul_shift_p(7)
2751 TEMPLATE_amns_elt_mul_shift_p(8)
2752 TEMPLATE_amns_elt_mul_shift_p(9)
2753 TEMPLATE_amns_elt_mul_shift_p(10)
2754 TEMPLATE_amns_elt_mul_shift_p(11)
2755 TEMPLATE_amns_elt_mul_shift_p(12)
2756 TEMPLATE_amns_elt_mul_shift_p(13)
2757 TEMPLATE_amns_elt_mul_shift_p(14)
2758 TEMPLATE_amns_elt_mul_shift_p(15)
2759 TEMPLATE_amns_elt_mul_shift_p(16)
2760 TEMPLATE_amns_elt_mul_shift_p(17)
2761 TEMPLATE_amns_elt_mul_shift_p(18)
2762 TEMPLATE_amns_elt_mul_shift_p(19)
2763 TEMPLATE_amns_elt_mul_shift_p(20)
2764 TEMPLATE_amns_elt_mul_shift_p(21)
2765 TEMPLATE_amns_elt_mul_shift_p(22)
2766 TEMPLATE_amns_elt_mul_shift_p(23)
2767 TEMPLATE_amns_elt_mul_shift_p(24)
2768 TEMPLATE_amns_elt_mul_shift_p(25)
2769 
2770 #undef TEMPLATE_amns_elt_mul_shift_p
2771 
2772 #define TEMPLATE_amns_elt_mul_shift_n(sl) \
2773  void \
2774  amns_elt_mul_shift_n##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS) \
2775  { \
2776  const uint8_t n = sl; \
2777  uint8_t i, j; \
2778  amns_llong tm[n]; \
2779  \
2780  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
2781  MPHELL_ASSERT(amns_calculate_max_coeff(b, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(b) > rho_max\n"); \
2782  \
2783  /* Polynomial Multiplication */ \
2784  \
2785  PRAGMA_UNROLL \
2786  for(i=0; i<n-1; i++) \
2787  { \
2788  tm[i]=-((amns_llong)a[i+1]*b[n-1]); \
2789  PRAGMA_UNROLL \
2790  for (j=i+2; j<n; j++) \
2791  { \
2792  tm[i]-=((amns_llong)a[j]*b[(n+i)-j]); \
2793  } \
2794  tm[i] <<= 1; \
2795  PRAGMA_UNROLL \
2796  for (j=0; j<=i; j++) \
2797  { \
2798  tm[i]+=(amns_llong)a[j]*b[i-j]; \
2799  } \
2800  } \
2801  tm[n-1]=(amns_llong)a[0]*b[n-1]; \
2802  PRAGMA_UNROLL \
2803  for (j=1; j<n; j++) \
2804  { \
2805  tm[n-1]+=(amns_llong)a[j]*b[(n-1)-j]; \
2806  } \
2807  \
2808  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
2809  \
2810  amns_internal_red(dst, tm, AMNS); \
2811  } \
2812 
2813 TEMPLATE_amns_elt_mul_shift_n(2)
2814 TEMPLATE_amns_elt_mul_shift_n(3)
2815 TEMPLATE_amns_elt_mul_shift_n(4)
2816 TEMPLATE_amns_elt_mul_shift_n(5)
2817 TEMPLATE_amns_elt_mul_shift_n(6)
2818 TEMPLATE_amns_elt_mul_shift_n(7)
2819 TEMPLATE_amns_elt_mul_shift_n(8)
2820 TEMPLATE_amns_elt_mul_shift_n(9)
2821 TEMPLATE_amns_elt_mul_shift_n(10)
2822 TEMPLATE_amns_elt_mul_shift_n(11)
2823 TEMPLATE_amns_elt_mul_shift_n(12)
2824 TEMPLATE_amns_elt_mul_shift_n(13)
2825 TEMPLATE_amns_elt_mul_shift_n(14)
2826 TEMPLATE_amns_elt_mul_shift_n(15)
2827 TEMPLATE_amns_elt_mul_shift_n(16)
2828 TEMPLATE_amns_elt_mul_shift_n(17)
2829 TEMPLATE_amns_elt_mul_shift_n(18)
2830 TEMPLATE_amns_elt_mul_shift_n(19)
2831 TEMPLATE_amns_elt_mul_shift_n(20)
2832 TEMPLATE_amns_elt_mul_shift_n(21)
2833 TEMPLATE_amns_elt_mul_shift_n(22)
2834 TEMPLATE_amns_elt_mul_shift_n(23)
2835 TEMPLATE_amns_elt_mul_shift_n(24)
2836 TEMPLATE_amns_elt_mul_shift_n(25)
2837 
2838 #undef TEMPLATE_amns_elt_mul_shift_n
2839 
2840 void amns_elt_mul(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
2841 {
2842  AMNS->amns_elt_mul(dst, a, b, AMNS);
2843 }
2844 
2852 void amns_elt_sqr_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
2853 {
2854 #if MPHELL_USE_DEBUG == 1
2855  ((amns_ptr)AMNS)->nb_mul++;
2856 #endif
2857  const uint8_t n = AMNS->n;
2858  int8_t i, j;
2859  amns_llong tm[n];
2860 
2861  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n");
2862 
2863  /* Polynomial Multiplication */
2864 
2865  if(AMNS->lambda_bit == 1)
2866  {
2867  for(i=0; i<n-2; i++)
2868  {
2869  tm[i]=((amns_llong)a[i+1]*a[n-1])<<1;
2870  for (j=i+2; j<(n+i+1)/2; j++)
2871  {
2872  tm[i]+=(((amns_llong)a[j]*a[(n+i)-j]))<<1;
2873  }
2874  if((i & 1) == (n & 1))
2875  /* i is the same parity than n */
2876  {
2877  tm[i]+=((amns_llong)a[(n+i)/2]*a[(n+i)/2]);
2878  }
2879  tm[i] <<= AMNS->lambda_bit;
2880  if((i & 1) == 0)
2881  /* i is even */
2882  {
2883  tm[i]+=((amns_llong)a[i/2]*a[i/2]);
2884  }
2885  for (j=0; j<(i+1)/2; j++)
2886  {
2887  tm[i]+=((amns_llong)a[j]*a[i-j])<<1;
2888  }
2889  }
2890  tm[n-2]=((amns_llong)a[n-1]*a[n-1]);
2891  tm[n-2] <<= AMNS->lambda_bit;
2892  if((n & 1) == 0)
2893  /* n-2 is even and i <= n/2 */
2894  {
2895  tm[n-2]+=((amns_llong)a[(n-2)/2]*a[(n-2)/2]);
2896  }
2897  for (j=0; j<(n-1)/2; j++)
2898  {
2899  tm[n-2]+=((amns_llong)a[j]*a[(n-2)-j])<<1;
2900  }
2901 
2902  tm[n-1]=((amns_llong)a[0]*a[n-1])<<1;
2903  for (j=1; j<n/2; j++)
2904  {
2905  tm[n-1]+=((amns_llong)a[j]*a[(n-1)-j])<<1;
2906  }
2907  if(n & 1)
2908  /* n odd => n-1 even */
2909  {
2910  tm[n-1]+=((amns_llong)a[(n-1)/2]*a[(n-1)/2]);
2911  }
2912  }
2913  else
2914  {
2915  for(i=0; i<n-2; i++)
2916  {
2917  tm[i]=((amns_llong)a[i+1]*a[n-1])<<1;
2918  for (j=i+2; j<(n+i+1)/2; j++)
2919  {
2920  tm[i]+=(((amns_llong)a[j]*a[(n+i)-j]))<<1;
2921  }
2922  if((i & 1) == (n & 1))
2923  /* i is the same parity than n */
2924  {
2925  tm[i]+=((amns_llong)a[(n+i)/2]*a[(n+i)/2]);
2926  }
2927  tm[i] *= AMNS->lambda;
2928  if((i & 1) == 0)
2929  /* i is even */
2930  {
2931  tm[i]+=((amns_llong)a[i/2]*a[i/2]);
2932  }
2933  for (j=0; j<(i+1)/2; j++)
2934  {
2935  tm[i]+=((amns_llong)a[j]*a[i-j])<<1;
2936  }
2937  }
2938  tm[n-2]=((amns_llong)a[n-1]*a[n-1]);
2939  tm[n-2] *= AMNS->lambda;
2940  if((n & 1) == 0)
2941  /* n-2 is even and i <= n/2 */
2942  {
2943  tm[n-2]+=((amns_llong)a[(n-2)/2]*a[(n-2)/2]);
2944  }
2945  for (j=0; j<(n-1)/2; j++)
2946  {
2947  tm[n-2]+=((amns_llong)a[j]*a[(n-2)-j])<<1;
2948  }
2949 
2950  tm[n-1]=((amns_llong)a[0]*a[n-1])<<1;
2951  for (j=1; j<n/2; j++)
2952  {
2953  tm[n-1]+=((amns_llong)a[j]*a[(n-1)-j])<<1;
2954  }
2955  if(n & 1)
2956  /* n odd => n-1 even */
2957  {
2958  tm[n-1]+=((amns_llong)a[(n-1)/2]*a[(n-1)/2]);
2959  }
2960  }
2961 
2962  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */
2963 
2964 #if MPHELL_USE_DEBUG == 1
2965  ((amns_ptr)AMNS)->nb_mul_red++;
2966 #endif
2967 
2968  amns_internal_red(dst, tm, AMNS);
2969 }
2970 
2971 #define TEMPLATE_amns_elt_sqr(sl) \
2972  void \
2973  amns_elt_sqr##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS) \
2974  { \
2975  const uint8_t n = sl; \
2976  int8_t i, j; \
2977  amns_llong tm[n]; \
2978  \
2979  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
2980  \
2981  /* Polynomial Multiplication */ \
2982  PRAGMA_UNROLL \
2983  for(i=0; i<n-2; i++) \
2984  { \
2985  tm[i]=((amns_llong)a[i+1]*a[n-1])<<1; \
2986  PRAGMA_UNROLL \
2987  for (j=i+2; j<(n+i+1)/2; j++) \
2988  { \
2989  tm[i]+=(((amns_llong)a[j]*a[(n+i)-j]))<<1; \
2990  } \
2991  if((i & 1) == (n & 1)) \
2992  /* i is the same parity than n */ \
2993  { \
2994  tm[i]+=((amns_llong)a[(n+i)/2]*a[(n+i)/2]); \
2995  } \
2996  tm[i] *= AMNS->lambda; \
2997  if((i & 1) == 0) \
2998  /* i is even */ \
2999  { \
3000  tm[i]+=((amns_llong)a[i/2]*a[i/2]); \
3001  } \
3002  PRAGMA_UNROLL \
3003  for (j=0; j<(i+1)/2; j++) \
3004  { \
3005  tm[i]+=((amns_llong)a[j]*a[i-j])<<1; \
3006  } \
3007  } \
3008  tm[n-2]=((amns_llong)a[n-1]*a[n-1]); \
3009  tm[n-2] *= AMNS->lambda; \
3010  if((n & 1) == 0) \
3011  /* n-2 is even and i <= n/2 */ \
3012  { \
3013  tm[n-2]+=((amns_llong)a[(n-2)/2]*a[(n-2)/2]); \
3014  } \
3015  PRAGMA_UNROLL \
3016  for (j=0; j<(n-1)/2; j++) \
3017  { \
3018  tm[n-2]+=((amns_llong)a[j]*a[(n-2)-j])<<1; \
3019  } \
3020  \
3021  tm[n-1]=((amns_llong)a[0]*a[n-1])<<1; \
3022  PRAGMA_UNROLL \
3023  for (j=1; j<n/2; j++) \
3024  { \
3025  tm[n-1]+=((amns_llong)a[j]*a[(n-1)-j])<<1; \
3026  } \
3027  if(n & 1) \
3028  /* n odd => n-1 even */ \
3029  { \
3030  tm[n-1]+=((amns_llong)a[(n-1)/2]*a[(n-1)/2]); \
3031  } \
3032  \
3033  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
3034  \
3035  amns_internal_red(dst, tm, AMNS); \
3036  } \
3037 
3038 TEMPLATE_amns_elt_sqr(2)
3039 TEMPLATE_amns_elt_sqr(3)
3040 TEMPLATE_amns_elt_sqr(4)
3041 TEMPLATE_amns_elt_sqr(5)
3042 TEMPLATE_amns_elt_sqr(6)
3043 TEMPLATE_amns_elt_sqr(7)
3044 TEMPLATE_amns_elt_sqr(8)
3045 TEMPLATE_amns_elt_sqr(9)
3046 TEMPLATE_amns_elt_sqr(10)
3047 TEMPLATE_amns_elt_sqr(11)
3048 TEMPLATE_amns_elt_sqr(12)
3049 TEMPLATE_amns_elt_sqr(13)
3050 TEMPLATE_amns_elt_sqr(14)
3051 TEMPLATE_amns_elt_sqr(15)
3052 TEMPLATE_amns_elt_sqr(16)
3053 TEMPLATE_amns_elt_sqr(17)
3054 TEMPLATE_amns_elt_sqr(18)
3055 TEMPLATE_amns_elt_sqr(19)
3056 TEMPLATE_amns_elt_sqr(20)
3057 TEMPLATE_amns_elt_sqr(21)
3058 TEMPLATE_amns_elt_sqr(22)
3059 TEMPLATE_amns_elt_sqr(23)
3060 TEMPLATE_amns_elt_sqr(24)
3061 TEMPLATE_amns_elt_sqr(25)
3062 
3063 #undef TEMPLATE_amns_elt_sqr
3064 
3065 #define TEMPLATE_amns_elt_sqr_shift_p(sl) \
3066  void \
3067  amns_elt_sqr_shift_p##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS) \
3068  { \
3069  const uint8_t n = sl; \
3070  int8_t i, j; \
3071  amns_llong tm[n]; \
3072  \
3073  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
3074  \
3075  /* Polynomial Multiplication */ \
3076  PRAGMA_UNROLL \
3077  for(i=0; i<n-2; i++) \
3078  { \
3079  tm[i]=((amns_llong)a[i+1]*a[n-1])<<1; \
3080  PRAGMA_UNROLL \
3081  for (j=i+2; j<(n+i+1)/2; j++) \
3082  { \
3083  tm[i]+=(((amns_llong)a[j]*a[(n+i)-j]))<<1; \
3084  } \
3085  if((i & 1) == (n & 1)) \
3086  /* i is the same parity than n */ \
3087  { \
3088  tm[i]+=((amns_llong)a[(n+i)/2]*a[(n+i)/2]); \
3089  } \
3090  tm[i] <<= 1; \
3091  if((i & 1) == 0) \
3092  /* i is even */ \
3093  { \
3094  tm[i]+=((amns_llong)a[i/2]*a[i/2]); \
3095  } \
3096  PRAGMA_UNROLL \
3097  for (j=0; j<(i+1)/2; j++) \
3098  { \
3099  tm[i]+=((amns_llong)a[j]*a[i-j])<<1; \
3100  } \
3101  } \
3102  tm[n-2]=((amns_llong)a[n-1]*a[n-1]); \
3103  tm[n-2] <<= 1; \
3104  if((n & 1) == 0) \
3105  /* n-2 is even and i <= n/2 */ \
3106  { \
3107  tm[n-2]+=((amns_llong)a[(n-2)/2]*a[(n-2)/2]); \
3108  } \
3109  PRAGMA_UNROLL \
3110  for (j=0; j<(n-1)/2; j++) \
3111  { \
3112  tm[n-2]+=((amns_llong)a[j]*a[(n-2)-j])<<1; \
3113  } \
3114  \
3115  tm[n-1]=((amns_llong)a[0]*a[n-1])<<1; \
3116  PRAGMA_UNROLL \
3117  for (j=1; j<n/2; j++) \
3118  { \
3119  tm[n-1]+=((amns_llong)a[j]*a[(n-1)-j])<<1; \
3120  } \
3121  if(n & 1) \
3122  /* n odd => n-1 even */ \
3123  { \
3124  tm[n-1]+=((amns_llong)a[(n-1)/2]*a[(n-1)/2]); \
3125  } \
3126  \
3127  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
3128  \
3129  amns_internal_red(dst, tm, AMNS); \
3130  } \
3131 
3132 TEMPLATE_amns_elt_sqr_shift_p(2)
3133 TEMPLATE_amns_elt_sqr_shift_p(3)
3134 TEMPLATE_amns_elt_sqr_shift_p(4)
3135 TEMPLATE_amns_elt_sqr_shift_p(5)
3136 TEMPLATE_amns_elt_sqr_shift_p(6)
3137 TEMPLATE_amns_elt_sqr_shift_p(7)
3138 TEMPLATE_amns_elt_sqr_shift_p(8)
3139 TEMPLATE_amns_elt_sqr_shift_p(9)
3140 TEMPLATE_amns_elt_sqr_shift_p(10)
3141 TEMPLATE_amns_elt_sqr_shift_p(11)
3142 TEMPLATE_amns_elt_sqr_shift_p(12)
3143 TEMPLATE_amns_elt_sqr_shift_p(13)
3144 TEMPLATE_amns_elt_sqr_shift_p(14)
3145 TEMPLATE_amns_elt_sqr_shift_p(15)
3146 TEMPLATE_amns_elt_sqr_shift_p(16)
3147 TEMPLATE_amns_elt_sqr_shift_p(17)
3148 TEMPLATE_amns_elt_sqr_shift_p(18)
3149 TEMPLATE_amns_elt_sqr_shift_p(19)
3150 TEMPLATE_amns_elt_sqr_shift_p(20)
3151 TEMPLATE_amns_elt_sqr_shift_p(21)
3152 TEMPLATE_amns_elt_sqr_shift_p(22)
3153 TEMPLATE_amns_elt_sqr_shift_p(23)
3154 TEMPLATE_amns_elt_sqr_shift_p(24)
3155 TEMPLATE_amns_elt_sqr_shift_p(25)
3156 
3157 #undef TEMPLATE_amns_elt_sqr_shift_p
3158 
3159 #define TEMPLATE_amns_elt_sqr_shift_n(sl) \
3160  void \
3161  amns_elt_sqr_shift_n##sl(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS) \
3162  { \
3163  const uint8_t n = sl; \
3164  int8_t i, j; \
3165  amns_llong tm[n]; \
3166  \
3167  MPHELL_ASSERT(amns_calculate_max_coeff(a, AMNS) < AMNS->max_digit_delta, "amns_elt_mul, internal reduction problem, max_coef(a) > rho_max\n"); \
3168  \
3169  /* Polynomial Multiplication */ \
3170  PRAGMA_UNROLL \
3171  for(i=0; i<n-2; i++) \
3172  { \
3173  tm[i]=-((amns_llong)a[i+1]*a[n-1])<<1; \
3174  PRAGMA_UNROLL \
3175  for (j=i+2; j<(n+i+1)/2; j++) \
3176  { \
3177  tm[i]-=(((amns_llong)a[j]*a[(n+i)-j]))<<1; \
3178  } \
3179  if((i & 1) == (n & 1)) \
3180  /* i is the same parity than n */ \
3181  { \
3182  tm[i]-=((amns_llong)a[(n+i)/2]*a[(n+i)/2]); \
3183  } \
3184  tm[i] <<= 1; \
3185  if((i & 1) == 0) \
3186  /* i is even */ \
3187  { \
3188  tm[i]+=((amns_llong)a[i/2]*a[i/2]); \
3189  } \
3190  PRAGMA_UNROLL \
3191  for (j=0; j<(i+1)/2; j++) \
3192  { \
3193  tm[i]+=((amns_llong)a[j]*a[i-j])<<1; \
3194  } \
3195  } \
3196  tm[n-2]=((amns_llong)a[n-1]*a[n-1]); \
3197  tm[n-2] <<= 1; \
3198  if((n & 1) == 0) \
3199  /* n-2 is even and i <= n/2 */ \
3200  { \
3201  tm[n-2]+=((amns_llong)a[(n-2)/2]*a[(n-2)/2]); \
3202  } \
3203  PRAGMA_UNROLL \
3204  for (j=0; j<(n-1)/2; j++) \
3205  { \
3206  tm[n-2]+=((amns_llong)a[j]*a[(n-2)-j])<<1; \
3207  } \
3208  \
3209  tm[n-1]=((amns_llong)a[0]*a[n-1])<<1; \
3210  PRAGMA_UNROLL \
3211  for (j=1; j<n/2; j++) \
3212  { \
3213  tm[n-1]+=((amns_llong)a[j]*a[(n-1)-j])<<1; \
3214  } \
3215  if(n & 1) \
3216  /* n odd => n-1 even */ \
3217  { \
3218  tm[n-1]+=((amns_llong)a[(n-1)/2]*a[(n-1)/2]); \
3219  } \
3220  \
3221  /* Internal reduction (coeffs), RedCoeff - Montgomery like (Randomization of Arithmetic over AMNS) */ \
3222  \
3223  amns_internal_red(dst, tm, AMNS); \
3224  } \
3225 
3226 TEMPLATE_amns_elt_sqr_shift_n(2)
3227 TEMPLATE_amns_elt_sqr_shift_n(3)
3228 TEMPLATE_amns_elt_sqr_shift_n(4)
3229 TEMPLATE_amns_elt_sqr_shift_n(5)
3230 TEMPLATE_amns_elt_sqr_shift_n(6)
3231 TEMPLATE_amns_elt_sqr_shift_n(7)
3232 TEMPLATE_amns_elt_sqr_shift_n(8)
3233 TEMPLATE_amns_elt_sqr_shift_n(9)
3234 TEMPLATE_amns_elt_sqr_shift_n(10)
3235 TEMPLATE_amns_elt_sqr_shift_n(11)
3236 TEMPLATE_amns_elt_sqr_shift_n(12)
3237 TEMPLATE_amns_elt_sqr_shift_n(13)
3238 TEMPLATE_amns_elt_sqr_shift_n(14)
3239 TEMPLATE_amns_elt_sqr_shift_n(15)
3240 TEMPLATE_amns_elt_sqr_shift_n(16)
3241 TEMPLATE_amns_elt_sqr_shift_n(17)
3242 TEMPLATE_amns_elt_sqr_shift_n(18)
3243 TEMPLATE_amns_elt_sqr_shift_n(19)
3244 TEMPLATE_amns_elt_sqr_shift_n(20)
3245 TEMPLATE_amns_elt_sqr_shift_n(21)
3246 TEMPLATE_amns_elt_sqr_shift_n(22)
3247 TEMPLATE_amns_elt_sqr_shift_n(23)
3248 TEMPLATE_amns_elt_sqr_shift_n(24)
3249 TEMPLATE_amns_elt_sqr_shift_n(25)
3250 
3251 #undef TEMPLATE_amns_elt_sqr_shift_n
3252 
3253 
3254 void amns_elt_sqr(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
3255 {
3256  AMNS->amns_elt_sqr(dst, a, AMNS);
3257 }
3258 
3259 
amns_free
void amns_free(amns_ptr *AMNS)
Free the amns system.
Definition: mphell-amns.c:444
amns_elt_sqr_generic
void amns_elt_sqr_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
Set dst to a^2, using a generic code not optimised.
Definition: mphell-amns.c:2852
amns_calcule_Ti
void amns_calcule_Ti(amns_ptr AMNS, const amns_block *P0, const amns_block *P1)
Compute the polynomials (amns elements) Ti such that Ti(gamma) = 2^(rho.i) * phi^2....
Definition: mphell-amns.c:983
amns_init
void amns_init(amns_ptr AMNS, const amns_block *E, const amns_block *P0, const amns_block *P1, const amns_block *M, const amns_ulong *Mprime, number_srcptr p, number gamma, uint8_t rho, uint8_t nb_add_max)
Initialise the amns system.
Definition: mphell-amns.c:1324
amns_elt_read_sep
void amns_elt_read_sep(amns_block *x, char *str)
Parser to read a signed AMNS vector.
Definition: mphell-amns.c:1202
amns_init_stat
void amns_init_stat(amns_ptr AMNS)
Initialise again the AMNS statistics.
Definition: mphell-amns.c:2039
amns_print_AMNS
void amns_print_AMNS(amns_srcptr AMNS)
Print the AMNS system.
Definition: mphell-amns.c:577
amns_calcule_gi
void amns_calcule_gi(amns_ptr AMNS)
Compute the number gi such that gi = gamma^i mod p. Used for AMNS to binary conversion.
Definition: mphell-amns.c:1020
amns_elt_read_sep_ul
void amns_elt_read_sep_ul(amns_ulong *x, char *str)
Parser to read a unsigned AMNS vector.
Definition: mphell-amns.c:1227
amns_elt_sub
void amns_elt_sub(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
Set dst to a - b.
Definition: mphell-amns.c:2507
amns_print_elt
void amns_print_elt(amns_elt_srcptr x, amns_srcptr AMNS)
Print the AMNS element x.
Definition: mphell-amns.c:561
amns_elt_cmp_ui
int8_t amns_elt_cmp_ui(amns_elt_srcptr src1, block src2, amns_srcptr AMNS)
Compare src1 and src2.
Definition: mphell-amns.c:2297
amns_print_bloc_ul
void amns_print_bloc_ul(amns_ulong b)
Print an amns ulong (uint64_t or uint32_t)
Definition: mphell-amns.c:524
previous_power_2
uint8_t previous_power_2(uint8_t x)
Round to the previous power of 2.
Definition: mphell-amns.c:1316
amns_elt_read_ul
void amns_elt_read_ul(amns_ulong *x, char *str)
Read a ulong polynomial from a string.
Definition: mphell-amns.c:2088
amns_calculate_max_coeff
amns_block amns_calculate_max_coeff(amns_elt_srcptr a, amns_srcptr AMNS)
Calculate (||a||_infty)
Definition: mphell-amns.c:671
amns_print_elt_ul
void amns_print_elt_ul(const amns_ulong *x, amns_srcptr AMNS)
Print an amns ulong vector.
Definition: mphell-amns.c:572
amns_elt_set_zero
void amns_elt_set_zero(amns_elt_ptr dst, amns_srcptr AMNS)
Set dst to 0.
Definition: mphell-amns.c:2103
amns_elt_is_reduced_generic
static bool amns_elt_is_reduced_generic(amns_elt_srcptr a, amns_srcptr AMNS)
Test if the coefficient a_i of a are all such that |a_i|<2^rho.
Definition: mphell-amns.c:1112
amns_calcule_Miprime
void amns_calcule_Miprime(amns_ptr AMNS, const amns_block *Mprime)
Compute the Mtiprime used by the internal reduction.
Definition: mphell-amns.c:1075
amns_elt_add_generic
void amns_elt_add_generic(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
Set dst to a + b, using a generic code not optimised.
Definition: mphell-amns.c:2329
amns_elt_add
void amns_elt_add(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
Set dst to a + b.
Definition: mphell-amns.c:2354
amns_mul_scalar_llong
void amns_mul_scalar_llong(amns_llong *dst, amns_elt_srcptr a, amns_ulong b, amns_srcptr AMNS)
Multiply the llong polynomial a by the scalar b.
Definition: mphell-amns.c:2124
amns_add_llong
void amns_add_llong(amns_llong *dst, amns_llong *a, amns_llong *b, amns_srcptr AMNS)
Add the llong polynomials a and b.
Definition: mphell-amns.c:2143
amns_internal_red_exact
void amns_internal_red_exact(amns_elt_ptr dst, amns_srcptr AMNS)
Set dst such that dst(gamma) == R(gamma) et |coeffs(dst)| < 2^rho, use after addition when the coeffi...
Definition: mphell-amns.c:951
amns_calculate_max_coeff_size
uint8_t amns_calculate_max_coeff_size(amns_elt_srcptr a, amns_srcptr AMNS)
Calculate log2(||a||_infty)
Definition: mphell-amns.c:645
amns_internal_red_generic
void amns_internal_red_generic(amns_elt_ptr S, amns_llong *V, amns_srcptr AMNS)
Internal reduction using Montgomery method, not optimised because the compiler cannot guess the loop ...
Definition: mphell-amns.c:697
amns_elt_neg
void amns_elt_neg(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
Set dst to -a.
Definition: mphell-amns.c:2427
amns_elt_alloc
void amns_elt_alloc(amns_elt *dst, amns_srcptr AMNS)
Allocate the amns (polynomial of degree less than n) element according to the degree of E.
Definition: mphell-amns.c:496
amns_elt_copy
void amns_elt_copy(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
Copy a into dst.
Definition: mphell-amns.c:2310
amns_elt_isequal
bool amns_elt_isequal(amns_elt_srcptr src1, amns_elt_srcptr src2, amns_srcptr AMNS)
Test if src1 == src2, if true OK, if false, must be tested on binary !!!
Definition: mphell-amns.c:2271
amns_elt_cmp
int8_t amns_elt_cmp(amns_elt_srcptr src1, amns_elt_srcptr src2, amns_srcptr AMNS)
Compare src1 and src2.
Definition: mphell-amns.c:2284
binary_ui_to_amns
void binary_ui_to_amns(block a, amns_elt_ptr dst, amns_srcptr AMNS)
Convert a small number into its AMNS representation.
Definition: mphell-amns.c:2189
binary_to_amns
void binary_to_amns(number_srcptr a, amns_elt_ptr dst, amns_srcptr AMNS)
Convert a number into its AMNS representation.
Definition: mphell-amns.c:2154
amns_print_elt_raw
void amns_print_elt_raw(const amns_block *x, uint8_t size)
Print the AMNS element x.
Definition: mphell-amns.c:533
amns_elt_is_zero
bool amns_elt_is_zero(amns_elt_srcptr src, amns_srcptr AMNS)
Test if src is zero.
Definition: mphell-amns.c:2261
amns_print_stat
void amns_print_stat(amns_srcptr AMNS)
Print the AMNS system statistic.
Definition: mphell-amns.c:622
amns_elt_write
void amns_elt_write(amns_block *x, uint8_t size, char *str)
Write a amns element into a string.
Definition: mphell-amns.c:2053
amns_internal_red
void amns_internal_red(amns_elt_ptr S, amns_llong *V, amns_srcptr AMNS)
Internal reduction using Montgomery method, optimised with templates to allow the compiler to guess t...
Definition: mphell-amns.c:740
amns_elt_read
void amns_elt_read(amns_block *x, char *str)
Read a AMNS element from a string.
Definition: mphell-amns.c:2069
amns_elt_copy_ul_2_amns
void amns_elt_copy_ul_2_amns(amns_elt dst, const amns_ulong *a, amns_srcptr AMNS)
Copy a unsigned vector into a signed vector modulo phi, the modulo is applied through the cast.
Definition: mphell-amns.c:1183
amns_print_elt_raw_ul
void amns_print_elt_raw_ul(const amns_ulong *x, uint8_t size)
Print an amns ulong vector.
Definition: mphell-amns.c:550
amns_to_binary
void amns_to_binary(const amns_elt_srcptr a, number_ptr dst, amns_srcptr AMNS)
Convert AMNS representation into a number.
Definition: mphell-amns.c:2223
amns_calcule_Mi
void amns_calcule_Mi(amns_ptr AMNS, const amns_block *M)
Compute the Mti used by the internal reduction.
Definition: mphell-amns.c:1040
amns_elt_free
void amns_elt_free(amns_elt *dst)
Free the amns element.
Definition: mphell-amns.c:501
amns_print_bloc
void amns_print_bloc(amns_block b)
Print b.
Definition: mphell-amns.c:510
amns_alloc_init_str
void amns_alloc_init_str(amns_ptr *AMNS, char *str, number p)
Allocate and initialise the amns system from the string generated by the Sage AMNS generator from htt...
Definition: mphell-amns.c:1242
set_fast_internal_reduction_nist521
void set_fast_internal_reduction_nist521(amns_ptr AMNS)
Set up a dedicated AMNS internal reduction for NIST 521 (Mersenne prime), the AMNS must be exactly th...
Definition: mphell-amns.c:935
mphell-amns.h
Declaration of Adapted Modular Number System (AMNS) functions.
amns_elt_srcptr
const amns_block * amns_elt_srcptr
Define amns_elt_srcptr, use in all functions where the parameter is const.
Definition: mphell-amns.h:73
amns_ptr
amns_t * amns_ptr
Define amns_ptr, use in all functions.
Definition: mphell-amns.h:150
amns_elt_sqr
void amns_elt_sqr(amns_elt_ptr dst, amns_elt_srcptr a, amns_srcptr AMNS)
Set dst to a^2.
amns_elt_mul
void amns_elt_mul(amns_elt_ptr dst, amns_elt_srcptr a, amns_elt_srcptr b, amns_srcptr AMNS)
Set dst to a * b.
amns_elt_ptr
amns_block * amns_elt_ptr
Define amns_elt_ptr, use in all functions.
Definition: mphell-amns.h:67
amns_elt_relax_pool_elt
static void amns_elt_relax_pool_elt(amns_elt *dst, amns_srcptr AMNS, uint8_t stack)
Relax an initialised amns element from the pool.
Definition: mphell-amns.h:202
amns_elt_get_pool_elt
static void amns_elt_get_pool_elt(amns_elt *dst, amns_srcptr AMNS, uint8_t stack)
Get an initialised amns element from the pool.
Definition: mphell-amns.h:169
amns_alloc
void amns_alloc(amns_ptr *AMNS, uint8_t n, number_srcptr p)
Allocate the amns system according to the degree of the external reduction polynomial E.
amns_elt
amns_block * amns_elt
An AMNS element is a polynomial, we stock the digits in a left to right representation (a_0 is the co...
Definition: mphell-amns.h:61
amns_block
int64_t amns_block
Define the AMNS base block type.
Definition: mphell-amns.h:39
number_isequal_ui
bool number_isequal_ui(number_srcptr src1, const block src2)
Test if src1 == src2.
Definition: mphell-number.c:749
number_block_size
uint8_t number_block_size(number_srcptr src)
Calculate the number of block used by src.
Definition: mphell-number.c:270
number_isequal
bool number_isequal(number_srcptr src1, number_srcptr src2)
Test if src1 == src2.
Definition: mphell-number.c:772
number_mod
void number_mod(number_ptr dst, number_srcptr src1, number_srcptr src2)
Compute dst such that src1 = q * src2 + dst ; dst < src2.
Definition: mphell-number.c:1791
number_copy
void number_copy(number_ptr dst, number_srcptr src)
Copy src into dst.
Definition: mphell-number.c:87
number_addmul_ui
void number_addmul_ui(number_ptr dst, number_srcptr src1, const block src2)
Set dst to dst + src1 * src2.
Definition: mphell-number.c:1397
number_set_ui
void number_set_ui(number_ptr dst, const block src)
Set dst to src.
Definition: mphell-number.c:103
number_free
void number_free(number *dst)
Free a number_ptr allocated on the RAM memory (malloc)
Definition: mphell-number.c:75
number_set_str
void number_set_str(number_ptr dst, const char *str, const uint8_t base)
Set dst to str.
Definition: mphell-number.c:298
number_powm_ui
void number_powm_ui(number_ptr dst, number_srcptr src1, const block src2, number_srcptr mod, uint8_t stack)
Set dst to src1^src2 modulo mod.
Definition: mphell-number.c:1604
number_isdiff_ui
bool number_isdiff_ui(number_srcptr src1, const block src2)
Test if src1 != src2.
Definition: mphell-number.c:786
number_tmp_free
void number_tmp_free(number *t, const uint8_t size, uint8_t stack)
Free a temporary number.
Definition: mphell-number.c:45
number_mul_mod
void number_mul_mod(number_ptr dst, number_srcptr src1, number_srcptr src2, number_srcptr mod, uint8_t stack)
Set dst to (src1 * src2) % mod.
Definition: mphell-number.c:1442
number_cmp
int8_t number_cmp(number_srcptr src1, number_srcptr src2)
Compare src1 and src2.
Definition: mphell-number.c:957
number_divmod_ui
void number_divmod_ui(number_ptr q, block *r, number_srcptr src1, const block src2)
Compute (q, r) such that src1 = q * src2 + r ; r < src2.
Definition: mphell-number.c:1673
number_submul_ui
void number_submul_ui(number_ptr dst, number_srcptr src1, const block src2)
Set dst to dst - src1 * src2.
Definition: mphell-number.c:1417
number_tmp_alloc
void number_tmp_alloc(number *t, const uint8_t size, uint8_t stack)
Allocate a temporary number.
Definition: mphell-number.c:31
number_cmp_ui
int8_t number_cmp_ui(number_srcptr src1, const block src2)
Compare src1 and src2.
Definition: mphell-number.c:937
number_log2
uint16_t number_log2(number_srcptr src)
Calculate log2(src), which is the binary size of src.
Definition: mphell-number.c:256
number_print
void number_print(number_srcptr src, const uint8_t base)
Print src in base "base".
Definition: mphell-number.c:706
number_init
void number_init(number *dst, const uint8_t n)
Allocate a number_ptr on the RAM memory (malloc)
Definition: mphell-number.c:59
bits_to_nblock
uint8_t bits_to_nblock(const uint16_t nbits)
Return the number of blocks required to store a nbits number.
Definition: mphell-util.c:29
amns
Define a AMNS.
Definition: mphell-amns.h:81
amns::lambda_sign
bool lambda_sign
Definition: mphell-amns.h:99
amns::gamma
number gamma
Definition: mphell-amns.h:86
amns::E
amns_elt E
Definition: mphell-amns.h:84
amns::Mti
amns_elt * Mti
Definition: mphell-amns.h:103
amns::Mtiprime
amns_elt * Mtiprime
Definition: mphell-amns.h:104
amns::n
uint8_t n
Definition: mphell-amns.h:88
amns::gamma_size
uint16_t gamma_size
Definition: mphell-amns.h:87
amns::max_amns_block
amns_llong max_amns_block
Definition: mphell-amns.h:95
amns::p
number p
Definition: mphell-amns.h:82
amns::amns_block_size
uint8_t amns_block_size
Definition: mphell-amns.h:94
amns::lambda
amns_block lambda
Definition: mphell-amns.h:97
amns::p_size
uint16_t p_size
Definition: mphell-amns.h:83
amns::Ti
amns_elt * Ti
Definition: mphell-amns.h:106
amns::k
uint8_t k
Definition: mphell-amns.h:85
amns::gi
number * gi
Definition: mphell-amns.h:107
amns::lambda_bit
uint8_t lambda_bit
Definition: mphell-amns.h:98
amns::nb_add_max
uint8_t nb_add_max
Definition: mphell-amns.h:101
amns::max_digit_delta
amns_block max_digit_delta
Definition: mphell-amns.h:92
amns::max_digit
amns_block max_digit
Definition: mphell-amns.h:90
amns::min_digit
amns_block min_digit
Definition: mphell-amns.h:91
amns::rho
uint8_t rho
Definition: mphell-amns.h:89
amns::min_digit_delta
amns_block min_digit_delta
Definition: mphell-amns.h:93
Generated by doxygen 1.9.1