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 routine
for <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 polynomial
arithmetic 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 helps
the 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 compatability
as much as possible, but to make the badly needed improvements
to the interface that I've made with this release, this was not
possible.
<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 painful
medicine that should only be necessary to take just this one time
(but then as a <tt>C++</tt> programmer, you must already
be used to suffering ;-).
Just about all of the incompatabilities are detectable by the compiler.
See below for a detailed list of the changes and
some 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 too
many problems.  But I've overloaded all of the basic arithmetic
operators and procedures so as to emulate a natural kind
of "type promotion" logic.  With these promotions, along with
a  full compliment of conversion functions, one hardly misses
the 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 consistent
with 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 version
which 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> have
changed 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 characteristic
polynomial 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 imagine
any 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, instead
of 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 make
most 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 how
this 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 compiler
to 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 operators
and 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 situations
where 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 on
Pentium/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 Korkin
Zolotarev reductions, and a new quadratic precision LLL variant
that 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 for
lattice basis reduction, including deep insertions and
block Korkin Zolotarev reduction.
These are significantly faster than the LLL algorithm
in 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 coefficients
are large.

<li>
Faster polynomial multiplication over the integers,
incorporating the Schoenhagge-Strassen method.

<li>
Compilation flags that increase performance on machines
with 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>