| 1 | <html> |
|---|
| 2 | <head> |
|---|
| 3 | <title> |
|---|
| 4 | A Tour of NTL: NTL past, present, and future </title> |
|---|
| 5 | </head> |
|---|
| 6 | |
|---|
| 7 | <body bgcolor="#fff9e6"> |
|---|
| 8 | <center> |
|---|
| 9 | <a href="tour-time.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 10 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 11 | <a href="tour-changes.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 12 | </center> |
|---|
| 13 | |
|---|
| 14 | <h1> |
|---|
| 15 | <p align=center> |
|---|
| 16 | A Tour of NTL: NTL past, present, and future |
|---|
| 17 | </p> |
|---|
| 18 | </h1> |
|---|
| 19 | |
|---|
| 20 | <p> <hr> <p> |
|---|
| 21 | |
|---|
| 22 | <h3> |
|---|
| 23 | Some History |
|---|
| 24 | </h3> |
|---|
| 25 | |
|---|
| 26 | <p> |
|---|
| 27 | |
|---|
| 28 | Work on NTL started around 1990, when I wanted to implement some new |
|---|
| 29 | algorithms for factoring polynomials over finite fields. |
|---|
| 30 | I found that none of the available software was adequate for |
|---|
| 31 | this task, mainly because the code for polynomial arithmetic in |
|---|
| 32 | the available software was too slow. |
|---|
| 33 | So I wrote my own. |
|---|
| 34 | My starting point was Arjen Lenstra's LIP package for long integer |
|---|
| 35 | arithmetic, which was written in <tt>C</tt>. |
|---|
| 36 | It soon became clear that using <tt>C++</tt> instead of <tt>C</tt> |
|---|
| 37 | would be much more productive and less prone to errors, |
|---|
| 38 | mainly because of <tt>C++</tt>'s constructors and destructors |
|---|
| 39 | which allow memory management to be automated. |
|---|
| 40 | Using <tt>C++</tt> has other benefits as well, like function |
|---|
| 41 | and operator overloading, which makes for more readable code. |
|---|
| 42 | |
|---|
| 43 | <p> |
|---|
| 44 | One of the basic design principles of LIP was portability. |
|---|
| 45 | I adopted this principle for NTL as well, for a number of reasons, |
|---|
| 46 | not the least of which was that my computing environment |
|---|
| 47 | kept changing whenever I changed jobs. |
|---|
| 48 | Achieving portability is getting easier as standards, |
|---|
| 49 | like IEEE floating point, get widely adopted, and as the definition of |
|---|
| 50 | and implementations of the |
|---|
| 51 | <tt>C++</tt> language stabilize (which a few years ago was a huge headache, |
|---|
| 52 | but is now only a big one, and in a few years will be a small one). |
|---|
| 53 | |
|---|
| 54 | |
|---|
| 55 | <p> |
|---|
| 56 | Since 1990, NTL has evolved in many ways, |
|---|
| 57 | and it now provides a fairly polished and well-rounded programming interface. |
|---|
| 58 | |
|---|
| 59 | <p> |
|---|
| 60 | When I started working on NTL, there really were not that many |
|---|
| 61 | good, portable long integer packages around. |
|---|
| 62 | Besides LIP, there was the BSD Unix MP library. |
|---|
| 63 | The first version of GMP was released in the early 1990's. |
|---|
| 64 | At that point in time, LIP seemed like the best starting point. |
|---|
| 65 | LIP remains a reasonable long integer package, but in recent years, |
|---|
| 66 | GMP has really become quite good: it seems well supported on |
|---|
| 67 | many platforms, and is typically much faster than LIP. |
|---|
| 68 | |
|---|
| 69 | <p> |
|---|
| 70 | I've now re-structured NTL so that one can use |
|---|
| 71 | either 'traditional' LIP or GMP as the <i>primary</i> long integer package. |
|---|
| 72 | Doing this introduced some (minor) backward incompatabilies in |
|---|
| 73 | the programming interface, so there is also a 'third way' -- you |
|---|
| 74 | can use GMP as a <i>supplemental</i> long integer package, getting |
|---|
| 75 | many (but not all) of the performance benefits of GMP, while |
|---|
| 76 | maintaining <i>complete</i> backward compatability with the traditional |
|---|
| 77 | long integer package. |
|---|
| 78 | This 'third way' is not highly recommended -- it is only intended |
|---|
| 79 | as backward compatabilty hack. |
|---|
| 80 | |
|---|
| 81 | <p> |
|---|
| 82 | |
|---|
| 83 | <h3> |
|---|
| 84 | The Future of NTL |
|---|
| 85 | </h3> |
|---|
| 86 | |
|---|
| 87 | <p> |
|---|
| 88 | |
|---|
| 89 | I hope that NTL remains stable in its current form. |
|---|
| 90 | I plan to support NTL, fixing bugs and serious performance |
|---|
| 91 | problems, but otherwise not to add significant new functionality or |
|---|
| 92 | modify the programming interface. |
|---|
| 93 | |
|---|
| 94 | <p> |
|---|
| 95 | I don't have time to add significant new functionality to NTL. |
|---|
| 96 | However, there seems to be an ever-growing number of NTL users |
|---|
| 97 | out there, and I encourage them to make their code available to |
|---|
| 98 | others. |
|---|
| 99 | These might be in the form of NTL "add ons", but there is the |
|---|
| 100 | possibility of integrating new functionality or algorithmic improvements into NTL itself. |
|---|
| 101 | One thing in particular that would be nice is support for |
|---|
| 102 | bivariate polynomial arithmetic, including GCDs, resultants, |
|---|
| 103 | and factoring, and for integer and all the various finite field |
|---|
| 104 | coefficient rings. |
|---|
| 105 | Another nice thing would be code for elliptic curves, |
|---|
| 106 | including an elliptic curve point counting algorithm. |
|---|
| 107 | Another nice thing would be something for factoring integers. |
|---|
| 108 | Any one of these projects would be a nice master's thesis project, |
|---|
| 109 | I think. |
|---|
| 110 | |
|---|
| 111 | <p> |
|---|
| 112 | As you can well imagine, there is potentially no end to algorithms one |
|---|
| 113 | could implement. |
|---|
| 114 | That is why I have to stop somewhere. |
|---|
| 115 | I think NTL has reached a point where it provides a reasonably |
|---|
| 116 | well-rounded suite of algorithms for basic problems. |
|---|
| 117 | |
|---|
| 118 | |
|---|
| 119 | <p> |
|---|
| 120 | |
|---|
| 121 | <center> |
|---|
| 122 | <a href="tour-time.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 123 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 124 | <a href="tour-changes.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 125 | </center> |
|---|
| 126 | |
|---|
| 127 | </body> |
|---|
| 128 | </html> |
|---|
