MPHELL  4.0.0
mphell-fp2.h
Go to the documentation of this file.
1 /*
2  MPHELL-4.0
3  Author(s): The MPHELL team
4 
5  (C) Copyright 2015-2018 - 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 #ifndef MPHELL_FP2_H
27 #define MPHELL_FP2_H
28 
29 #include "mphell-fp.h"
30 
35 typedef struct
36 {
37  fp_elt v0;
38  fp_elt v1;
39 } fp2_elt_t;
40 
46 
52 
57 typedef const fp2_elt_t * fp2_elt_srcptr;
58 
63 typedef struct
64 {
66  fp_elt non_residue;
67  number q;
68  /*char * pm2; !< Binary representation of (p-1)p-1 (FLT) */
71  number p_odd;
72  uint32_t p_even;
73  uint8_t size;
74 }
76 
82 
83 /**************************************TMP************************************/
84 
92 void
93 fp2_elt_get_pool_elt (fp2_elt * dst, const fp2_param param, uint8_t stack);
94 
102 void
103 fp2_elt_relax_pool_elt (fp2_elt * dst, const fp2_param param, uint8_t stack);
104 
105 /************************************SETTERS**********************************/
106 
113 void
114 fp2_alloc (fp2_param param, const fp_param base);
115 
124 void
125 fp2_create (fp2_param param, const fp_param base, fp_elt_srcptr non_residue, uint8_t stack);
126 
133 void
134 fp2_copy (fp2_param param_res, const fp2_param param);
135 
141 void
142 fp2_free (fp2_param param);
143 
150 void
151 fp2_get_characteristic (number_ptr c, const fp2_param param);
152 
159 void
160 fp2_get_size (number_ptr c, const fp2_param param);
161 
162 /*void*/
163 /*fp2_get_pm2 (char * str, const fp2_param param);*/
164 
171 void
172 fp2_elt_alloc (fp2_elt * dst, const fp2_param param);
173 
180 void
181 fp2_elt_init (fp2_elt_ptr dst, const fp2_param param);
182 
190 void
191 fp2_elt_copy (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param);
192 
198 void
199 fp2_elt_clear (fp2_elt * src);
200 
206 void
207 fp2_elt_free (fp2_elt * src);
208 
215 void
216 fp2_elt_set_one (fp2_elt_ptr dst, const fp2_param param);
217 
227 void
228 fp2_elt_set_ui (fp2_elt_ptr dst, const uint64_t src, const bool isreduced,
229  const fp2_param param, uint8_t stack);
230 
240 void
241 fp2_elt_set_number (fp2_elt_ptr dst, number_srcptr src, const bool isreduced,
242  const fp2_param param, uint8_t stack);
243 
251 void
252 fp2_elt_set_fp_elt (fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param);
253 
264 void
265 fp2_elt_set (fp2_elt_ptr dst, number_srcptr src1, number_srcptr src2,
266  const bool isreduced, const fp2_param param, uint8_t stack);
267 
276 void
277 fp2_elt_set_fp_elts (fp2_elt_ptr dst, fp_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param);
278 
289 void
290 fp2_elt_set_str (fp2_elt_ptr dst, const char *str, const uint8_t base,
291  const bool isreduced, const fp2_param param, uint8_t stack);
292 
300 void
301 fp2_elt_random (fp2_elt_ptr dst, const fp2_param param, uint8_t stack);
302 
311 void
312 fp2_elt_lift (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
313 
322 void
323 fp2_str (char **str, const fp2_param param, const uint8_t base, uint8_t stack);
324 
335 void
336 fp2_elt_str (char **str, fp2_elt_srcptr src, const uint8_t base,
337  const bool lift, const fp2_param param, uint8_t stack);
338 
339 /*************************COMPARISON AND LOGICAL******************************/
340 
351 int8_t
352 fp2_elt_cmp_fp_elt (fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param);
353 
364 int8_t
365 fp2_elt_cmp (fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param);
366 
374 bool
375 fp2_elt_isone (fp2_elt_srcptr src, const fp2_param param);
376 
384 bool
385 fp2_elt_iszero (fp2_elt_srcptr src, const fp2_param param);
386 
387 /***************************ADDITION SUBTRACTION******************************/
388 
396 void
397 fp2_elt_inc (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param);
398 
407 void
408 fp2_elt_add_fp_elt (fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2,
409  const fp2_param param);
410 
419 void
421  const fp2_param param);
422 
430 void
431 fp2_elt_dec (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param);
432 
441 void
442 fp2_elt_sub_fp_elt (fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2,
443  const fp2_param param);
444 
453 void
455  const fp2_param param);
456 
464 void
465 fp2_elt_neg_fp_elt (fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param);
466 
474 void
475 fp2_elt_neg (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param);
476 
477 
478 /*******************************MULTIPLICATION********************************/
479 
489 void
490 fp2_elt_mul_fp_elt (fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2,
491  const fp2_param param, uint8_t stack);
492 
500 void
502  const fp2_param param);
503 
511 void
513  const fp2_param param);
514 
522 void
524  const fp2_param param);
525 
534 void
536  const fp2_param param, uint8_t stack);
537 
547 void
549  const fp2_param param, uint8_t stack);
550 
559 void
560 fp2_elt_sqr_fp_elt (fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param, uint8_t stack);
561 
570 void
571 fp2_elt_sqr (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
572 
581 void
582 fp2_elt_inv_fp_elt (fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param, uint8_t stack);
583 
592 void
593 fp2_elt_inv (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
594 
604 void
605 fp2_elt_div_fp_elt (fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2,
606  const fp2_param param, uint8_t stack);
607 
617 void
619  const fp2_param param, uint8_t stack);
629 void
630 fp2_elt_pow_ui (fp2_elt_ptr dst, fp2_elt_srcptr src, const block n,
631  const fp2_param param, uint8_t stack);
632 
642 void
643 fp2_elt_pow_number (fp2_elt_ptr dst, fp2_elt_srcptr src, number_srcptr n,
644  const fp2_param param, uint8_t stack);
645 
654 bool
655 fp2_elt_issquare (fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
656 
668 int8_t
669 fp2_elt_ispower_ui (fp2_elt_srcptr src, const block n, const fp2_param param, uint8_t stack);
670 
682 int8_t
683 fp2_elt_ispower_number (fp2_elt_srcptr src, number_srcptr n,
684  const fp2_param param, uint8_t stack);
685 
694 void
695 fp2_elt_sqrt (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
696 
705 void
706 fp2_elt_cube_root (fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack);
707 
716 void
717 fp2_elt_unity_nth_root (fp2_elt_ptr dst, const block n, const fp2_param param, uint8_t stack);
718 
719 #endif
720 
721 
int8_t fp2_elt_ispower_ui(fp2_elt_srcptr src, const block n, const fp2_param param, uint8_t stack)
Test if src is a n-power in FP2, using A NOTE ON POWERS IN FINITE FIELDS from ANDREAS AABRANDT AND VA...
Definition: mphell-fp2.c:634
void fp2_elt_mul2(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- 2 * src.
Definition: mphell-fp2.c:419
int8_t fp2_elt_cmp_fp_elt(fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param)
Compare src1 and src2 in FP2.
Definition: mphell-fp2.c:311
void fp2_elt_neg_fp_elt(fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param)
Set dst <- (-src)
Definition: mphell-fp2.c:395
void fp2_elt_alloc(fp2_elt *dst, const fp2_param param)
Allocate space for a quadratic extension field element.
Definition: mphell-fp2.c:162
void fp2_alloc(fp2_param param, const fp_param base)
Allocate space for the quadratic extension field informations structure.
Definition: mphell-fp2.c:67
void fp2_elt_set_ui(fp2_elt_ptr dst, const uint64_t src, const bool isreduced, const fp2_param param, uint8_t stack)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp2.c:204
fp_param base
Definition: mphell-fp2.h:65
void fp2_elt_div(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param, uint8_t stack)
Set dst <- src1 / src2.
Definition: mphell-fp2.c:543
fp2_elt_t * fp2_elt_ptr
Define fp2_elt_ptr, use in all functions.
Definition: mphell-fp2.h:51
void fp2_elt_random(fp2_elt_ptr dst, const fp2_param param, uint8_t stack)
Set dst to a random element of FP2, the random process is chosen at the MHELL initialisation.
Definition: mphell-fp2.c:260
void fp2_elt_free(fp2_elt *src)
Free space used by src.
Definition: mphell-fp2.c:190
void fp2_elt_str(char **str, fp2_elt_srcptr src, const uint8_t base, const bool lift, const fp2_param param, uint8_t stack)
Converts src to string format in base specified by base.
Definition: mphell-fp2.c:294
void fp2_elt_unity_nth_root(fp2_elt_ptr dst, const block n, const fp2_param param, uint8_t stack)
Set dst to a non trivial n-th root of unity if it exists (ie n divides q-1), 1 otherwise.
Definition: mphell-fp2.c:1007
void fp2_elt_clear(fp2_elt *src)
Clear space used by src (remove the action of fp2_elt_init but less the one of fp2_elt_alloc)
Definition: mphell-fp2.c:183
int8_t fp2_elt_ispower_number(fp2_elt_srcptr src, number_srcptr n, const fp2_param param, uint8_t stack)
Test if src is a n-power in FP2, using A NOTE ON POWERS IN FINITE FIELDS from ANDREAS AABRANDT AND VA...
Definition: mphell-fp2.c:675
void fp2_elt_mul8(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- 8 * src.
Definition: mphell-fp2.c:435
void fp2_elt_cube_root(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^(1/3)
Definition: mphell-fp2.c:819
void fp2_get_size(number_ptr c, const fp2_param param)
Get the size of the quadratic extension field "param".
Definition: mphell-fp2.c:150
void fp2_elt_copy(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Copy src into dst, src and dst must belong to the same FP2.
Definition: mphell-fp2.c:176
void fp2_get_characteristic(number_ptr c, const fp2_param param)
Get the characteristic of the quadratic extension field "param".
Definition: mphell-fp2.c:144
int8_t fp2_elt_cmp(fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param)
Compare src1 and src2 in FP2.
Definition: mphell-fp2.c:321
void fp2_elt_set(fp2_elt_ptr dst, number_srcptr src1, number_srcptr src2, const bool isreduced, const fp2_param param, uint8_t stack)
Set dst to src1 + src2*x, if Montgomery arithmetic is used, is_reduced == false -> transform dst into...
Definition: mphell-fp2.c:227
bool fp2_elt_iszero(fp2_elt_srcptr src, const fp2_param param)
Test if src is zero.
Definition: mphell-fp2.c:341
void fp2_elt_init(fp2_elt_ptr dst, const fp2_param param)
Initialise a quadratic extension field element.
Definition: mphell-fp2.c:169
void fp2_elt_set_str(fp2_elt_ptr dst, const char *str, const uint8_t base, const bool isreduced, const fp2_param param, uint8_t stack)
Set dst to str, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp2.c:242
number q
Definition: mphell-fp2.h:67
void fp2_elt_mul4(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- 4 * src.
Definition: mphell-fp2.c:427
void fp2_copy(fp2_param param_res, const fp2_param param)
Copy the quadratic extension field structure param into param_res.
Definition: mphell-fp2.c:125
fp2_elt gen_sylow
Definition: mphell-fp2.h:70
void fp2_elt_add(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param)
Set dst <- src1 + src2.
Definition: mphell-fp2.c:364
void fp2_elt_neg(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- (-src)
Definition: mphell-fp2.c:402
void fp2_elt_add_fp_elt(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param)
Set dst <- src1 + src2.
Definition: mphell-fp2.c:356
bool fp2_elt_isone(fp2_elt_srcptr src, const fp2_param param)
Test if src is one.
Definition: mphell-fp2.c:335
void fp2_elt_inv(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^(-1)
Definition: mphell-fp2.c:508
void fp2_elt_sqrt(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^(1/2), using Tonelli–Shanks algorithm.
Definition: mphell-fp2.c:742
void fp2_elt_set_one(fp2_elt_ptr dst, const fp2_param param)
Set dst to one (or its Montgomery form if Montgomery arithmetic is used)
Definition: mphell-fp2.c:197
void fp2_elt_mul(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param, uint8_t stack)
Set dst <- src1 * src2, if Montgomery arithmetic is used, the Montgomery multiplication will be used ...
Definition: mphell-fp2.c:451
void fp2_elt_mul_fp_elt(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param, uint8_t stack)
Set dst <- src1 * src2, if Montgomery arithmetic is used, the Montgomery multiplication will be used ...
Definition: mphell-fp2.c:411
void fp2_elt_div_fp_elt(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param, uint8_t stack)
Set dst <- src1 / src2.
Definition: mphell-fp2.c:532
void fp2_elt_sub(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp2_elt_srcptr src2, const fp2_param param)
Set dst <- src1 - src2.
Definition: mphell-fp2.c:387
void fp2_elt_inv_fp_elt(fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^(-1)
Definition: mphell-fp2.c:501
void fp2_elt_sub_fp_elt(fp2_elt_ptr dst, fp2_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param)
Set dst <- src1 - src2.
Definition: mphell-fp2.c:379
void fp2_elt_mul3(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- 3 * src.
Definition: mphell-fp2.c:443
void fp2_elt_set_number(fp2_elt_ptr dst, number_srcptr src, const bool isreduced, const fp2_param param, uint8_t stack)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp2.c:212
uint8_t size
Definition: mphell-fp2.h:73
Quadratic extension field element structure.
Definition: mphell-fp2.h:35
uint32_t p_even
Definition: mphell-fp2.h:72
fp_elt non_residue
Definition: mphell-fp2.h:66
void fp2_elt_dec(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- src - 1.
Definition: mphell-fp2.c:372
void fp2_elt_inc(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param)
Set dst <- src + 1.
Definition: mphell-fp2.c:349
void fp2_elt_set_fp_elts(fp2_elt_ptr dst, fp_elt_srcptr src1, fp_elt_srcptr src2, const fp2_param param)
Set dst to src1 + src2*x.
Definition: mphell-fp2.c:235
void fp2_free(fp2_param param)
Free the space of the quadratic extension field informations structure.
Definition: mphell-fp2.c:133
void fp2_elt_lift(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
If Montgomery arithmetic is used, lift src (which is into Montgomery form) to classical FP2.
Definition: mphell-fp2.c:267
fp2_param_t * fp2_param
Pointer on a quadratic extension field structure.
Definition: mphell-fp2.h:81
Declaration of primary field functions, if Montgomery arithmetic is used, the Montgomery arithmetic w...
void fp2_elt_relax_pool_elt(fp2_elt *dst, const fp2_param param, uint8_t stack)
Free space of a temporary quadratic extension field element.
Definition: mphell-fp2.c:58
fp2_elt_t fp2_elt
Quadratic extension field element structure.
Definition: mphell-fp2.h:45
bool fp2_elt_issquare(fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Test if src is a square, using A NOTE ON POWERS IN FINITE FIELDS from ANDREAS AABRANDT AND VAGN LUNDS...
Definition: mphell-fp2.c:616
void fp2_str(char **str, const fp2_param param, const uint8_t base, uint8_t stack)
Converts fp2_param param to string format in base specified by base.
Definition: mphell-fp2.c:274
fp2_elt non_res
Definition: mphell-fp2.h:69
Primary field parameters.
number p_odd
Definition: mphell-fp2.h:71
const fp2_elt_t * fp2_elt_srcptr
Define fp2_elt_srcptr, use in all functions where the parameter is const.
Definition: mphell-fp2.h:57
void fp2_elt_set_fp_elt(fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param)
Set dst to src.
Definition: mphell-fp2.c:220
fp_elt v1
Definition: mphell-fp2.h:38
void fp2_elt_sqr(fp2_elt_ptr dst, fp2_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^2.
Definition: mphell-fp2.c:495
void fp2_elt_sqr_fp_elt(fp2_elt_ptr dst, fp_elt_srcptr src, const fp2_param param, uint8_t stack)
Set dst <- src^2.
Definition: mphell-fp2.c:483
Quadratic extension field structure.
Definition: mphell-fp2.h:63
fp_elt v0
Definition: mphell-fp2.h:37
void fp2_elt_pow_number(fp2_elt_ptr dst, fp2_elt_srcptr src, number_srcptr n, const fp2_param param, uint8_t stack)
Set dst <- src^n.
Definition: mphell-fp2.c:577
void fp2_elt_get_pool_elt(fp2_elt *dst, const fp2_param param, uint8_t stack)
Allocate and initialise space for a temporary quadratic extension field element.
Definition: mphell-fp2.c:51
void fp2_create(fp2_param param, const fp_param base, fp_elt_srcptr non_residue, uint8_t stack)
Create a quadratic extension of the field base.
Definition: mphell-fp2.c:106
void fp2_elt_pow_ui(fp2_elt_ptr dst, fp2_elt_srcptr src, const block n, const fp2_param param, uint8_t stack)
Set dst <- src^n.
Definition: mphell-fp2.c:554