Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
mnt4_init.cpp
Go to the documentation of this file.
1 
17 
18 namespace libff
19 {
20 
21 // bigint<mnt4_r_limbs> mnt4_modulus_r = mnt46_modulus_A;
22 // bigint<mnt4_q_limbs> mnt4_modulus_q = mnt46_modulus_B;
23 
33 
40 
42 {
43  typedef bigint<mnt4_r_limbs> bigint_r;
44  typedef bigint<mnt4_q_limbs> bigint_q;
45 
46  assert(
47  sizeof(mp_limb_t) == 8 ||
48  sizeof(mp_limb_t) == 4); // Montgomery assumes this
49 
50  /* parameters for scalar field Fr */
51  mnt4_modulus_r = bigint_r("475922286169261325753349249653048451545124878552"
52  "823515553267735739164647307408490559963137");
53  assert(mnt4_Fr::modulus_is_valid());
54  if (sizeof(mp_limb_t) == 8) {
56  bigint_r("163983144722506446826715124368972380525894397127205577781"
57  "234305496325861831001705438796139");
59  bigint_r("207236281459091063710247635236340312578688659363066707916"
60  "716212805695955118593239854980171");
61  mnt4_Fr::inv = 0xbb4334a3ffffffff;
62  }
63  if (sizeof(mp_limb_t) == 4) {
65  bigint_r("163983144722506446826715124368972380525894397127205577781"
66  "234305496325861831001705438796139");
68  bigint_r("207236281459091063710247635236340312578688659363066707916"
69  "716212805695955118593239854980171");
70  mnt4_Fr::inv = 0xffffffff;
71  }
72  mnt4_Fr::num_bits = 298;
73  mnt4_Fr::euler = bigint_r("237961143084630662876674624826524225772562439276"
74  "411757776633867869582323653704245279981568");
75  mnt4_Fr::s = 34;
76  mnt4_Fr::t = bigint_r("2770232305450256248897344628657729199302411164115319"
77  "9339359284829066871159442729");
79  bigint_r("1385116152725128124448672314328864599651205582057659966967964"
80  "2414533435579721364");
83  mnt4_Fr("12063881782691317345876882948569009984537700803089161801010977"
84  "2937363554409782252579816313");
85  mnt4_Fr::nqr = mnt4_Fr("5");
86  mnt4_Fr::nqr_to_t = mnt4_Fr("4062206042430904010564294587302981459372625525"
87  "08985450684842547562990900634752279902740880");
89 
90  /* parameters for base field Fq */
91  mnt4_modulus_q = bigint_q("475922286169261325753349249653048451545124879242"
92  "694725395555128576210262817955800483758081");
93  assert(mnt4_Fq::modulus_is_valid());
94  if (sizeof(mp_limb_t) == 8) {
96  bigint_q("273000478523237720910981655601160860640083126627235719712"
97  "980612296263966512828033847775776");
99  bigint_q("427298980065529822574935274648041073124704261331681436071"
100  "990730954930769758106792920349077");
101  mnt4_Fq::inv = 0xb071a1b67165ffff;
102  }
103  if (sizeof(mp_limb_t) == 4) {
105  bigint_q("273000478523237720910981655601160860640083126627235719712"
106  "980612296263966512828033847775776");
108  bigint_q("427298980065529822574935274648041073124704261331681436071"
109  "990730954930769758106792920349077");
110  mnt4_Fq::inv = 0x7165ffff;
111  }
112  mnt4_Fq::num_bits = 298;
113  mnt4_Fq::euler = bigint_q("237961143084630662876674624826524225772562439621"
114  "347362697777564288105131408977900241879040");
115  mnt4_Fq::s = 17;
116  mnt4_Fq::t = bigint_q("3630998887399759870554727551674258816109656366292531"
117  "779446068791017229177993437198515");
119  bigint_q("1815499443699879935277363775837129408054828183146265889723034"
120  "395508614588996718599257");
123  mnt4_Fq("26470625057180008075806930236965430553012567552126397603405487"
124  "8017580902343339784464690243");
125  mnt4_Fq::nqr = mnt4_Fq("17");
126  mnt4_Fq::nqr_to_t = mnt4_Fq("2647062505718000807580693023696543055301256755"
127  "21263976034054878017580902343339784464690243");
129 
130  /* parameters for twist field Fq2 */
132  "1132510112362881350982493452491542308959143818587889181068472142434191"
133  "4242292413349746081746824985483306726003898571037009192086083701428188"
134  "6963086681184370139950267830740466401280");
135  mnt4_Fq2::s = 18;
137  "8640366457846689994678447360927904578850889729216683815524842395280391"
138  "1150302225873917249655341991297200973540485924049447571457547770905980"
139  "6542104196047745818712370534824115");
141  "4320183228923344997339223680463952289425444864608341907762421197640195"
142  "5575151112936958624827670995648600486770242962024723785728773885452990"
143  "3271052098023872909356185267412057");
145  mnt4_Fq2::nqr = mnt4_Fq2(mnt4_Fq("8"), mnt4_Fq("1"));
147  mnt4_Fq("0"),
148  mnt4_Fq("29402818985595053196743631544512156561638230562612542604956687"
149  "802791427330205135130967658"));
152  mnt4_Fq("47592228616926132575334924965304845154512487924269472539555512"
153  "8576210262817955800483758080");
155 
156  /* parameters for Fq4 */
160  mnt4_Fq("76841632454535016156213515524733370693010820609768050046250116"
161  "94147890954040864167002308");
163  mnt4_Fq("47592228616926132575334924965304845154512487924269472539555512"
164  "8576210262817955800483758080");
166  mnt4_Fq("46823812292380782413772789810057511447582379718171792039093011"
167  "6882062371863914936316755773");
168 
169  /* choice of short Weierstrass curve and its twist */
170  mnt4_G1::coeff_a = mnt4_Fq("2");
171  mnt4_G1::coeff_b = mnt4_Fq("42389453652668417828941601153388824002931810367"
172  "3896002803341544124054745019340795360841685");
186  mnt4_Fq("47592228616926132575334924965304845154512487924269472539555512"
187  "8576210262817955800483758080");
189  mnt4_Fq("76841632454535016156213515524733370693010820609768050046250116"
190  "94147890954040864167002308");
191 
192  /* choice of group G1 */
193  // Identities
197  mnt4_Fq("60760244141852568949126569781626075788424196370144486719385562"
198  "369396875346601926534016838"),
199  mnt4_Fq("36373285070258297826390277081514578445974772235707184397110767"
200  "4179038674942891694705904306"),
201  mnt4_Fq::one());
202 
203  // Cofactor
205 
206  // WNAF
207  mnt4_G1::wnaf_window_table.resize(0);
208  mnt4_G1::wnaf_window_table.push_back(11);
209  mnt4_G1::wnaf_window_table.push_back(24);
210  mnt4_G1::wnaf_window_table.push_back(60);
211  mnt4_G1::wnaf_window_table.push_back(127);
212 
214  // window 1 is unbeaten in [-inf, 5.09]
216  // window 2 is unbeaten in [5.09, 9.64]
218  // window 3 is unbeaten in [9.64, 24.79]
220  // window 4 is unbeaten in [24.79, 60.29]
222  // window 5 is unbeaten in [60.29, 144.37]
224  // window 6 is unbeaten in [144.37, 344.90]
226  // window 7 is unbeaten in [344.90, 855.00]
228  // window 8 is unbeaten in [855.00, 1804.62]
230  // window 9 is unbeaten in [1804.62, 3912.30]
231  mnt4_G1::fixed_base_exp_window_table.push_back(1805);
232  // window 10 is unbeaten in [3912.30, 11264.50]
233  mnt4_G1::fixed_base_exp_window_table.push_back(3912);
234  // window 11 is unbeaten in [11264.50, 27897.51]
235  mnt4_G1::fixed_base_exp_window_table.push_back(11265);
236  // window 12 is unbeaten in [27897.51, 57596.79]
237  mnt4_G1::fixed_base_exp_window_table.push_back(27898);
238  // window 13 is unbeaten in [57596.79, 145298.71]
239  mnt4_G1::fixed_base_exp_window_table.push_back(57597);
240  // window 14 is unbeaten in [145298.71, 157204.59]
241  mnt4_G1::fixed_base_exp_window_table.push_back(145299);
242  // window 15 is unbeaten in [157204.59, 601600.62]
243  mnt4_G1::fixed_base_exp_window_table.push_back(157205);
244  // window 16 is unbeaten in [601600.62, 1107377.25]
245  mnt4_G1::fixed_base_exp_window_table.push_back(601601);
246  // window 17 is unbeaten in [1107377.25, 1789646.95]
247  mnt4_G1::fixed_base_exp_window_table.push_back(1107377);
248  // window 18 is unbeaten in [1789646.95, 4392626.92]
249  mnt4_G1::fixed_base_exp_window_table.push_back(1789647);
250  // window 19 is unbeaten in [4392626.92, 8221210.60]
251  mnt4_G1::fixed_base_exp_window_table.push_back(4392627);
252  // window 20 is unbeaten in [8221210.60, 42363731.19]
253  mnt4_G1::fixed_base_exp_window_table.push_back(8221211);
254  // window 21 is never the best
256  // window 22 is unbeaten in [42363731.19, inf]
257  mnt4_G1::fixed_base_exp_window_table.push_back(42363731);
258 
259  /* choice of group G2 */
260  // Identities
264  mnt4_Fq2(
265  mnt4_Fq("4383749262193500998549191000778096818427835091637909918478"
266  "67546339851681564223481322252708"),
267  mnt4_Fq("3762095361550048011093551436092327860546447645971239327767"
268  "9280819942849043649216370485641")),
269  mnt4_Fq2(
270  mnt4_Fq("3743740900852896826835252103493693184297354644137066311854"
271  "3015118291998305624025037512482"),
272  mnt4_Fq("4246214795988938826723931903374206805975846958923171976461"
273  "13820787463109735345923009077489")),
274  mnt4_Fq2::one());
275 
276  // Cofactor
278  "4759222861692613257533492496530484515451248799325659352378425214132558"
279  "78328503110407553025");
280 
281  // WNAF
282  mnt4_G2::wnaf_window_table.resize(0);
283  mnt4_G2::wnaf_window_table.push_back(5);
284  mnt4_G2::wnaf_window_table.push_back(15);
285  mnt4_G2::wnaf_window_table.push_back(39);
286  mnt4_G2::wnaf_window_table.push_back(109);
287 
289  // window 1 is unbeaten in [-inf, 4.17]
291  // window 2 is unbeaten in [4.17, 10.12]
293  // window 3 is unbeaten in [10.12, 24.65]
295  // window 4 is unbeaten in [24.65, 60.03]
297  // window 5 is unbeaten in [60.03, 143.16]
299  // window 6 is unbeaten in [143.16, 344.73]
301  // window 7 is unbeaten in [344.73, 821.24]
303  // window 8 is unbeaten in [821.24, 1793.92]
305  // window 9 is unbeaten in [1793.92, 3919.59]
306  mnt4_G2::fixed_base_exp_window_table.push_back(1794);
307  // window 10 is unbeaten in [3919.59, 11301.46]
308  mnt4_G2::fixed_base_exp_window_table.push_back(3920);
309  // window 11 is unbeaten in [11301.46, 18960.09]
310  mnt4_G2::fixed_base_exp_window_table.push_back(11301);
311  // window 12 is unbeaten in [18960.09, 44198.62]
312  mnt4_G2::fixed_base_exp_window_table.push_back(18960);
313  // window 13 is unbeaten in [44198.62, 150799.57]
314  mnt4_G2::fixed_base_exp_window_table.push_back(44199);
315  // window 14 is never the best
317  // window 15 is unbeaten in [150799.57, 548694.81]
318  mnt4_G2::fixed_base_exp_window_table.push_back(150800);
319  // window 16 is unbeaten in [548694.81, 1051769.08]
320  mnt4_G2::fixed_base_exp_window_table.push_back(548695);
321  // window 17 is unbeaten in [1051769.08, 2023925.59]
322  mnt4_G2::fixed_base_exp_window_table.push_back(1051769);
323  // window 18 is unbeaten in [2023925.59, 3787108.68]
324  mnt4_G2::fixed_base_exp_window_table.push_back(2023926);
325  // window 19 is unbeaten in [3787108.68, 7107480.30]
326  mnt4_G2::fixed_base_exp_window_table.push_back(3787109);
327  // window 20 is unbeaten in [7107480.30, 38760027.14]
328  mnt4_G2::fixed_base_exp_window_table.push_back(7107480);
329  // window 21 is never the best
331  // window 22 is unbeaten in [38760027.14, inf]
332  mnt4_G2::fixed_base_exp_window_table.push_back(38760027);
333 
334  /* pairing parameters */
336  bigint_q("689871209842287392837045615510547309923794944");
339  "1077973603571099034307944903095920722789277838030318543579109081219034"
340  "3983877286149717711641082558674308976086994539461051191727497797155906"
341  "2689561855016270594656570874331111995170645233717143416875749097203441"
342  "437192367065467706065411650403684877366879441766585988546560");
344  bigint_q("689871209842287392837045615510547309923794945");
346  mnt4_final_exponent_last_chunk_w1 = bigint_q("1");
347 }
348 
349 } // namespace libff
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::euler
static bigint< 2 *n > euler
(modulus^2-1)/2
Definition: fp2.hpp:46
libff::mnt4_Fr
Fp_model< mnt4_r_limbs, mnt4_modulus_r > mnt4_Fr
Definition: mnt4_init.hpp:36
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::nqr_to_t
static Fp2_model< n, modulus > nqr_to_t
nqr^t
Definition: fp2.hpp:59
libff::mnt4_twist_mul_by_b_c1
mnt4_Fq mnt4_twist_mul_by_b_c1
Definition: mnt4_init.cpp:30
libff::mnt4_twist_coeff_b
mnt4_Fq2 mnt4_twist_coeff_b
Definition: mnt4_init.cpp:26
libff::mnt4_twist_mul_by_a_c1
mnt4_Fq mnt4_twist_mul_by_a_c1
Definition: mnt4_init.cpp:28
libff::mnt4_G2
Definition: mnt4_g2.hpp:26
libff::mnt4_G2::G2_one
static mnt4_G2 G2_one
Definition: mnt4_g2.hpp:36
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::t_minus_1_over_2
static bigint< 2 *n > t_minus_1_over_2
(t-1)/2
Definition: fp2.hpp:52
libff
Definition: ffi.cpp:8
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::one
static const Fp2_model< n, modulus > & one()
libff::mnt4_G2::h
static bigint< h_limbs > h
Definition: mnt4_g2.hpp:49
libff::Fp_model::squared
Fp_model squared() const
libff::mnt4_twist_coeff_a
mnt4_Fq2 mnt4_twist_coeff_a
Definition: mnt4_init.cpp:25
libff::Fp_model::nqr
static Fp_model< n, modulus > nqr
a quadratic nonresidue
Definition: fp.hpp:70
libff::mnt4_G2::coeff_b
static mnt4_Fq2 coeff_b
Definition: mnt4_g2.hpp:39
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >::zero
static const Fp_model< n, modulus > & zero()
libff::Fp_model::t
static bigint< n > t
with t odd
Definition: fp.hpp:66
libff::mnt4_G2::twist
static mnt4_Fq2 twist
Definition: mnt4_g2.hpp:37
libff::mnt4_final_exponent
bigint< 4 *mnt4_q_limbs > mnt4_final_exponent
Definition: mnt4_init.cpp:36
libff::Fp_model::s
static size_t s
modulus = 2^s * t + 1
Definition: fp.hpp:64
libff::mnt4_G1
Definition: mnt4_g1.hpp:26
libff::init_mnt4_params
void init_mnt4_params()
Definition: mnt4_init.cpp:41
libff::Fp4_model::non_residue
static my_Fp non_residue
Definition: fp4.hpp:50
libff::mnt4_G1::G1_one
static mnt4_G1 G1_one
Definition: mnt4_g1.hpp:36
libff::mnt4_twist_mul_by_q_X
mnt4_Fq mnt4_twist_mul_by_q_X
Definition: mnt4_init.cpp:31
libff::mnt4_final_exponent_last_chunk_abs_of_w0
bigint< mnt4_q_limbs > mnt4_final_exponent_last_chunk_abs_of_w0
Definition: mnt4_init.cpp:37
libff::Fp_model::euler
static bigint< n > euler
(modulus-1)/2
Definition: fp.hpp:62
libff::Fp_model::modulus_is_valid
static bool modulus_is_valid()
Definition: fp.hpp:84
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >::one
static const Fp_model< n, modulus > & one()
libff::mnt4_Fq
Fp_model< mnt4_q_limbs, mnt4_modulus_q > mnt4_Fq
Definition: mnt4_init.hpp:37
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::Frobenius_coeffs_c1
static my_Fp Frobenius_coeffs_c1[2]
non_residue^((modulus^i-1)/2) for i=0,1
Definition: fp2.hpp:61
libff::mnt4_modulus_q
bigint< mnt4_q_limbs > mnt4_modulus_q
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::nqr
static Fp2_model< n, modulus > nqr
a quadratic nonresidue in Fp2
Definition: fp2.hpp:57
libff::mnt4_G1::coeff_a
static mnt4_Fq coeff_a
Definition: mnt4_g1.hpp:37
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::static_init
static void static_init()
libff::mnt4_G1::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: mnt4_g1.hpp:34
libff::mnt4_G2::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: mnt4_g2.hpp:34
libff::Fp_model::t_minus_1_over_2
static bigint< n > t_minus_1_over_2
(t-1)/2
Definition: fp.hpp:68
libff::mnt4_G2::G2_zero
static mnt4_G2 G2_zero
Definition: mnt4_g2.hpp:35
libff::bigint
Definition: bigint.hpp:20
libff::mnt4_Fq2
Fp2_model< mnt4_q_limbs, mnt4_modulus_q > mnt4_Fq2
Definition: mnt4_init.hpp:38
libff::Fp_model::static_init
static void static_init()
libff::Fp_model::root_of_unity
static Fp_model< n, modulus > root_of_unity
generator^((modulus-1)/2^s)
Definition: fp.hpp:76
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::non_residue
static my_Fp non_residue
Definition: fp2.hpp:55
mnt4_init.hpp
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >
libff::mnt4_ate_loop_count
bigint< mnt4_q_limbs > mnt4_ate_loop_count
Definition: mnt4_init.cpp:34
libff::mnt4_G1::coeff_b
static mnt4_Fq coeff_b
Definition: mnt4_g1.hpp:38
libff::mnt4_G1::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: mnt4_g1.hpp:33
mnt4_g2.hpp
libff::mnt4_ate_is_loop_count_neg
bool mnt4_ate_is_loop_count_neg
Definition: mnt4_init.cpp:35
libff::mnt4_G2::coeff_a
static mnt4_Fq2 coeff_a
Definition: mnt4_g2.hpp:38
libff::mnt4_twist_mul_by_b_c0
mnt4_Fq mnt4_twist_mul_by_b_c0
Definition: mnt4_init.cpp:29
libff::Fp_model::nqr_to_t
static Fp_model< n, modulus > nqr_to_t
nqr^t
Definition: fp.hpp:72
libff::Fp_model::multiplicative_generator
static Fp_model< n, modulus > multiplicative_generator
generator of Fp^*
Definition: fp.hpp:74
libff::mnt4_final_exponent_last_chunk_is_w0_neg
bool mnt4_final_exponent_last_chunk_is_w0_neg
Definition: mnt4_init.cpp:38
libff::Fp_model::num_bits
static size_t num_bits
Definition: fp.hpp:60
libff::mnt4_twist_mul_by_q_Y
mnt4_Fq mnt4_twist_mul_by_q_Y
Definition: mnt4_init.cpp:32
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >
libff::mnt4_modulus_r
bigint< mnt4_r_limbs > mnt4_modulus_r
libff::Fp_model::inv
static mp_limb_t inv
-modulus^(-1) mod W, where W = 2^(word size)
Definition: fp.hpp:78
libff::mnt4_final_exponent_last_chunk_w1
bigint< mnt4_q_limbs > mnt4_final_exponent_last_chunk_w1
Definition: mnt4_init.cpp:39
libff::Fp4_model::Frobenius_coeffs_c1
static my_Fp Frobenius_coeffs_c1[4]
non_residue^((modulus^i-1)/4) for i=0,1,2,3
Definition: fp4.hpp:52
libff::mnt4_G2::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: mnt4_g2.hpp:33
libff::mnt4_twist_mul_by_a_c0
mnt4_Fq mnt4_twist_mul_by_a_c0
Definition: mnt4_init.cpp:27
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::zero
static const Fp2_model< n, modulus > & zero()
libff::mnt4_G1::h
static bigint< h_limbs > h
Definition: mnt4_g1.hpp:47
libff::Fp_model::Rsquared
static bigint< n > Rsquared
R^2, where R = W^k, where k = ??
Definition: fp.hpp:80
libff::mnt4_twist
mnt4_Fq2 mnt4_twist
Definition: mnt4_init.cpp:24
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::t
static bigint< 2 *n > t
with t odd
Definition: fp2.hpp:50
libff::Fp2_model< mnt4_q_limbs, mnt4_modulus_q >::s
static size_t s
modulus^2 = 2^s * t + 1
Definition: fp2.hpp:48
mnt4_g1.hpp
libff::mnt4_G1::G1_zero
static mnt4_G1 G1_zero
Definition: mnt4_g1.hpp:35
libff::Fp_model::Rcubed
static bigint< n > Rcubed
R^3.
Definition: fp.hpp:82