MPHELL  4.0.0
mphell-fp3.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_fp3_H
27 #define MPHELL_fp3_H
28 
29 #include "mphell-fp.h"
30 
35 typedef struct
36 {
37  fp_elt v0;
38  fp_elt v1;
39  fp_elt v2;
40 } fp3_elt_t;
41 
47 
53 
58 typedef const fp3_elt_t * fp3_elt_srcptr;
59 
64 typedef struct
65 {
67  fp_elt non_residue;
68  number q;
69  /*char * pm2; !< Binary representation of (p-1)p^2-1 (FLT) */
72  number p_odd;
73  uint32_t p_even;
74  uint8_t size;
75 }
77 
83 
84 /**************************************TMP************************************/
85 
93 void
94 fp3_elt_get_pool_elt (fp3_elt * dst, const fp3_param param, uint8_t stack);
95 
103 void
104 fp3_elt_relax_pool_elt (fp3_elt * dst, const fp3_param param, uint8_t stack);
105 
106 /************************************SETTERS**********************************/
107 
114 void
115 fp3_alloc (fp3_param param, const fp_param base);
116 
125 void
126 fp3_create (fp3_param param, const fp_param base, fp_elt_srcptr non_residue, uint8_t stack);
127 
134 void
135 fp3_copy (fp3_param param_res, const fp3_param param);
136 
142 void
143 fp3_free (fp3_param param);
144 
151 void
152 fp3_get_characteristic (number_ptr c, const fp3_param param);
153 
160 void
161 fp3_get_size (number_ptr c, const fp3_param param);
162 
163 /*void*/
164 /*fp3_get_pm2 (char * str, const fp3_param param);*/
165 
172 void
173 fp3_elt_alloc (fp3_elt * dst, const fp3_param param);
174 
181 void
182 fp3_elt_init (fp3_elt_ptr dst, const fp3_param param);
183 
191 void
192 fp3_elt_copy (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
193 
199 void
200 fp3_elt_clear (fp3_elt * src);
201 
207 void
208 fp3_elt_free (fp3_elt * src);
209 
216 void
217 fp3_elt_set_one (fp3_elt_ptr dst, const fp3_param param);
218 
228 void
229 fp3_elt_set_ui (fp3_elt_ptr dst, const uint64_t src, const bool isreduced,
230  const fp3_param param, uint8_t stack);
231 
241 void
242 fp3_elt_set_number (fp3_elt_ptr dst, number_srcptr src, const bool isreduced,
243  const fp3_param param, uint8_t stack);
244 
252 void
253 fp3_elt_set_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param);
254 
266 void
267 fp3_elt_set (fp3_elt_ptr dst, number_srcptr src1, number_srcptr src2,
268  number_srcptr src3, const bool isreduced, const fp3_param param, uint8_t stack);
269 
279 void
280 fp3_elt_set_fp_elts (fp3_elt_ptr dst, fp_elt_srcptr src1, fp_elt_srcptr src2, fp_elt_srcptr src3, const fp3_param param);
281 
292 void
293 fp3_elt_set_str (fp3_elt_ptr dst, const char *str, const uint8_t base,
294  const bool isreduced, const fp3_param param, uint8_t stack);
295 
303 void
304 fp3_elt_random (fp3_elt_ptr dst, const fp3_param param, uint8_t stack);
305 
314 void
315 fp3_elt_lift (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
316 
325 void
326 fp3_str (char **str, const fp3_param param, const uint8_t base, uint8_t stack);
327 
338 void
339 fp3_elt_str (char **str, fp3_elt_srcptr src, const uint8_t base,
340  const bool lift, const fp3_param param, uint8_t stack);
341 
342 /*************************COMPARISON AND LOGICAL******************************/
343 
354 int8_t
355 fp3_elt_cmp_fp_elt (fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param);
356 
367 int8_t
368 fp3_elt_cmp (fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param);
369 
377 bool
378 fp3_elt_isone (fp3_elt_srcptr src, const fp3_param param);
379 
387 bool
388 fp3_elt_iszero (fp3_elt_srcptr src, const fp3_param param);
389 
390 /***************************ADDITION SUBTRACTION******************************/
391 
399 void
400 fp3_elt_inc (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
401 
410 void
411 fp3_elt_add_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
412  const fp3_param param);
413 
422 void
424  const fp3_param param);
425 
433 void
434 fp3_elt_dec (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
435 
444 void
445 fp3_elt_sub_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
446  const fp3_param param);
447 
456 void
458  const fp3_param param);
459 
467 void
468 fp3_elt_neg_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param);
469 
477 void
478 fp3_elt_neg (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
479 
480 
481 /*******************************MULTIPLICATION********************************/
482 
492 void
493 fp3_elt_mul_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
494  const fp3_param param, uint8_t stack);
495 
503 void
505  const fp3_param param);
506 
514 void
516  const fp3_param param);
517 
525 void
527  const fp3_param param);
528 
537 void
539  const fp3_param param, uint8_t stack);
540 
550 void
552  const fp3_param param, uint8_t stack);
553 
562 void
563 fp3_elt_sqr_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack);
564 
572 void
573 fp3_elt_sqr (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
574 
582 void
583 fp3_elt_inv_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack);
584 
593 void
594 fp3_elt_inv (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
595 
605 void
606 fp3_elt_div_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
607  const fp3_param param, uint8_t stack);
608 
618 void
620  const fp3_param param, uint8_t stack);
621 
631 void
632 fp3_elt_pow_ui (fp3_elt_ptr dst, fp3_elt_srcptr src, const block n,
633  const fp3_param param, uint8_t stack);
634 
644 void
645 fp3_elt_pow_number (fp3_elt_ptr dst, fp3_elt_srcptr src, number_srcptr n,
646  const fp3_param param, uint8_t stack);
647 
656 bool
657 fp3_elt_issquare (fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
658 
670 int8_t
671 fp3_elt_ispower_ui (fp3_elt_srcptr src, const block n, const fp3_param param, uint8_t stack);
672 
684 int8_t
685 fp3_elt_ispower_number (fp3_elt_srcptr src, number_srcptr n,
686  const fp3_param param, uint8_t stack);
687 
696 void
697 fp3_elt_sqrt (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
698 
707 void
708 fp3_elt_cube_root (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
709 
718 void
719 fp3_elt_unity_nth_root (fp3_elt_ptr dst, const block n, const fp3_param param, uint8_t stack);
720 
721 #endif
722 
723 
724 
void fp3_alloc(fp3_param param, const fp_param base)
Allocate space for the cubic extension field informations structure.
Definition: mphell-fp3.c:69
void fp3_elt_mul2(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 2 * src.
Definition: mphell-fp3.c:465
void fp3_elt_get_pool_elt(fp3_elt *dst, const fp3_param param, uint8_t stack)
Allocate and initialise space for a temporary cubic extension field element.
Definition: mphell-fp3.c:51
void fp3_elt_inv(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^(-1)
Definition: mphell-fp3.c:580
void fp3_elt_init(fp3_elt_ptr dst, const fp3_param param)
Initialise a cubic extension field element.
Definition: mphell-fp3.c:182
void fp3_elt_cube_root(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^(1/3)
Definition: mphell-fp3.c:910
fp_elt v1
Definition: mphell-fp3.h:38
void fp3_elt_pow_ui(fp3_elt_ptr dst, fp3_elt_srcptr src, const block n, const fp3_param param, uint8_t stack)
Set dst <- src^n.
Definition: mphell-fp3.c:646
void fp3_get_size(number_ptr c, const fp3_param param)
Get the size of the cubic extension field "param".
Definition: mphell-fp3.c:162
void fp3_elt_div_fp_elt(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param, uint8_t stack)
Set dst <- src1 / src2.
Definition: mphell-fp3.c:624
void fp3_elt_set_fp_elt(fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param)
Set dst to src.
Definition: mphell-fp3.c:240
const fp3_elt_t * fp3_elt_srcptr
Define fp3_elt_srcptr, use in all functions where the parameter is const.
Definition: mphell-fp3.h:58
void fp3_elt_alloc(fp3_elt *dst, const fp3_param param)
Allocate space for a cubic extension field element.
Definition: mphell-fp3.c:174
void fp3_elt_set_one(fp3_elt_ptr dst, const fp3_param param)
Set dst to one (or its Montgomery form if Montgomery arithmetic is used)
Definition: mphell-fp3.c:214
void fp3_elt_sqrt(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^(1/2), using Tonelli–Shanks algorithm.
Definition: mphell-fp3.c:833
fp_elt v2
Definition: mphell-fp3.h:39
void fp3_copy(fp3_param param_res, const fp3_param param)
Copy the cubic extension field structure param into param_res.
Definition: mphell-fp3.c:131
fp_elt v0
Definition: mphell-fp3.h:37
void fp3_elt_mul4(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 4 * src.
Definition: mphell-fp3.c:474
fp_param_t * base
Definition: mphell-fp3.h:66
void fp3_elt_sqr(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^2.
Definition: mphell-fp3.c:566
bool fp3_elt_isone(fp3_elt_srcptr src, const fp3_param param)
Test if src is one.
Definition: mphell-fp3.c:370
int8_t fp3_elt_ispower_number(fp3_elt_srcptr src, number_srcptr n, const fp3_param param, uint8_t stack)
Test if src is a n-power in FP3, using A NOTE ON POWERS IN FINITE FIELDS from ANDREAS AABRANDT AND VA...
Definition: mphell-fp3.c:767
void fp3_elt_relax_pool_elt(fp3_elt *dst, const fp3_param param, uint8_t stack)
Free space of a temporary cubic extension field element.
Definition: mphell-fp3.c:59
number q
Definition: mphell-fp3.h:68
void fp3_get_characteristic(number_ptr c, const fp3_param param)
Get the characteristic of the cubic extension field "param".
Definition: mphell-fp3.c:156
void fp3_elt_dec(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- src - 1.
Definition: mphell-fp3.c:412
void fp3_elt_set_number(fp3_elt_ptr dst, number_srcptr src, const bool isreduced, const fp3_param param, uint8_t stack)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp3.c:231
void fp3_elt_str(char **str, fp3_elt_srcptr src, const uint8_t base, const bool lift, const fp3_param param, uint8_t stack)
Converts src to string format in base specified by base.
Definition: mphell-fp3.c:321
void fp3_elt_sub_fp_elt(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param)
Set dst <- src1 - src2.
Definition: mphell-fp3.c:420
void fp3_str(char **str, const fp3_param param, const uint8_t base, uint8_t stack)
Converts fp2_param param to string format in base specified by base.
Definition: mphell-fp3.c:301
fp3_param_t * fp3_param
Address of a cubic extension field structure.
Definition: mphell-fp3.h:82
void fp3_elt_inv_fp_elt(fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^(-1)
Definition: mphell-fp3.c:572
void fp3_elt_add(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param)
Set dst <- src1 + src2.
Definition: mphell-fp3.c:403
void fp3_elt_set_ui(fp3_elt_ptr dst, const uint64_t src, const bool isreduced, const fp3_param param, uint8_t stack)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp3.c:222
void fp3_elt_add_fp_elt(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param)
Set dst <- src1 + src2.
Definition: mphell-fp3.c:394
int8_t fp3_elt_cmp_fp_elt(fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param)
Compare src1 and src2 in FP3.
Definition: mphell-fp3.c:338
fp3_elt non_res
Definition: mphell-fp3.h:70
Cubic extension field element structure.
Definition: mphell-fp3.h:35
void fp3_elt_mul8(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 8 * src.
Definition: mphell-fp3.c:483
void fp3_elt_mul(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param, uint8_t stack)
Set dst <- src1 * src2, if Montgomery arithmetic is used, the Montgomery multiplication will be used ...
Definition: mphell-fp3.c:501
void fp3_elt_set_str(fp3_elt_ptr dst, const char *str, const uint8_t base, const bool isreduced, const fp3_param param, uint8_t stack)
Set dst to str, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-fp3.c:265
void fp3_elt_unity_nth_root(fp3_elt_ptr dst, const block n, const fp3_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-fp3.c:1099
fp_elt non_residue
Definition: mphell-fp3.h:67
uint8_t size
Definition: mphell-fp3.h:74
void fp3_elt_mul_fp_elt(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param, uint8_t stack)
Set dst <- src1 * src2, if Montgomery arithmetic is used, the Montgomery multiplication will be used ...
Definition: mphell-fp3.c:456
void fp3_elt_clear(fp3_elt *src)
Clear space used by src (remove the action of fp3_elt_init but let the one of fp3_elt_alloc)
Definition: mphell-fp3.c:198
void fp3_elt_sqr_fp_elt(fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- src^2.
Definition: mphell-fp3.c:558
void fp3_elt_set_fp_elts(fp3_elt_ptr dst, fp_elt_srcptr src1, fp_elt_srcptr src2, fp_elt_srcptr src3, const fp3_param param)
Set dst to src1 + src2*x + src3*x^2.
Definition: mphell-fp3.c:257
void fp3_create(fp3_param param, const fp_param base, fp_elt_srcptr non_residue, uint8_t stack)
Create a cubic extension of the field base.
Definition: mphell-fp3.c:108
Cubic extension field structure.
Definition: mphell-fp3.h:64
void fp3_elt_inc(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- src + 1.
Definition: mphell-fp3.c:386
void fp3_elt_sub(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param)
Set dst <- src1 - src2.
Definition: mphell-fp3.c:429
fp3_elt_t * fp3_elt_ptr
Define fp3_elt_ptr, use in all functions.
Definition: mphell-fp3.h:52
uint32_t p_even
Definition: mphell-fp3.h:73
void fp3_elt_div(fp3_elt_ptr dst, fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param, uint8_t stack)
Set dst <- src1 / src2.
Definition: mphell-fp3.c:635
Declaration of primary field functions, if Montgomery arithmetic is used, the Montgomery arithmetic w...
void fp3_elt_random(fp3_elt_ptr dst, const fp3_param param, uint8_t stack)
Set dst to a random element of FP3, the random process is chosen at the MHELL initialisation.
Definition: mphell-fp3.c:285
bool fp3_elt_iszero(fp3_elt_srcptr src, const fp3_param param)
Test if src is zero.
Definition: mphell-fp3.c:377
void fp3_elt_mul3(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
Set dst <- 3 * src.
Definition: mphell-fp3.c:492
number p_odd
Definition: mphell-fp3.h:72
void fp3_elt_copy(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Copy src into dst, src and dst must belong to the same FP3.
Definition: mphell-fp3.c:190
Primary field parameters.
fp3_elt_t fp3_elt
Cubic extension field element structure.
Definition: mphell-fp3.h:46
fp3_elt gen_sylow
Definition: mphell-fp3.h:71
void fp3_elt_set(fp3_elt_ptr dst, number_srcptr src1, number_srcptr src2, number_srcptr src3, const bool isreduced, const fp3_param param, uint8_t stack)
Set dst to src1 + src2*x + src3*x^2, if Montgomery arithmetic is used, is_reduced == false -> transfo...
Definition: mphell-fp3.c:248
void fp3_elt_lift(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack)
If Montgomery arithmetic is used, lift src (which is into Montgomery form) to classical FP3.
Definition: mphell-fp3.c:293
int8_t fp3_elt_cmp(fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param)
Compare src1 and src2 in FP3.
Definition: mphell-fp3.c:348
void fp3_elt_neg(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- (-src)
Definition: mphell-fp3.c:446
void fp3_elt_pow_number(fp3_elt_ptr dst, fp3_elt_srcptr src, number_srcptr n, const fp3_param param, uint8_t stack)
Set dst <- src^n.
Definition: mphell-fp3.c:669
void fp3_free(fp3_param param)
Free the space of the cubic extension field informations structure.
Definition: mphell-fp3.c:143
int8_t fp3_elt_ispower_ui(fp3_elt_srcptr src, const block n, const fp3_param param, uint8_t stack)
Test if src is a n-power in FP3, using A NOTE ON POWERS IN FINITE FIELDS from ANDREAS AABRANDT AND VA...
Definition: mphell-fp3.c:726
void fp3_elt_free(fp3_elt *src)
Free space used by src.
Definition: mphell-fp3.c:206
bool fp3_elt_issquare(fp3_elt_srcptr src, const fp3_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-fp3.c:708
void fp3_elt_neg_fp_elt(fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param)
Set dst <- (-src)
Definition: mphell-fp3.c:438