and added ZZ/byte array conversions.<li>Improved performance of primality test, and added a more convenient routine <tt>GenPrime</tt>.<li>Overloaded NTL's vector placement "new" operator in a differentway to avoid conflicts with standard <tt>C++</tt> library.<li>Renamed many macros.<li>Renamed header files.<li>Made some changes to the packagingthe installation procedure.</ul><p><b>Renamed Macros.</b>I renamed many macros defined in NTL header files.<p>The reason is that I want to minimize namespace pollution.Someday, NTL will be wrapped in a namespace, and when that happensthe only remaining namespace pollution problems will be caused by macros.Eliminating all macros from NTL is not feasible.Instead, all NTL defined macros now begin with the prefix "NTL_",which reduces the namespace pollution to an ecceptable level.You will probably not be affected by this, unless youdo some low level hacking using a macro like <tt>ZZ_NBITS</tt>(now called <tt>NTL_NBITS</tt>), or unless you create yourown NTL vectors using a macro like <tt>ntl_vector_decl</tt>(now called <tt>NTL_vector_decl</tt>).<p>For a complete list of affected names, see <a href="names.txt">names.txt</a>.<p>Adapting to this name change should be painless, as there is a program to translate source files from the old naming convention to the new.The file "newnames.c", can be compiled as either a <tt>C</tt> or <tt>C++</tt>program. The program is a "filter" that copies its input to its output,replacing all the old macro names by the new macro names.<p>In the WinNTL distribibution, "newnames.c" is called "newnames.cpp" and is located in the directory"newnames".<p><b>Renamed header files.</b>The names of header files themeselves pollute another (extra-linguitsic) namespace.To alleviate this problem, the header files have been renamed.Instead of<pre>   #include "foo.h"</pre>one now should write<pre>   #include &lt;NTL/foo.h&gt;</pre>The only exceptions are the old header files "ntl_vector.h","ntl_matrix.h", and "ntl_pair.h", which are now called<tt>&lt;NTL/vector.h&gt;</tt>, <tt>&lt;NTL/matrix.h&gt;</tt>, and <tt>&lt;NTL/pair.h&gt;</tt>.<p><b>Installation procedure.</b>Now allNTL flags like NTL_LONG_LONG, NTL_AVOID_FLOAT, etc., can  now be setby editing the special file "include/NTL/config.h".See details in that file.The reason for this change is that this allows all of these settingsto be made when NTL is configured and built.Clients of NTL will then automatically use consistent settings.One should not set these flags on the compiler command line as previously.<p>Pentium/Linux people should no longer have to worryabout the NTL_X86_FIX flag. NTL now psychically deducesthe "right thing to do", although if its psychic abilities fail,you can override it with flags in "include/NTL/config.h".<p>The "packaging" in the Unix distribution is slightlydifferent, but hopefully nicer.Among other things, the tar file now unpacks into a sub-directory of the current directory.See <a href="tour-unix.html">the unix installation section</a>for more details.The Windows zip file now also unpacks into  sub-directory.<p><b>My apologies.</b>Although these changes are minor, they will cause some NTLusers some inconvenience.I apologize for this.I really, really hope there are no more changes like this(see my <a href="tour-roadmap.html">roadmap</a> of NTL's future).<p><hr><p><h3>Changes between NTL 3.1a and 3.1b</h3><p>Defined functions <tt>div(GF2X,GF2X,GF2)</tt> and <tt>div(GF2X,GF2X,long)</tt>,which had not been defined in earlier versions.Affected file: <tt>GF2X.c</tt>.Most programs never use this, and most linkers do not complainif these are missing (but some do).<p><hr><p><h3>Changes between NTL 3.0f and 3.1a</h3><p>This version is backward compatible with previous versions.<p><ul><li>Added floating point LLL routines based on Givens rotations,instead of classical Gramm-Schmidt orthogonalization.This is a more stable, but somewhat slower, method.See <a href="LLL.txt">LLL.txt</a> for details.<li>Added support for irreducible trinomials and pentanomialsover GF(2). The <tt>GF2XModulus</tt> routines,and by extension, the <tt>GF2E</tt> routines,now exploit moduli of this special form.The new routine <tt>BuildSparseIrred</tt> in <tt>GF2XFactoring</tt>builds irreducibles of this form.<li>Also implemented a faster modular inversion routinefor <tt>GF2X</tt>, and improved the performance of <tt>ZZ_pX</tt>multiplication for small degree polynomials.</ul><p><hr><p><h3>Changes between NTL 3.0e and 3.0f</h3><p><ul><li>Fixed a bug (another one) affecting routines<pre>   RandomBits, RandomBits_ZZ</pre>in module <tt>ZZ</tt>.Affected source file: <tt>lip.c</tt>.<li>Bug fix and performance tweak in <tt>ZZX</tt> factorizer.Affected source file: <tt>ZZXFactoring.c</tt>.   </ul><p><hr><p><h3>Changes between NTL 3.0 and 3.0e</h3><p><ul><li>Fixed a bug affecting routines <pre>   RandomBits, RandomBits_ZZ, RandomBits_long</pre>in module <tt>ZZ</tt>.The only source files that are affected and require re-compilation are<pre>   ZZ.c, lip.c</pre><li>Note about names:3.0a-c were "pre-releases", which makes the "first release" 3.0d,and hence this bug fix 3.0e.   </ul><p><hr><p><h3>Changes between NTL 2.0 and 3.0</h3><p><ul><li>Added functionality:<p><ul><li>Added classes vec_GF2 and mat_GF2 for fast linear algebra over GF(2).<li>Added classes ZZ_pE, ZZ_pEX, zz_pE, zz_pEX, supporting polynomialarithmetic over extension rings/fields over prime fields.<li>Added John Abbott's pruning heuristic to the ZZX factoring routine.<li>Speeded up multiplication in zz_pX for small p (this also helpsthe ZZX factoring routine).<li>Added some some transcendental functions (e.g., exp, log, pi) to RR.<li>Added verbose mode and pruning to the XD and RR variants of LLL.</ul><p><li>Improved programming interface:with this version, I've taken an the opportunity to give the programming interface a "professional facelift".In previous releases, I've tried to maintain backward compatabilityas much as possible, but to make the badly needed improvementsto the interface that I've made with this release, this was notpossible.<p>NTL 3.0 is not backward compatable with NTL 2.0.<p>I apologize to NTL users for this, but it is a bit of painfulmedicine that should only be necessary to take just this one time(but then as a <tt>C++</tt> programmer, you must alreadybe used to suffering ;-).Just about all of the incompatabilities are detectable by the compiler.See below for a detailed list of the changes andsome tips on making the transition.<p>The new interface is much more enjoyable to work with,and I don't foresee any changes to the interace in the future.Here is a broad overview of the changes:<p><ul><li>Added functional/operator notation consistently throughout NTL,making it possible to write much more concise and readable code.<li>Got rid of automatic type conversions:  these cause just toomany problems.  But I've overloaded all of the basic arithmeticoperators and procedures so as to emulate a natural kindof "type promotion" logic.  With these promotions, along witha  full compliment of conversion functions, one hardly missesthe automatic conversions.<li>Got rid of the macros<pre>   vector(T), matrix(T), pair(T),</pre>which were causing too many name space problems.<li>Made assignment operators have the "correct" return type.<li>Introduced a more powerful and flexible mechanism for modulus changing.<li>Cleaned up numerous other minor problems.</ul></ul><p><h4>Compatibility</h4><p>Here is a detailed list of the changes to the programming interface.<p><ul><li>The names of the classes <pre>   BB, BB_p, BB_pX</pre>have been changed to<pre>   GF2X, GF2E, GF2EX</pre><li>There is also a class <tt>GF2</tt> to represent GF(2).Many of the functions relating to <tt>BB, BB_p, BB_pX</tt>had argument and return-value types of type <tt>long</tt>that are now of the more appropriate type <tt>GF2</tt>.This change was needed so that the interface would be consistentwith that of the new classes<pre>   ZZ_pE, ZZ_pEX, zz_pE, zz_pEX.</pre><li>The explicit conversion operator from <tt>GF2X</tt> (the new <tt>BB</tt>) to <tt>GF2EX</tt> (the new <tt>BB_pX</tt>)has different semantics: it now performs a coefficient lift,instead of creating a constant polynomial.<li>The conversion operator "<tt>&lt;&lt;</tt>" has been retired.Now instead of<pre>   x &lt;&lt; a; </pre>one writes<pre>   conv(x, a);</pre><p>Operator "<tt>&lt;&lt;</tt>" is now used for shift operations.<li>Every conversion routine now has a corresponding functional versionwhich has the name <tt>to_T</tt>, where <tt>T</tt> is the result type.These new names replace old names that were less consistent.So instead of<pre>   x = Long(a);</pre>one writes<pre>   x = to_long(a);</pre><li>The names of the routines<pre>   ZZ_pInit, zz_pInit, zz_pFFTInit, GF2EInit</pre>have been changed to<pre>   zz_p::init, zz_p::init, zz_p::FFTInit, GF2E::init</pre><li>The names of the routines <pre>   and, or, xor </pre>for class <tt>ZZ</tt> havechanged to <pre>   bit_and, bit_or, bit_xor, </pre>because the new <tt>C++</tt>standard defines these as reserved words.<li>The function <tt>LowBits</tt> for <tt>ZZ</tt> is now called <tt>trunc</tt>.<li>Polynomial inversion mod <tt>X^n</tt> has changed from <tt>inv</tt>to <tt>InvTrunc</tt>.<li>Modular trace, norm, minimum polynomial and characteristicpolynomial have changed from<pre>   trace, norm, MinPoly, IrredPoly, CharPoly</pre>to<pre>   TraceMod, NormMod, MinPolyMod, IrredPolyMod, CharPolyMod</pre><li>For the class <tt>ZZX</tt>, the functions <pre>   DivRem, div, rem, /, %, /=, %=</pre>have new semantics when dividing by non-monic polynomials.The old semantics are provided by new routines <pre>   PseudoDivRem, PseudoDiv, PseudoRem.</pre><li>The <tt>UpdateMap</tt> routines have slightly different semantics:in versions &lt; 3.0, the output always had length n;now high-order zeroes are stripped.<li>The classes <tt>ZZ_pBak</tt>, <tt>zz_pBak,</tt> etc.,  have just slightly different semantics;  I can't imagineany reasonable program detecting a difference.<li>The assignment operator and copy constructor for the class <tt>RR</tt>have different semantics: they now produce exact copies, insteadof rounding to current precision.<li>All of the NTL compiler flags now start with <tt>NTL_</tt>to avoid name space problems.<li>All of the files "zz_p.h", vec_zz_p.h", etc., have been eliminated.Use instead the names "lzz_p.h", "vec_lzz_p.h", etc.</ul><p><h4>Tips on making the transition</h4><p><ul><li>Apply this <a href="sedscript.txt">sed script</a> to makemost of the necessary syntactic changes.<li>Re-compile old NTL programs with the flag <pre>   -DNTL_TRANSITION</pre>See <a href="flags.txt">flags.txt</a> for details on howthis will help your compiler detect remaining incompatabilities.In particular, any uses of operator <tt>&lt;&lt;</tt>in its old role as a conversion operator will cause the compilerto raise an error.You can then convert all of these to the new notation.</ul><p><hr><p><h3>Changes between NTL 1.7 and 2.0</h3><p><ul><li>Implementation of classes BB (polynomials over GF(2))and BB_pX (polynomials over GF(2^n)).<li>A more consistent and natural interface, including arithmetic operatorsand a disciplined use of automatic conversion.So now one can write<pre>   x = a * b + c;</pre>instead of <pre>   mul(x, a, b);   add(x, x, c);</pre>as one must in older versions of NTL.The operator notation leads to somewhat less efficient code,and one can always use the old notation in situationswhere efficiency is critical.Despite the new programming interface,care has been taken to ensure backward compitability;pre-existing programs that use NTL should still work.<li>Windows port.<li>Added compile-time flag that allows one to exploit "long long" data type if it exists (this especially helps on Pentium/Linux platforms).<li>Added compile-time flag to get better quad_float code onPentium/Linux platforms.<li>A few bug fixes and performance tuning.</ul><p><hr><p><h3>Changes between NTL 1.5 and NTL 1.7</h3><p><ul><li>Incorporation of Keith Briggs' quadratic precision package.<li>Much faster and more robust lattice basis reduction,including Schnorr-Horner "volume heuristic" for Block KorkinZolotarev reductions, and a new quadratic precision LLL variantthat is much more robust.<li>A few bug fixes.</ul><p><hr><p><h3>Changes between NTL 1.0 and NTL 1.5</h3><p><ul><li>Implementation of Schnorr-Euchner algorithms forlattice basis reduction, including deep insertions andblock Korkin Zolotarev reduction.These are significantly faster than the LLL algorithmin NTL 1.0.<li>Implementation of arbitrary-precision floating point.<li>Implementation of double precision with extended exponent range,which is useful for lattice basis reduction when the coefficientsare large.<li>Faster polynomial multiplication over the integers,incorporating the Schoenhagge-Strassen method.<li>Compilation flags that increase performance on machineswith poor floating-point performance.<li>Sundry performance tuning and a few bug fixes.</ul><center><a href="tour-roadmap.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-ack.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center></body></html>