First online: September 15, 2020,
Last updated: October 5, 2020.
Remarks on the version of September 13, 2020 of eprint 2019/485 (Barbulescu, El Mrabet and Ghammam)
Differences in the model of cost
As explained in the 2020 version of eprint 2019/485, the model of cost is slightly different from eprint 2019/885. The preprint 2019/485 makes use of the general formula (equation 1 Section 3.2)
csieve × (1/𝒜) × (number of (a, b) pairs) + clinear algebra × ((number of prime ideals on both sides)/(𝒜×cfilter))2
There are two sets of differences:
- Differences in the choices of csieve, cfilter and clinear algebra;
- Differences in the choices of approximations (in the implementation).
In eprint 2017/334 and 2019/485 the values are csieve = 1, cfilter = log2B and clinear algebra = 128;
In eprint 2019/431 and 2019/885 the values are csieve = ln ln B, cfilter = 20 and clinear algebra = 200⌈(log2r)/64⌉.
The preprint 2019/485 follows the estimates from Barbulescu–Duquesne first designed in eprint 2017/334. The implementation choices are the following.
- The number of pairs (a,b) is upper bounded by (2A + 1)2deg h/(2w) where w is the number of units up to sign in Kh, and lower bounded by
(number of prime ideals on both sides) × ρ((log2Nf)/(log2B)) − 1ρ((log2Ng)/(log2B)) − 1
- An approximation of the number of distinct prime ideals of norm up to B is the number of prime integers up to B, which is B/ln B where B is the smoothness bound
- The (a, b) pairs are randomly sampled with
randint(-A,A+1)
in Python
- The norms Nf, Ng are averaged before computing the Dickman-rho function on the average norms: ρ(log2(averaged Nf)/log2B)ρ(log2(averaged Ng)/log2B)
- It is considered that α(f, h) = 0.0 and α(g, h) = 0.0
- The smoothness probability of the norms is approximated with the first order term ρ(log2Nf/log2B)ρ(log2Ng/log2B)
- 25600 random pairs are sampled to compute the average norms (3000 in eprint 2019/485)
Later in 2019 the implementation choices were refined with the following tricks.
- The number of (a, b) pairs is estimated to be (2A + 1)2deg h/(2wζKh(2)) where 1/ζKh(2) allows to account for the duplicates due to non-coprime ideals
- The number of distinct prime ideals of norm up to B is approximated with the formula LogIntegral(B) that is more accurate than B/ln B for large values of B
- The (a, b) pairs are randomly sampled with
randint(-A,A)
or randrange(-A,A+1)
in Python
- The average is made on the Dickman-rho values instead of the norms
- The exact value of α(f, h) and α(g, h) is computed, and polynomials are chosen to optimise α
- Two terms are involved in the smoothness estimate as in Murphy’s thesis: uf = (ln Nf + α(f, h))/ln B and Prf = ρ(uf) + (1 − γ)ρ(uf − 1)/ln Nf and the same on g side
- 105 to 106 random samples are used to compute the averages.
Tables of seeds
The Tables 10 to 17 at the end of the paper are mostly taken from the version of 2019 despite typos, wrong seeds and wrong security levels reported in eprint 2019/1371 and communicated to the authors on August 20, 2019. The following data is generated with this SageMath script. Because the tables below are generated from a script, the seeds are given in hexadecimal and 2-NAF form, and sparse form if it is short. Sometimes the 2-NAF form does not match exactly the sparse form given in eprint 2019/485 because it is not a 2-NAF form but another signed binary sparse representation. The seeds in the SageMath script are copied from the preprint.
The estimated security in Fpk is from eprint 2019/1371 Tables 4 and 10 in the version of December 6, 2019 (Table 10 was later removed in the version of February 2020 to fit in the 30 pages of the published version).
Some seeds for KSS do not provide integer values of p and r. Some seeds for k=27 and D=-3 are wrong. There are two families with D=-3 for k=27, construction 6.6 from Freeman, Scott, Teske (DOI 10.1007/s00145-009-9048-z, eprint 2006/372) and a BLS-like construction, with trace t(x) = x+1. It seems that the polynomials p(x) and r(x) from these two families were mixed when generating seeds, though the polynomials are correct in the paper.
Table 10 construction 6.2 k=1 mod 2
6.2 |
9 |
0x400637 |
222+210+29+25+24+22+2+1 |
222+211-29+26-23-1 |
483 |
265 |
4339 |
116 |
6.2 |
11 |
0x40ff |
|
214+28-1 |
363 |
281 |
3989 |
122 |
6.2 |
13 |
0x10451b |
220+214+210+28+24+23+2+1 |
220+214+210+28+25-22-1 |
599 |
481 |
7784 |
162 |
Table 10 construction 6.3 k=2 mod 4
6.3 |
10 |
0x18000000119 |
240+239+28+24+23+1 |
241-239+28+25-23+1 |
567 |
325 |
5662 |
Error p is not prime Error r is not prime |
6.3 |
14 |
0x37723d |
|
222-219-215-212+29+26-22+1 |
391 |
262 |
5464 |
131 |
6.3 |
18 |
0x4035ab |
222+213+212+210+28+27+25+23+2+1 |
222+214-211-29-26-24-22-1 |
483 |
265 |
8678 |
|
6.3 |
22 |
0xc013 |
215+214+24+2+1 |
216-214+24+22-1 |
404 |
312 |
8871 |
|
6.3 |
26 |
0x1101 |
212+28+1 |
212+28+1 |
361 |
291 |
9377 |
|
6.3 |
30 |
0x13c0d |
216+213+212+211+210+23+22+1 |
216+214-210+24-22+1 |
553 |
261 |
16571 |
|
6.3 |
34 |
0x43f1 |
|
214+210-24+1 |
534 |
451 |
18132 |
|
6.3 |
38 |
0x20a09 |
217+211+29+23+1 |
217+211+29+23+1 |
714 |
614 |
27101 |
|
6.3 |
42 |
0xd91 |
211+210+28+27+24+1 |
212-29-27+24+1 |
540 |
283 |
22641 |
|
6.3 |
46 |
0x2603 |
213+210+29+2+1 |
213+211-29+22-1 |
661 |
583 |
30380 |
|
6.3 |
50 |
0x4b91 |
214+211+29+28+27+24+1 |
214+212-210-27+24+1 |
767 |
570 |
38348 |
|
6.3 |
54 |
0xb2b |
211+29+28+25+23+2+1 |
212-210-28+26-24-22-1 |
664 |
414 |
35852 |
|
Table 10 construction 6.4 k=4 mod 8
6.4 |
12 |
0x10000000000000b0b |
264+211+29+28+23+2+1 |
264+212-210-28+24-22-1 |
511 |
257 |
6121 |
138 |
6.4 |
20 |
0x100010011 |
232+216+24+1 |
232+216+24+1 |
383 |
257 |
7641 |
|
6.4 |
28 |
0x40031b |
222+29+28+24+23+2+1 |
222+210-28+25-22-1 |
351 |
265 |
9801 |
|
6.4 |
36 |
0x414405 |
222+216+214+210+22+1 |
222+216+214+210+22+1 |
439 |
265 |
15789 |
|
6.4 |
44 |
0x5181 |
214+212+28+27+1 |
214+212+29-27+1 |
343 |
287 |
15065 |
|
6.4 |
52 |
0x31c1 |
213+212+28+27+26+1 |
214-212+29-26+1 |
380 |
328 |
19752 |
|
Table 10 construction 6.7 even k
6.7 |
12 |
0x100024001 |
232+217+214+1 |
232+217+214+1 |
446 |
257 |
5341 |
134 |
6.7 |
24 |
0x100000305 |
232+29+28+22+1 |
232+210-28+22+1 |
382 |
257 |
9145 |
|
6.7 |
30 |
0xfa3 |
211+210+29+28+27+25+2+1 |
212-27+25+22-1 |
692 |
383 |
20733 |
|
6.7 |
36 |
0x12729 |
216+213+210+29+28+25+23+1 |
216+213+211-28+25+23+1 |
548 |
389 |
19728 |
|
6.7 |
48 |
0x1004569 |
224+214+210+28+26+25+23+1 |
224+214+211-29-27-25+23+1 |
526 |
385 |
25202 |
|
Table 10 construction 6.7 odd k
6.7 |
9 |
0xa2f |
211+29+25+23+22+2+1 |
211+29+26-24-1 |
520 |
273 |
4672 |
140 |
6.7 |
15 |
0x5695 |
214+212+210+29+27+24+22+1 |
215-213-211-29+27+24+22+1 |
950 |
462 |
14247 |
|
6.7 |
21 |
0x1c93 |
212+211+210+27+24+2+1 |
213-210+27+24+22-1 |
1101 |
617 |
23120 |
|
6.7 |
27 |
0xb7d |
|
212-210-27-22+1 |
1219 |
830 |
32896 |
|
Table 11 construction 6.6 k=0 mod 6
6.6 |
12 |
-0x1ffffffbfffe00000000 |
|
-(-277+250+233) |
461 |
308 |
5525 |
134 |
6.6 |
24 |
-0xeffff000 |
|
-(-232+228+212) |
318 |
256 |
7620 |
162 |
6.6 |
30 |
0x100006009 |
232+214+213+23+1 |
232+215-213+23+1 |
383 |
257 |
11473 |
|
6.6 |
42 |
-0x3bffc0 |
|
-(-222+218+26) |
349 |
263 |
14655 |
|
6.6 |
48 |
0x16840 |
216+214+213+211+26 |
217-215-213+211+26 |
296 |
264 |
14174 |
|
Table 11 construction 6.6 k=2,4 mod 6
6.6 |
14 |
0x4226bf |
|
222+217+213+211-28-26-1 |
352 |
265 |
4917 |
150 |
6.6 |
16 |
0x1c768 |
216+215+214+210+29+28+26+25+23 |
217-214+211-27-25+23 |
369 |
270 |
5900 |
|
6.6 |
20 |
0x20041 |
217+26+1 |
217+26+1 |
373 |
273 |
7449 |
|
6.6 |
22 |
0x20020 |
217+25 |
217+25 |
475 |
341 |
10438 |
|
6.6 |
26 |
0x60ac |
214+213+27+25+23+22 |
215-213+28-26-24-22 |
408 |
351 |
10584 |
|
6.6 |
28 |
0x457c |
214+210+28+26+25+24+23+22 |
214+211-29-27-22 |
479 |
339 |
13397 |
|
6.6 |
32 |
0x232 |
29+25+24+2 |
29+26-24+2 |
309 |
293 |
9888 |
|
6.6 |
34 |
0x42a |
210+25+23+2 |
210+25+23+2 |
401 |
322 |
13625 |
|
6.6 |
38 |
0x4d5 |
210+27+26+24+22+1 |
210+28-26+24+22+1 |
410 |
370 |
15555 |
|
6.6 |
40 |
0x478 |
210+26+25+24+23 |
210+27-23 |
466 |
326 |
18631 |
|
Table 11 construction 6.6 k=3 mod 6
6.6 |
15 |
0x100011005 |
232+216+212+22+1 |
232+216+212+22+1 |
383 |
257 |
5737 |
138 |
6.6 |
21 |
0x41037e |
|
222+216+210-27-2 |
351 |
265 |
7367 |
Error p is not prime |
BLS3 |
27 |
0x7c09 |
214+213+212+211+210+23+1 |
215-210+23+1 |
298 |
268 |
8033 |
|
6.6 |
33 |
0x4283 |
214+29+27+2+1 |
214+29+27+22-1 |
336 |
282 |
11080 |
|
6.6 |
39 |
0x2c90 |
213+211+210+27+24 |
214-212-210+27+24 |
376 |
324 |
14656 |
|
6.6 |
45 |
0xcfb |
|
212-210+28-22-1 |
373 |
281 |
16775 |
|
Table 11 construction 6.6 k=1,5 mod 6
6.6 |
11 |
0x46d0 |
214+210+29+27+26+24 |
214+211-28-26+24 |
338 |
283 |
3718 |
118 |
6.6 |
13 |
0x2c90 |
213+211+210+27+24 |
214-212-210+27+24 |
376 |
324 |
4886 |
152 |
6.6 |
29 |
0xb90 |
211+29+28+27+24 |
212-210-27+24 |
691 |
646 |
20019 |
|
Table 14 KSS
KSS |
16 |
-0x3f87007ff |
|
-(-234+227-223+220-211+1) |
330 |
257 |
5280 |
140 |
KSS |
18 |
0x1000003ffe02 |
|
244+222-29+2 |
348 |
256 |
6257 |
|
KSS |
32 |
0x180c20 |
220+219+211+210+25 |
221-219+212-210+25 |
350 |
283 |
11171 |
Error p(u) is not in Z Error r(u) is not in Z |
KSS |
36 |
0x1824213 |
224+223+217+214+29+24+2+1 |
225-223+217+214+29+24+22-1 |
330 |
268 |
11862 |
Error p(u) is not in Z Error r(u) is not in Z |
KSS |
40 |
0x42191 |
218+213+28+27+24+1 |
218+213+29-27+24+1 |
377 |
258 |
15077 |
Error p(u) is not in Z Error r(u) is not in Z |
KSS |
54 |
0x18888 |
216+215+211+27+23 |
217-215+211+27+23 |
349 |
314 |
18802 |
Error r is not prime |
Table 14 other
LZZW |
9 |
0x40000000007ffc00002 |
|
274+235-222+2 |
591 |
443 |
5314 |
128 |
BN |
12 |
0x4001fffffffffffffffffffffbfff |
|
2114+2101-214-1 |
462 |
462 |
5535 |
135 |
DCC |
15 |
0x100090402 |
232+219+216+210+2 |
232+219+216+210+2 |
383 |
257 |
5737 |
138 |
Table 15 128 bits
6.3 |
14 |
0x37723d |
|
222-219-215-212+29+26-22+1 |
391 |
262 |
5464 |
131 |
6.4 |
20 |
0x100010011 |
232+216+24+1 |
232+216+24+1 |
383 |
257 |
7641 |
|
6.4 |
28 |
0x40031b |
222+29+28+24+23+2+1 |
222+210-28+25-22-1 |
351 |
265 |
9801 |
|
6.6 |
12 |
-0x1ffffffbfffe00000000 |
|
-(-277+250+233) |
461 |
308 |
5525 |
134 |
6.6 |
15 |
0x100011005 |
232+216+212+22+1 |
232+216+212+22+1 |
383 |
257 |
5737 |
138 |
6.6 |
24 |
-0xeffff000 |
|
-(-232+228+212) |
318 |
256 |
7620 |
162 |
BLS3 |
27 |
0x7c09 |
214+213+212+211+210+23+1 |
215-210+23+1 |
298 |
268 |
8033 |
|
6.7 |
12 |
0x100024001 |
232+217+214+1 |
232+217+214+1 |
446 |
257 |
5341 |
134 |
KSS |
16 |
-0x3f87007ff |
|
-(-234+227-223+220-211+1) |
330 |
257 |
5280 |
140 |
DCC |
15 |
0x100090402 |
232+219+216+210+2 |
232+219+216+210+2 |
383 |
257 |
5737 |
138 |
Table 15 192 bits
6.3 |
14 |
0x10000000979 |
240+211+28+26+25+24+23+1 |
240+211+29-27-23+1 |
719 |
481 |
10053 |
172 Error p is not prime |
6.4 |
20 |
0x2000000000011a41 |
261+216+212+211+29+26+1 |
261+216+213-211+29+26+1 |
731 |
489 |
14601 |
|
6.4 |
28 |
-0x80002003 |
-(231+213+2+1) |
-(-231-213-22+1) |
495 |
373 |
13833 |
200 |
6.6 |
12 |
0xc0000000000000000000000002 000000000000000000000008c6 |
2207+2206+2105+211+27+26+22+2 |
2208-2206+2105+211+28-26+23-2 |
1244 |
831 |
14928 |
|
6.6 |
15 |
0x7000000000000018f01 |
274+273+272+216+215+211+210+29+28+1 |
275-272+217-215+212-28+1 |
897 |
599 |
13442 |
|
BLS3 |
27 |
0x6110e0 |
222+221+216+212+27+26+25 |
223-221+216+212+28-25 |
451 |
406 |
12162 |
|
6.6 |
24 |
-0x10007fffffffe40 |
|
-(-256-243+29-26) |
559 |
449 |
13403 |
202 |
6.7 |
24 |
-0xfbffffffefff |
|
-(-248+242+212+1) |
573 |
384 |
13746 |
205 |
KSS |
16 |
0xa0000000000000201afd0 |
|
283+281+225+217-214-212-26+24 |
824 |
651 |
13173 |
Error p(u) is not in Z Error r(u) is not in Z |
KSS |
18 |
0x4000000000000000049e2 |
282+214+211+28+27+26+25+2 |
282+214+211+29-25+2 |
652 |
484 |
11729 |
Error p(u) is not in Z Error r(u) is not in Z |
DCC |
15 |
0x200000000000001d0108 |
277+220+219+218+216+28+23 |
277+221-218+216+28+23 |
923 |
617 |
13837 |
|
Table 15 256 bits exotic k
6.2 |
17 |
0x1000067bf |
|
232+215-213+211-26-1 |
1215 |
1025 |
20639 |
|
6.3 |
18 |
0x8000000553f |
|
243+214+212+210+28+26-1 |
945 |
517 |
16993 |
|
6.6 |
19 |
0x9bf0 |
|
215+213-210-24 |
610 |
551 |
11587 |
|
6.6 |
20 |
0x400000003df2 |
|
246+214-29-24+2 |
1011 |
737 |
20209 |
|
6.6 |
22 |
0x200008bd |
229+211+27+25+24+23+22+1 |
229+211+28-26-22+1 |
811 |
581 |
17830 |
|
6.6 |
26 |
0x821104 |
223+217+212+28+22 |
223+217+212+28+22 |
644 |
553 |
16720 |
|
6.6 |
28 |
0x41f956 |
|
222+217-211+29-27-25-23-2 |
748 |
530 |
20942 |
|
6.7 |
9 |
0x305be9 |
|
222-220+215-213-210-25+23+1 |
991 |
519 |
8914 |
|
Table 15 256 bits
6.4 |
20 |
0xe00000000000000073c9 |
|
280-277+215-212+210-26+23+1 |
956 |
639 |
19114 |
|
6.4 |
28 |
0x4000000000007d83 |
|
262+215-29-27+22-1 |
991 |
745 |
27721 |
|
6.6 |
15 |
0x40000000000000000000000000000040000c00 |
2150+230+211+210 |
2150+230+212-210 |
1799 |
1201 |
26977 |
|
6.6 |
24 |
0x60000000100004000000000000 |
2102+2101+268+250 |
2103-2101+268+250 |
1025 |
821 |
24583 |
Error p(u) is not in Z Error r is not prime |
BLS3 |
27 |
-0xffffc14 |
|
-(-228+210-24-22) |
559 |
503 |
15078 |
|
6.7 |
12 |
0x80000000000000000000000000720f |
2119+214+213+212+29+23+22+2+1 |
2119+215-212+29+24-1 |
1664 |
953 |
19957 |
|
KSS |
16 |
0x600000000000000000000000000000000016e1 |
2150+2149+212+210+29+27+26+25+1 |
2151-2149+213-211-28-25+1 |
1496 |
1189 |
23935 |
Error p(u) is not in Z Error r(u) is not in Z |
LZZW |
9 |
0x80000000000000000000000000000000000 000000000000000000000000000000005f090 |
2287+218+216+215+214+213+212+27+24 |
2287+219-217-212+27+24 |
2295 |
1721 |
20650 |
|
DCC |
15 |
0x10000000000000000000000007f6b |
|
2112+215-27-24-22-1 |
1343 |
897 |
20137 |
|