search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 481 forks source link

[with proto-patch] A Speed-up Patch for NTL's ZZXFactoring.c #4283

Open 5707a846-ac0e-410a-be52-83a04a9868e6 opened 16 years ago

5707a846-ac0e-410a-be52-83a04a9868e6 commented 16 years ago

The goal of this patch is to speed-up NTL's factoring algorithm for polynomials in Z[X]. The speed-up comes from using fpLLL rather than NTL's native LLL algorithm. We do this by converting a ZZ_mat of ZZ's (NTL's multi-precision integers) and passing them into a mat_ZZ matrix of mpz_t's (fpLLL's native format). Then run fpLLL on the new matrix and pass the entries back to NTL. I don't replace NTL's LLL just pass what should be an already reduced basis to NTL's LLL. (NTL computes extra information that would require a hack into fpLLL to get and might not be worth it.) This patch allows NTL to beat MAGMA on many examples (it still is a little slower than MAGMA (but faster than SAGE) on irreducible polynomials). I think that the cross over between Pari's factoring and NTL's factoring should be re-evaluated (currently Pari is used for polynomials of degree 30 through 300) if not just use NTL for all polynomials now.

Component: factorization

Keywords: NTL, LLL, Univariate

Issue created by migration from https://trac.sagemath.org/ticket/4283

5707a846-ac0e-410a-be52-83a04a9868e6 commented 16 years ago

Attachment: ntlfactor.patch.gz