[Previous] [Up] [Next]

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

[Previous] [Up] [Next]