Factoring Polynomials via Polytopes: Extended version
Fatima Abu Salem‚ Shuhong Gao and Alan G. B. Lauder
Abstract
We introduce a new approach to multivariate polynomial factorisation which incorporates ideas from polyhedral geometry, and generalises Hensel lifting. Our main contribution is to present an algorithm for factoring bivariate polynomials which is able to exploit to some extent the sparsity of polynomials. We give details of an implementation which we used to factor randomly chosen sparse and composite polynomials of high degree over the binary field.
Details
| Institution |
Oxford University Computing Laboratory |
| Month |
April |
| Number |
RR−04−07 |
| Year |
2004 |