MPHELL  5.0.0
mphell-fp3.h
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 #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 
225 void
226 fp3_elt_set_zero (fp3_elt_ptr dst, const fp3_param param);
227 
237 void
238 fp3_elt_set_ui (fp3_elt_ptr dst, const uint64_t src, const bool isreduced,
239  const fp3_param param, uint8_t stack);
240 
250 void
251 fp3_elt_set_number (fp3_elt_ptr dst, number_srcptr src, const bool isreduced,
252  const fp3_param param, uint8_t stack);
253 
261 void
262 fp3_elt_set_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param);
263 
275 void
276 fp3_elt_set (fp3_elt_ptr dst, number_srcptr src1, number_srcptr src2,
277  number_srcptr src3, const bool isreduced, const fp3_param param, uint8_t stack);
278 
288 void
289 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);
290 
301 void
302 fp3_elt_set_str (fp3_elt_ptr dst, const char *str, const uint8_t base,
303  const bool isreduced, const fp3_param param, uint8_t stack);
304 
312 void
313 fp3_elt_random (fp3_elt_ptr dst, const fp3_param param, uint8_t stack);
314 
323 void
324 fp3_elt_lift (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
325 
334 void
335 fp3_str (char **str, const fp3_param param, const uint8_t base, uint8_t stack);
336 
347 void
348 fp3_elt_str (char **str, fp3_elt_srcptr src, const uint8_t base,
349  const bool lift, const fp3_param param, uint8_t stack);
350 
351 /*************************COMPARISON AND LOGICAL******************************/
352 
363 int8_t
364 fp3_elt_cmp_fp_elt (fp3_elt_srcptr src1, fp_elt_srcptr src2, const fp3_param param);
365 
376 int8_t
377 fp3_elt_cmp (fp3_elt_srcptr src1, fp3_elt_srcptr src2, const fp3_param param);
378 
386 bool
387 fp3_elt_isone (fp3_elt_srcptr src, const fp3_param param);
388 
396 bool
397 fp3_elt_iszero (fp3_elt_srcptr src, const fp3_param param);
398 
399 /***************************ADDITION SUBTRACTION******************************/
400 
408 void
409 fp3_elt_inc (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
410 
419 void
420 fp3_elt_add_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
421  const fp3_param param);
422 
431 void
433  const fp3_param param);
434 
442 void
443 fp3_elt_dec (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
444 
453 void
454 fp3_elt_sub_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
455  const fp3_param param);
456 
465 void
467  const fp3_param param);
468 
476 void
477 fp3_elt_neg_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param);
478 
486 void
487 fp3_elt_neg (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param);
488 
489 
490 /*******************************MULTIPLICATION********************************/
491 
501 void
502 fp3_elt_mul_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
503  const fp3_param param, uint8_t stack);
504 
512 void
514  const fp3_param param);
515 
523 void
525  const fp3_param param);
526 
534 void
536  const fp3_param param);
537 
546 void
548  const fp3_param param, uint8_t stack);
549 
559 void
561  const fp3_param param, uint8_t stack);
562 
571 void
572 fp3_elt_sqr_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack);
573 
581 void
582 fp3_elt_sqr (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
583 
591 void
592 fp3_elt_inv_fp_elt (fp3_elt_ptr dst, fp_elt_srcptr src, const fp3_param param, uint8_t stack);
593 
602 void
603 fp3_elt_inv (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
604 
614 void
615 fp3_elt_div_fp_elt (fp3_elt_ptr dst, fp3_elt_srcptr src1, fp_elt_srcptr src2,
616  const fp3_param param, uint8_t stack);
617 
627 void
629  const fp3_param param, uint8_t stack);
630 
640 void
641 fp3_elt_pow_ui (fp3_elt_ptr dst, fp3_elt_srcptr src, const block n,
642  const fp3_param param, uint8_t stack);
643 
653 void
654 fp3_elt_pow_number (fp3_elt_ptr dst, fp3_elt_srcptr src, number_srcptr n,
655  const fp3_param param, uint8_t stack);
656 
665 bool
666 fp3_elt_issquare (fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
667 
679 int8_t
680 fp3_elt_ispower_ui (fp3_elt_srcptr src, const block n, const fp3_param param, uint8_t stack);
681 
693 int8_t
694 fp3_elt_ispower_number (fp3_elt_srcptr src, number_srcptr n,
695  const fp3_param param, uint8_t stack);
696 
705 void
706 fp3_elt_sqrt (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
707 
716 void
717 fp3_elt_cube_root (fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param, uint8_t stack);
718 
727 void
728 fp3_elt_unity_nth_root (fp3_elt_ptr dst, const block n, const fp3_param param, uint8_t stack);
729 
730 #endif
731 
732 
733 
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:776
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:215
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:347
void fp3_elt_mul8(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 8 * src.
Definition: mphell-fp3.c:492
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:717
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_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_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:199
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:257
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:249
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:310
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:403
void fp3_elt_mul2(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 2 * src.
Definition: mphell-fp3.c:474
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:302
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:240
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:447
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_free(fp3_elt *src)
Free space used by src.
Definition: mphell-fp3.c:207
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:655
void fp3_get_size(number_ptr c, const fp3_param param)
Get the size of the cubic extension field "param".
Definition: mphell-fp3.c:163
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:842
bool fp3_elt_isone(fp3_elt_srcptr src, const fp3_param param)
Test if src is one.
Definition: mphell-fp3.c:379
void fp3_elt_set_zero(fp3_elt_ptr dst, const fp3_param param)
Set dst to zero.
Definition: mphell-fp3.c:223
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:274
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:567
fp3_elt_t * fp3_elt_ptr
Define fp3_elt_ptr, use in all functions.
Definition: mphell-fp3.h:52
void fp3_elt_init(fp3_elt_ptr dst, const fp3_param param)
Initialise a cubic extension field element.
Definition: mphell-fp3.c:183
void fp3_elt_neg(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- (-src)
Definition: mphell-fp3.c:455
void fp3_elt_inc(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- src + 1.
Definition: mphell-fp3.c:395
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:294
void fp3_elt_mul4(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- 4 * src.
Definition: mphell-fp3.c:483
fp3_param_t * fp3_param
Address of a cubic extension field structure.
Definition: mphell-fp3.h:82
void fp3_elt_dec(fp3_elt_ptr dst, fp3_elt_srcptr src, const fp3_param param)
Set dst <- src - 1.
Definition: mphell-fp3.c:421
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:429
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:266
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:465
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:678
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
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:191
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:1108
void fp3_free(fp3_param param)
Free the space of the cubic extension field informations structure.
Definition: mphell-fp3.c:143
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
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:644
void fp3_elt_alloc(fp3_elt *dst, const fp3_param param)
Allocate space for a cubic extension field element.
Definition: mphell-fp3.c:175
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:330
fp3_elt_t fp3_elt
Cubic extension field element structure.
Definition: mphell-fp3.h:46
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:919
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:633
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:510
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:412
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:735
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:575
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:501
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:589
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
bool fp3_elt_iszero(fp3_elt_srcptr src, const fp3_param param)
Test if src is zero.
Definition: mphell-fp3.c:386
void fp3_get_characteristic(number_ptr c, const fp3_param param)
Get the characteristic of the cubic extension field "param".
Definition: mphell-fp3.c:157
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:231
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:581
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:438
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:357
Declaration of primary field functions, if Montgomery arithmetic is used, the Montgomery arithmetic w...
Cubic extension field element structure.
Definition: mphell-fp3.h:36
fp_elt v0
Definition: mphell-fp3.h:37
fp_elt v1
Definition: mphell-fp3.h:38
fp_elt v2
Definition: mphell-fp3.h:39
Cubic extension field structure.
Definition: mphell-fp3.h:65
fp3_elt non_res
Definition: mphell-fp3.h:70
uint32_t p_even
Definition: mphell-fp3.h:73
fp_param_t * base
Definition: mphell-fp3.h:66
fp_elt non_residue
Definition: mphell-fp3.h:67
number q
Definition: mphell-fp3.h:68
fp3_elt gen_sylow
Definition: mphell-fp3.h:71
uint8_t size
Definition: mphell-fp3.h:74
number p_odd
Definition: mphell-fp3.h:72
Primary field parameters.