sec_invert performance

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I quick guess is that the exponent is fixed for powm, not a function of
> the input size.

Ah, its hardcoded to always use 6 limbs. If I change it to use the same
size as b and m, results are a bit different:

$ ./speed -s 1-64 -c -r mpn_gcdext mpn_sec_invert mpz_powm_sec
overhead 5.43 cycles, precision 10000 units of 6.25e-10 secs, CPU freq 1600.00 MHz
           mpn_gcdext mpn_sec_invert  mpz_powm_sec
1            #1393.53        9.2563        2.8281
2            #3700.83        8.4530        2.8537
3            #5628.82        9.2296        4.7198
4            #7387.08        9.8705        6.5449
5            #9270.67       12.2271        9.4494
6           #11102.89       13.2985       11.9077
7           #12923.54       14.2668       14.8305
8           #14985.50       14.9848       17.2423
9           #16826.96       17.1405       21.4808
10          #18998.00       17.9614       24.7252
11          #20390.00       19.6006       29.7402
12          #23244.21       19.9373       32.0728
13          #24235.58       22.4859       39.6380
14          #26027.70       23.5316       44.4109
15          #29157.89       23.7497       47.7260
16          #30368.62       26.6497       53.3113
17          #32534.43       28.4042       60.1591
18          #33580.67       29.1482       69.0387
19          #34424.60       31.2023       78.6099
20          #36470.00       32.4313       84.8543
21          #36405.25       35.8625       99.2162
22          #41335.25       33.8338       97.9815
23          #39861.67       38.2781      116.4425
24          #41421.67       39.4835      124.2736
25          #44087.67       41.0079      138.0154
26          #48386.33       39.9403      139.1569
27          #40868.00       50.5410      184.1573

So if you know that the modulo is prime (or has some other type of known
factorization), using powm actually beats sec_invert for sizes up to 6
limbs.

I still puzzled why the ratio between sec_invert and gcdext doesn't
approach some constant (I'd expect the ratio to start growing again for
sizes above the threshold for subquadratic gcdext).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.