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:

1. Differences in the choices of csieve, cfilter and clinear algebra;
2. 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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits)
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

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (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