#

A Tour of NTL: Some Performance Data

Here are some timing figures from using NTL. They were obtained using NTL 10.3.0 compiled with `g++` 4.8.5 and with GMP 6.1 on a 2.3GHz Intel Haswell processor (E5-2698 v3) running Linux.

All times are ins seconds. The times were obtained using the program `Timing` included in the distribution. The data was generated using NTL's random number generator, but running this on a different machine should (in theory) generate the same data.

    multiply 1000-bit ints: 1.75457e-07
    square 1000-bit ints: 1.15092e-07
    remainder 2000/1000-bit ints: 3.58906e-07
    gcd 1000-bit ints: 2.87446e-06
    xgcd 1000-bit ints: 4.44974e-06
    power mod 1000-bit ints: 0.000430014
    multiply degree-1000 poly mod 1000-bit prime: 0.00432467
    remainder degree-2000/1000 poly mod 1000-bit prime: 0.0124687
    preconditioned remainder degree-2000/1000 poly mod 1000-bit prime: 0.00438738
    gcd degree-1000 poly mod 1000-bit prime: 0.122324
    multiply degree-1000 int poly with 1000-bit coeffs: 0.00604421

    factoring degree-1000 poly mod 1000-bit prime...
    square-free decomposition...0.122127
    factoring multiplicity 1, deg = 1000
    computing X^p...7.24754
    computing DDF...generating baby steps...+++++++++++++++++++++2.78802
    generating giant steps...++++++++++++++++++++++2.89808
    giant refine...++++split 1 1
    split 2 26
    *++++*++++*++++*++++*++*split 0 973
    giant refine time: 4.80172
    baby refine...split 1 1
    split 26 26
    split 973 973
    baby refine time: 3.5e-05
    DDF time: 10.4926
    ...total time = 17.8706

    multiply 500-bit GF2Xs: 5.36244e-08
    remainder 1000/500-bit GF2Xs: 8.18858e-07
    gcd 500-bit GF2Xs: 3.63416e-06

    factoring degree-500 GF2X: 0.000154094
    gcd 500-bit GF2X: 3.62521e-06
    multiply degree-500 poly mod 500-bit GF2X: 0.00246822
    remainder degree-1000/500 poly mod 500-bit GF2X: 0.00890477
    preconditioned remainder degree-1000/500 poly mod 500-bit GF2X: 0.00496887
    gcd degree-500 poly mod 500-bit GF2X: 0.0455247

    factoring degree-500 poly mod 500-bit GF2X...
    square-free decomposition...0.004409
    factoring multiplicity 1, deg = 250
    computing X^p...0.476971
    computing DDF...generating baby steps...++++++++++0.326249
    generating giant steps...+++++++++++0.350505
    giant refine...++++split 1 9
    split 2 13
    split 4 44
    *++++split 7 73
    *split 0 111
    giant refine time: 0.228952
    baby refine...split 9 9
    split 13 13
    split 44 44
    split 73 73
    split 111 111
    baby refine time: 0.001264
    DDF time: 0.907007

    ...total time = 1.38948