Fermat 6.5 with Vastly Improved Polynomial GCD

June 25, 2021; April 9, 2021; May 20, 2020; April 29, 2020; April 24, 2020; January 27, 2020; October 16, 2019; July 13, 2018; January 5, 2018; 2017.

New 64 bit versions of Fermat. copyright Robert H. Lewis, 1995 - 2021.


There are two versions, Linux, Intel hardware; and Mac, for Intel hardware and OS 10.6 - 10.*. See below to download.


Fermat 6.* implements a Zippel-like interpolation algorithm for multivariate polynomial GCD of six or more variables. (See R. Zippel. Interpolating Polynomials from their Values. J. Symbolic Comp. 9(3), 375-403, 1990.) If you do not have at least six variables, you will not see any change.


Years ago, Fermat was the fastest CAS for polynomial arithmetic. One reason for this is the polynomial GCD algorithms. However, despite continual improvements in those methods, it became clear by 2006 that a better method for problems involving more than four variables was often required. Fermat 6.0 provides that method. Some problems that took several days on previous versions of Fermat now complete in less than a minute.


Magma, a well-respected CAS, has long been considered to have very good polynomial arithmetic. Here is a suite of problems arising from actual applications that compares the new Fermat 6.0 with Magma. On the whole, it would seem from these tests that Fermat is a bit better, especially with large problems that take more than two minutes.


The new algorithm in Fermat applies to ground ring Z or Z/p for prime p. However, p should be "fairly large". In my own work I never use primes less than 20000 and often use p = 2^31 - 19. I have tested the new method on primes as small as 2003 and it worked fine. On p = 181 it worked but had to restart itself at least once. (It still took only one fifth the time of Fermat 5.25.) It will certainly fail on much smaller primes, as it needs a certain amount of "room" to succeed.


The method can be turned off with the new toggle command &z. It is on by default.


THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
NO ONE MAY USE THIS SOFTWARE AS PART OF ANY BUSINESS OR FOR-PROFIT ENDEAVOR WITHOUT THE EXPRESS WRITTEN PERMISSION OF ROBERT H. LEWIS. ROBERT H. LEWIS RETAINS THE COPYRIGHT TO ANY PROGRAM THAT INCLUDES THIS SOFTWARE.

See also the Fermat FAQ page.


June 25, 2021: Version 6.5.
- Various small bugs were fixed. The use of monomial-oriented multiply has been adjusted. It is turned off when there are only three variables, and when there are only four variables over a finite field. The determinant command &(D=n) now works for sparse arrays; see the manual. The manual has been revised. This function is now documented: Xmono


April 9, 2021: Version 6.38.
The manual has been revised. - Various small bugs were fixed. The manual has been revised. These functions are now documented: EGCD, WDeg, Totdeg.


May 20, 2020: Version 6.37.
- Fixed a very old bug that would appear as a "Fermat error" in certain matrix inversion problems with small all-integer matrices.


April 29, 2020: Version 6.36 for Linux.
- Fixed a silly stupid omission in the Linux version.


April 24, 2020: Version 6.36.
- Fixed several "features" of Zippel-like GCD that slowed it down (sometimes catastrophically) when the number of polynomial variables is large, say, bigger than 20.
- Improved the monomial multiply routines. They ran slowly when the number of polynomial variables is large, say, bigger than 20.
- Minpoly now works better for large matrices.


January 27, 2020: Version 6.32.
- Fixed very old silly bug that prevented factoring from working well. Factoring of one-variable polys over Z/p now works well.
- Powermod can now be invoked inside loops, such as for i = 1, 10 do Powermod(t, Modulus^i, f).


January 13, 2020: Version 6.31.
- Small rare bug fixed in GCD failing in extreme case.


October 16, 2019: Version 6.3.
- Several improvements having to do with slow GCD in extreme cases, such as many variables (> 40), or GCD(u,v) where v has hundreds of times more terms than u.


July 13, 2018: Version 6.21 has some small improvements and bug fixes.
- There is a new function Totdeg. Renamed the previous function WDeg. Totdeg resembles Sqfree in syntax, but the caret ^ works. Returns the largest and smallest sum of exponents in any monomial. One can easily check for homogeneous then.
- There was a small silly bug of omission that occurred rarely but would crash Fermat. This was introduced in 6.0.
- There was a small very rare bug that resulted in false positives in Divides(u, s) when u was very small and linear. This is an old bug.
- There was a bug in Redrowech working on a sparse matrix. It would fail if auxiliary matrices were requested. This is an old bug.
- There is now an option to Redrowech to not swap columns, i.e., just leave a column with all 0s below alone and move on. Use the new function Rowech (no red).


January 5, 2018: Version 6.19 has many small improvements and bug fixes.
- There is a new function Timecpu that displays the total CPU time used so far.
- There was a small bug that occurred only if the ferstart.txt file contained a command to find the determinant of a sparse matrix, in which case the computation would run very slowly.
- The command &d now has an imperative form, &(d = ...).
- There was an omission in the Mac version that rarely caused a slow down in the GCD routines.
- There was a problem in the heuristic that decides when to run the new Zippel-like GCD(u,v) routine. It was flawed if there were many variables x_i in an argument, say u, with Deg(u, x_i) = 1.
- Comments within a function can now have the form ; ...... end-of-line. So a comment can be delineated by { } as before, but now also by ; end-of-line.
- The interpreter will now display the line number when an error occurs reading a file. This is harder to do than it sounds. Occasionally, the number displayed is off by one or two. The text file being read cannot contain DOS line endings.


July 12, 2017: Version 6.17 has several small improvements over 6.16, which are unlikely to be noticed by any user. Certain rare failures occurred in some probabalistic algorithms. Also, there was a genuine, deeper error in an algorithm that finally revealed itself.


June 9, 2017: Version 6.16 has several small improvements over 6.0, which will probably not be noticed by any user. Certain very rare failures occurred in some probabalistic algorithms. Those failures are now a few orders of magnitude less likely.


64 bit Mac version 6.5. This was compiled with 10.14.6. It will not work on 10.5 and earlier. Expand the tar bundle. Put ferm6 in the right place so that the application Terminal sees it. Start up Terminal, then cd into ferm6. Type ./fer64. Don't just open the folder and double-click on fer64. For me, at least, that doesn't work well.

64 bit Linux version 6.5. This is compiled with the static option.


Fermat is freeware. Institutions or those with grant money should contribute $US 70 per machine.