refactor polynomial_element.pyx factor function

[williamstein]

The "factor" function in polynomial_element.pyx needs to be refactored, because it has to be modified every time a new interesting base ring gets added to Sage.

Instead of importing a ton of different rings, the function should just call a method on the base ring, e.g.,

def _factor_univariate_polynomial(self, f):
    ...

Since the code in factor is for generic polynomials, it doesn't use their internal representation, so this should be fine. It just turns out that factoring algorithms depend a huge amount on the base ring, and polynomials get created over tons of different bases (but there are far less classes that derive from "polynomial").

I suggest for this ticket, at a minimum we add a quick "hasattr" check at the top of the current factor function, then leave the existing code. Then new code can be written to use this. In the near future somebody can move most of the imports and cases out the current factor function, so it becomes very short, and the code gets put in the right place.

A major motivation for this is that people create their own new rings R in external code that depends on sage, and want to be able to factor polynomials over R. They do not define a new class for polynomials over R. It seems silly for them to have to patch the core sage library to get factorization functionality.

---

Apply

1. attachment: trac_10635-new_version_with_tests.patch
2. attachment: trac_10635-fix_doctest_error_due_to_noise.reviewer.patch
   to the Sage library.

Component: basic arithmetic

Keywords: sd32

Author: Christopher Hall

Reviewer: Mariah Lenox, William Stein, Simon Spicer

Merged: sage-4.7.2.alpha3

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

[sagetrac-cjh]

comment:1

As someone interested in this change, let me chime in with a few suggestions of my own.

(1) A similar refactoring should be done for roots(). It's true factor() can be used to find roots, but that's not necessarily the best approach. This suggests the names ._univariate_polynomial_x for x=factor,roots,etc.

(2) So-called 'modular' gcd algorithms give a real boost to rings where applicable, so it would be nice to let x=gcd in (1).

(3) Consider whether options such as 'multiplicities=False' should really be options to .univariate_polynomial_factor() or whether they can be handled 'universally'.

[sagetrac-cjh]

Attachment: trac_10635_field_hooks.patch.gz

Patch implementing desired changes

[sagetrac-cjh]

comment:2

The patch addresses issue (1) and is for Sage 4.6.2.

[sagetrac-mariah]

comment:3

Patch applied to sage-4.7.1.alpha2, then did 'sage -b', then 'make testlong'. All tests passed. Positive review!

cjh - you need to add your name to the author field.

[sagetrac-mariah]

Reviewer: Mariah Lenox