Repository files navigation

The original code was bundled with CGAL, between versions 3.6 (March, 2010)and 4.3 (October, 2013). For CGAL 4.4, I removed it because I rewrote thealgebraic kernel that used it. I release it because I hope the code is usefulfor someone. If you are interested, don't hesitate in contacting me.

The implementation the well-known Euclidean algorithm to compute GCD.However, big numbers make the size of the coefficients explode. We use thenmodular arithmetic. We compute images of the input polynomials modulo someprimes and compute then images of these modular polynomials. Then, we useChinese lifting to recover the result.

You can compile using GNU make. Edit makefile and config to suit your needs.

The code is tested automatically viaTravis CI usingGCC and Clang, both under GNU/Linux and Mac OS. Tests are triggered when a newcommit is pushed. The code should also compile on MSVC, although I did nottest it.

• von Zur Gathen and Gerhard,Modern Computer Algebra, 2nd edition,Cambridge, 2003.
• Geddes, Czapor and Labahn,Algorithms for Computer Algebra,Springer, 1992.
• Zippel,Effective Polynomial Computations, Springer, 1993.

The code is released under the LGPLv3. See files COPYING.LESSER andCOPYING in the bundle for more information. Originally, the code wasreleased under the LGPLv2.