Ticket #4283 (assigned enhancement)

Opened 2 months ago

Last modified 2 months ago

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

Reported by: anovocin Assigned to: anovocin (accepted)
Priority: major Milestone: sage-3.2.2
Component: factorization Keywords: NTL, LLL, Univariate
Cc:

Description

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<mpz_t> 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.

Attachments

ntlfactor.patch (2.4 kB) - added by anovocin on 10/14/2008 08:21:47 AM.

Change History

10/14/2008 07:27:44 AM changed by anovocin

  • owner changed from tbd to anovocin.
  • status changed from new to assigned.
  • summary changed from [with proto-patch]A Speed-up Patch for NTL's ZZXFactoring.c to [with proto-patch] A Speed-up Patch for NTL's ZZXFactoring.c.

10/14/2008 08:21:47 AM changed by anovocin

  • attachment ntlfactor.patch added.