Changeset 7486:b75f20360b8d

Timestamp:

11/27/07 17:59:55 (5 years ago)

Author:

Carl Witty <cwitty@…>

Branch:

default

Message:

Avoid the "find roots by factoring" algorithm if the coefficient ring is not an integral domain.

File:

• sage/rings/polynomial/polynomial_element.pyx (modified) (4 diffs)

sage/rings/polynomial/polynomial_element.pyx

@@ -2420 +2420 @@
             [(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)]
 
-        An example where the base ring doesn't have a factorization
-        algorithm (yet).  Note that this is currently done via naive
-        enumeration, so could be very slow:
+        A couple of examples where the base ring doesn't have a
+        factorization algorithm (yet).  Note that this is currently
+        done via naive enumeration, so could be very slow:
             sage: R = Integers(6)
             sage: S.<x> = R['x']
@@ -2432 +2432 @@
             sage: p.roots(multiplicities=False)
             [1, 5]
+            sage: R = Integers(9)
+            sage: A = PolynomialRing(R, 'y')
+            sage: y = A.gen()
+            sage: f = 10*y^2 - y^3 - 9
+            sage: f.roots(multiplicities=False)
+            [0, 1, 3, 6]
 
         An example over the complex double field (where root finding
@@ -2599 +2605 @@
         .change_ring(L) and proceed as below.
 
-        The next method is to attempt to factor the polynomial.
-        If this succeeds, then for every degree-one factor a*x+b, we
-        add -b/a as a root (as long as this quotient is actually in
-        the desired ring).
-
-        If factoring over K is not implemented, and K is finite, then
-        we find the roots by enumerating all elements of K and checking
-        whether the polynomial evaluates to zero at that value.
+        The next method, which is used if K is an integral domain, is
+        to attempt to factor the polynomial.  If this succeeds, then
+        for every degree-one factor a*x+b, we add -b/a as a root (as
+        long as this quotient is actually in the desired ring).
+
+        If factoring over K is not implemented (or K is not an
+        integral domain), and K is finite, then we find the roots by
+        enumerating all elements of K and checking whether the
+        polynomial evaluates to zero at that value.
         
 
@@ -2767 +2774 @@
 
         try:
-            rts = self.factor()
+            if K.is_integral_domain():
+                rts = self.factor()
+            else:
+                raise NotImplementedError
         except NotImplementedError:
             if K.is_finite():