📄 tour-time.html
字号:
<html><head><title>A Tour of NTL: Some Performance Data </title></head><body bgcolor="#fff9e6"><center><a href="tour-gmp.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> <a href="tour-roadmap.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center><h1> <p align=center>A Tour of NTL: Some Performance Data </p></h1><p> <hr> <p>For some detailed performance measurements for basic integerarithmetic <a href="tour-gmp.html">go here</a>.<p>This page discusses the performance of other, higher-level operations.Here are some timing figures from using NTL.The figures were obtained using an IBM RS6000 Workstation, Model 43P-133,which has a 133 MHz PowerPC Model 604 processor.The operating system is AIX and the compiler is xlC.The compiler options were <tt>-O2 -qarch=ppc</tt>and the NTL flags <tt>NTL_AVOID_FLOAT</tt> and <tt>NTL_TBL_REM</tt>were set.<a href="tour-gmp.html">GMP</a> was not used.<p><h2>Factoring polynomials over finite fields</h2><p>The first problem considered is the factorization of univariate polynomials modulo a prime <var>p</var>.As test polynomials, we take the family of polynomialsdefined in [V. Shoup, J. Symb. Comp. 20:363-397, 1995].For every <var>n</var>, we define <var>p</var> to be the first prime greater than<var>2^(n-2)*PI</var>, and the polynomial is <p><var>sum(a[n-i]*X^i, i = 0..n), </var><p>where <var>a[0] = 1</var>, and <var>a[i+1] = a[i]^2 + 1.</var>Here are some running times:<p><table cellpadding=10><tr><td> <var>n</var> <td> 64 <td> 128 <td> 256 <td> 512 <td> 1024 <tr><td> hh:mm:ss <td> 2 <td> 13 <td> 1:53 <td> 21:01 <td> 4:05:25</table><p>Also of interest is space usage.The <var>n</var> = 512 case used 4MB main memory, and the <var>n</var> = 1024 case used 17 MB main memory.<p>Just for fun, I tried the case <var>n=2048</var> withversion 4.3 of NTL on a 700MHz Pentium-III,using <a href="tour-gmp.html">GMP</a>.This took about 8.5 hours.For comparison,this took 12 <i>days</i> when I ran it on a stae-of-the art Sparc station in 1994.Some of the improvement was due just to faster clock speeds,but using <a href="tour-gmp.html">GMP</a>for the long arithmetic helped too.Without GMP, it takes 17 hours.<p>Another test suite, this time using small primes,was used by Kaltofen and Lobo (Proc. ISSAC '94).One of their polynomials is a degree 10001 polynomial,modulo the prime 127.This polynomial was factored with NTL in just over 3 hours,using 17MB of memory.<p><h2>Factoring polynomials over the integers</h2><p>The second problem considered is factoring univariate polynomials over the integers.This test suite comes from <a href="http://www.loria.fr/~zimmerma">Paul Zimmermann</a>.The polynomial <var>P1(X)</var> hasdegree 156, coefficients up to 424 digits, and 36 factors (12 of degree 2, 15 of degree 4, 9 of degree 8). Thepolynomial <var>P2(X)</var> has degree 196, coefficients up to 419 digits and 12 factors (2 of degree 2, 4 of degree 12 and6 of degree 24). The polynomial <var>P3(X)</var> has degree 336, coefficients up to 597 digits and 16 factors (4 of degree12 and 12 of degree 24). The polynomial <var>P4(X)</var> has degree 462, coefficients up to 756 digits, and two factorsof degree 66 and 396.The polynomial <var>P5(X)</var> has degree 64, coefficients of up to 40digits, and is irreducible.It is a so-called Swinnerton-Dyer polynomial,which is one of the most difficult types to factor (or prove irreducible).<a href="http://www.loria.fr/~zimmerma/mupad"> More details </a> on this test suite are available.<p>Our running times (hh:mm:ss) were as follows:<pre> 1.7, 6.7, 14, 3:56, 2:17.</pre>In all cases less than 5MB of main memory was used.<p>These times relect an improvement over version 3.7a dueto a simple trick of exploiting the structure of polynomialsof the form <tt>g(x^k)</tt>.It is a real hack, but many other factorizers "on the market"do this too, so it is only fair.Moreover, as these polynomials arise from "natural problems",and are not artificially constructed, it seems reasonable tolook for and exploit such structure.<p>Without this hack (as in version 3.7a) the times for<var>P1(X)</var>, <var>P2(X)</var>, and <var>P3(X)</var> (hh:mm:ss)we as follows:<pre> 15, 21, 1:12.</pre>The times for <var>P4(X)</var> and <var>P5(X)</var> remain unchanged.<p>All of these times reflect significant improvements tothe factorizer available since version 3.6a.As a comparison, here are the corresponding times in version 3.5a:<pre> 21, 23, 1:16, 1:37:10, 1:25:00.</pre><p>In addition to the above polynomials, Zimmermann has recentlyadded a challenge polynomial <var>P8(X)</tt> to his listof challenge polynomials.This is a particularly hard-to-factor polynomial, but usingnew techniques, we were able to prove that it is irreduciblein time <tt>1:41:00</tt> using 128MB of memory on a 375MHz PowerPC(model 43P-150).This technique is based on a time/space tradeoff.For example, using 64MB of memory, the running time for thesame calculation was <tt>2:40:00</tt>.<p><h2>Lattice basis reduction</h2><p>NTL's lattice basis reduction code has been used to push the envelopeon breaking new lattice-based cryptosystems.To date, NTL's lattice code has been used to break theGGH cryptosystem [Goldreich, Goldwasser, Halevi, Crypto '97]up to dimension 350.These experiments were designedand conducted by <a href="http://www.dmi.ens.fr/~pnguyen">Phong Nguyen</a>.<p><center><a href="tour-gmp.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> <a href="tour-roadmap.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -