# source:sage/rings/polynomial_element.py@3:6ee487e4d475

Revision 3:6ee487e4d475, 73.3 KB checked in by tornaria@…, 7 years ago (diff)

[project @ patch to sage-1.0.0.1]

Line
1"""
2Univariate Polynomials
3"""
4
5#*****************************************************************************
6#       Copyright (C) 2005 William Stein <wstein@ucsd.edu>
7#
9#
10#    This code is distributed in the hope that it will be useful,
11#    but WITHOUT ANY WARRANTY; without even the implied warranty of
12#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13#    General Public License for more details.
14#
15#  The full text of the GPL is available at:
16#
18#*****************************************************************************
19
20import operator
21
22import sage.rings.rational_field
23import sage.rings.integer_ring
24import sage.rings.rational
25import integer
26import finite_field
28import sage.rings.polynomial_ring
29from sage.rings.coerce import bin_op, cmp as coerce_cmp
30import arith
31import sage.rings.ring_element as ring_element
32import sage.rings.euclidean_domain_element as euclidean_domain_element
33import sage.rings.integral_domain_element as integral_domain_element
34import sage.rings.principal_ideal_domain_element as principal_ideal_domain_element
35import integer_ring
36import integer_mod_ring
37import polynomial_pyx
38import rational_field
39import complex_field
40import fraction_field_element
41import fraction_field
42from infinity import infinity
43import sage.misc.misc as misc
44from sage.libs.all import pari, gen
45from sage.libs.ntl.all import ZZ as ntl_ZZ, ZZX, ZZX_class, ZZ_p, ZZ_pX, ZZ_pX_class, set_modulus
46import sage.misc.latex as latex
47import sage.structure.factorization as factorization
48
49from coerce import bin_op
50
51QQ = rational_field.RationalField()
52
53ZZ = integer_ring.IntegerRing()
54
55
56class Polynomial(ring_element.RingElement):
57    """
58    Polynomial base class.
59    """
60    def __init__(self, parent, is_gen = False, construct=False):
61        """
62        The following examples illustrate creation of elements of
63        polynomial rings, and some basic arithmetic.
64
65        First we make a polynomial over the integers and do some arithmetic:
66            sage: x = PolynomialRing(IntegerRing()).gen()
67            sage: f = x^5 + 2*x^2 + (-1); f
68            x^5 + 2*x^2 - 1
69            sage: f^2
70            x^10 + 4*x^7 - 2*x^5 + 4*x^4 - 4*x^2 + 1
71
72        Next we do arithmetic in a sparse polynomial ring over the integers:
73            sage: R = PolynomialRing(IntegerRing(), "x"); x = R.gen(); R
74            Univariate Polynomial Ring in x over Integer Ring
75            sage: S = PolynomialRing(R, "Z"); Z = S.gen(); S
76            Univariate Polynomial Ring in Z over Univariate Polynomial Ring in x over Integer Ring
77            sage: f = Z^3 + (x^2-2*x+1)*Z - 3; f
78            Z^3 + (x^2 - 2*x + 1)*Z + -3
79            sage: f*f
80            Z^6 + (2*x^2 - 4*x + 2)*Z^4 + (-6)*Z^3 + (x^4 - 4*x^3 + 6*x^2 - 4*x + 1)*Z^2 + (-6*x^2 + 12*x - 6)*Z + 9
81            sage: f^3 == f*f*f
82            True
83
84        To have the element print as 'y', give 'y' as the
85        second argument to the PolynomialRing constructor.
86            sage: y = PolynomialRing(IntegerRing(), 'y').gen()
87            sage: y^3 - 2*y
88            y^3 - 2*y
89        """
90        ring_element.RingElement.__init__(self, parent)
91        self._is_gen = is_gen
92
94        if self.degree() >= right.degree():
95            x = list(self.list())
96            y = right.list()
97        else:
98            x = list(right.list())
99            y = self.list()
100
101        for i in xrange(len(y)):
102            x[i] += y[i]
103
104        return self.polynomial(x)
105
106    def __call__(self, *a):
107        """
108        Evaluate polynomial at x=a using Horner's rule
109
110        INPUT:
111            a -- ring element a; need not be in the coefficient
112                 ring of the polynomial.
113
114        OUTPUT:
115            the value of f at a.
116
117        EXAMPLES:
118            sage: x = Q['x'].gen()
119            sage: f = x/2 - 5
120            sage: f(3)
121            -7/2
122            sage: x = Z['x'].gen()
123            sage: f = (x-1)^5
124            sage: f(2/3)
125            -1/243
126
127        AUTHORS:
128            -- David Joyner, 2005-04-10
129            -- William Stein, 2006-01-22; change so parent
130               is determined by the arithmetic
131        """
132        a = a[0]
133        if isinstance(a, tuple):
134            a = a[0]
135        d = self.degree()
136        result = self[d]
137        i = d - 1
138        while i >= 0:
139            result = result * a + self[i]
140            i -= 1
141        return result
142
143    def __cmp__(self, other):
144        if not isinstance(other, Polynomial) or other.parent() != self.parent():
145            return coerce_cmp(self, other)
146        if self.degree() < other.degree():
147            return -1
148        elif self.degree() > other.degree():
149            return 1
150        if self.list() < other.list():
151            return -1
152        elif self.list() > other.list():
153            return 1
154        else:
155            return 0
156
157    def __getitem__(self, n):
158        raise NotImplementedError
159
160    def __hash__(self):
161        return hash((self.degree(), self[0]))
162
163    def __float__(self):
164         if self.degree() > 0:
165             raise TypeError, "cannot coerce nonconstant polynomial to float"
166         return float(self[0])
167
168    def __int__(self):
169        if self.degree() > 0:
170            raise TypeError, "cannot coerce nonconstant polynomial to int"
171        return int(self[0])
172
173    def _im_gens_(self, codomain, im_gens):
174        """
175        EXAMPLES:
176            sage: R, x = PolynomialRing(ZZ).objgen()
177            sage: H = Hom(R, QQ); H
178            Set of Homomorphisms from Univariate Polynomial Ring in x over Integer Ring to Rational Field
179            sage: f = H([5]); f
180            Ring morphism:
181              From: Univariate Polynomial Ring in x over Integer Ring
182              To:   Rational Field
183              Defn: x |--> 5
184            sage: f(x)
185            5
186            sage: f(x^2 + 3)
187            28
188        """
189        a = im_gens[0]
190        P = a.parent()
191        d = self.degree()
192        result = P._coerce_(self[d])
193        i = d - 1
194        while i >= 0:
195            result = result * a + P._coerce_(self[i])
196            i -= 1
197        return result
198
199    def _integer_(self):
200        if self.degree() > 0:
201            raise TypeError, "cannot coerce nonconstant polynomial %s to int"%self
202        return integer.Integer(self[0])
203
204    def __invert__(self):
205        return self.parent()(1)/self
206
207    def inverse_of_unit(self):
208        if self.degree() > 0:
209            raise ValueError, "self is not a unit."
210        return self.parent()(~(self[0]))
211
212    def __long__(self):
213        if self.degree() > 0:
214            raise TypeError, "cannot coerce nonconstant polynomial to long"
215        return long(self[0])
216
217    def _mul_(self, right):
218        """
219        EXAMPLES:
220            sage: x = PolynomialRing(IntegerRing()).gen()
221            sage: (x - 4)*(x^2 - 8*x + 16)
222            x^3 - 12*x^2 + 48*x - 64
223        """
224        if right == 0 or self == 0:
225            return self.polynomial(0)
226        return self._mul_karatsuba(right)
227
228    def _pow(self, right):
229        if self.degree() <= 0:
230            return self.parent()(self[0]**right)
231        if right < 0:
232            return (~self)**(-right)
233        if self._is_gen:   # special case x**n should be faster!
234            z = self.parent()(0)
235            z[right] = 1
236            return z
237        return arith.generic_power(self, right)
238
239    def _repr(self, name=None):
240        s = " "
241        m = self.degree() + 1
242        r = reversed(xrange(m))
243        if name is None:
244            name = self.parent().variable_name()
245        atomic_repr = self.parent().base_ring().is_atomic_repr()
246        coeffs = self.list()
247        for n in reversed(xrange(m)):
248            x = coeffs[n]
249            if x != 0:
250                if n != m-1:
251                    s += " + "
252                x = str(x)
253                if not atomic_repr and n > 0 and (x.find("+") != -1 or x.find("-") != -1):
254                    x = "(%s)"%x
255                if n > 1:
256                    var = "*%s^%s"%(name,n)
257                elif n==1:
258                    var = "*%s"%name
259                else:
260                    var = ""
261                s += "%s%s"%(x,var)
262        if atomic_repr:
263            s = s.replace(" + -", " - ")
264        s = s.replace(" 1*"," ")
265        s = s.replace(" -1*", " -")
266        if s==" ":
267            return "0"
268        return s[1:]
269
270    def _repr_(self):
271        return self._repr()
272
273    def _latex_(self, name=None):
274        s = " "
275        m = self.degree() + 1
276        r = reversed(xrange(m))
277        if name is None:
278            name = self.parent().variable_name()
279        atomic_repr = self.parent().base_ring().is_atomic_repr()
280        coeffs = self.list()
281        for n in reversed(xrange(m)):
282            x = coeffs[n]
283            if x != 0:
284                if n != m-1:
285                    s += " + "
286                x = latex.latex(x)
287                if not atomic_repr and n > 0 and (x.find("+") != -1 or x.find("-") != -1):
288                    x = "\\left(%s\\right)"%x
289                if n > 1:
290                    var = "|%s^{%s}"%(name,n)
291                elif n==1:
292                    var = "|%s"%name
293                else:
294                    var = ""
295                s += "%s%s"%(x,var)
296        if atomic_repr:
297            s = s.replace(" + -", " - ")
298        s = s.replace(" 1|"," ")
299        s = s.replace(" -1|", " -")
300        s = s.replace("|","")
301        if s==" ":
302            return "0"
303        return s[1:]
304
305
306    def __setitem__(self, n, x):
307        raise NotImplentedError
308
309
310    def __floordiv__(self,right):
311        """
312        Quotient of division of self by other.  This is denoted //.
313        """
314        Q, _ = self.quo_rem(right)
315        return Q
316
317    def __mod__(self, other):
318        """
319        Remainder of division of self by other.
320        EXAMPLES:
321            sage: x = PolynomialRing(IntegerRing()).gen()
322            sage: x % (x+1)
323            -1
324            sage: (x^3 + x - 1) % (x^2 - 1)
325            2*x - 1
326        """
327        _, R = self.quo_rem(other)
328        return R
329
330    def _is_atomic(self):
331        return self.degree() == self.valuation()
332
333    def _mul_generic(self, right):
334        d1 = self.degree()
335        d2 = right.degree()
336        d = d1 + d2
337        w = [sum([self[i]*right[k-i] for i in range(0,min(d1,k)+1) if \
338                  i <= d1 and k-i <= d2 and self[i]!=0 and right[k-i]!=0]) \
339                for k in range(d+1)]
340        return Polynomial(self.parent(), w)
341
342    def _mul_karatsuba(self, right):
343        r"""
344        Returns the product of two polynomials using the Karatsuba
345        divide and conquer multiplication algorithm.  This is only
346        used over a generic base ring.  (Special libraries like NTL
347        are used, e.g., for the integers and rationals, which are much
348        faster.)
349
350        INPUT:
351           self: Polynomial
352           right: Polynomial (over same base ring as self)
353
354        OUTPUT: Polynomial
355           The product self*right.
356
357        ALGORITHM:
358           The basic idea is to use that
359           $$360 (aX + b) (cX + d) = acX^2 + ((a+b)(c+d)-ac-bd)X + bd 361$$
362           where ac=a*c and bd=b*d, which requires three
363           multiplications instead of the naive four.  (In my examples,
364           strangely just doing the above with four multiplications
365           does tend to speed things up noticeably.)
366           Given f and g of arbitrary degree bigger than one, let e
367           be min(deg(f),deg(g))/2.  Write
368           $$369 f = a X^e + b \text{ and } g = c X^e + d 370$$
371           and use the identity
372           $$373 (aX^e + b) (cX^e + d) = ac X^{2e} +((a+b)(c+d) - ac - bd)X^e + bd 374$$
375           to recursively compute $fg$.
376
377        TIMINGS:
378        On a Pentium M 1.8Ghz laptop:
379           f=R.random(1000,bound=100)
380           g=R.random(1000,bound=100)
381           time h=f._mul_karatsuba(g)
382           Time: 0.42 seconds
383           The naive multiplication algorithm takes 14.58 seconds.
384           In contrast, MAGMA does this sort of product almost
385           instantly, and can easily deal with degree 5000.  Basically
386           MAGMA is 100 times faster at polynomial multiplication.
387
388           Over Z using NTL, multiplying two polynomials constructed
389           using R.random(10000,bound=100) takes 0.10 seconds.  Using
390           MAGMA V2.11-10 the same takes 0.14 seconds.  So in this
391           case NTL is somewhat faster than MAGMA.
392
393           Over Q using PARI, multiplying two polynomials constructed
394           using R.random(10000,bound=100) takes 1.23 seconds.  Not
395           good!  TODO: use NTL polynomials over Z with a denominator
397
398        NOTES:
399         * Karatsuba multiplication of polynomials is also implemented in PARI in
400                src/basemath/polarit3.c
401         * The MAGMA documentation appears to give no information about how
402           polynomial multiplication is implemented.
403        """
404
405        def sum(v,w):
406            if len(v)>=len(w):
407                x = list(v)
408                y = w
409            else:
410                x = list(w)
411                y = v
412            for i in range(len(y)):
413                x[i] = x[i] + y[i]
414            return x
415        def dif(v,w):
416            if len(v)>=len(w):
417                x = list(v)
418                y = w
419            else:
420                x = list(w)
421                y = v
422            for i in range(len(y)):
423                x[i] -= y[i]
424            return x
425        def do_karatsuba(left, right):
426            if len(left) == 0 or len(right) == 0:
427                return []
428            if len(left) == 1:
429                return [left[0]*a for a in right]
430            if len(right) == 1:
431                return [right[0]*a for a in left]
432            if len(left) == 2 and len(right) == 2:
433                b = left[0]
434                a = left[1]
435                d = right[0]
436                c = right[1]
437                ac = a*c
438                bd = b*d
439                return [bd,(a+b)*(c+d)-ac-bd,ac]
440            e = min(len(left), len(right))/2
441            assert e>=1, "bug in karatsuba"
442            a, b = left[e:], left[:e]
443            c, d = right[e:], right[:e]
444            ac = do_karatsuba(a,c)
445            bd = do_karatsuba(b,d)
446            zeros = [0 for _ in range(e)]
447            t2 = zeros + zeros + ac
448            t1 = zeros + dif(do_karatsuba(sum(a,b),sum(c,d)),sum(ac,bd))
449            t0 = bd
450            return sum(t0,sum(t1,t2))
451        return self.parent()(do_karatsuba(self.list(), right.list()))
452
453    def base_ring(self):
454        """
455        Return the base ring of the parent of self.
456
457        EXAMPLES:
458            sage: x = PolynomialRing(ZZ).gen()
459            sage: x.base_ring()
460            Integer Ring
461            sage: (2*x+3).base_ring()
462            Integer Ring
463        """
464        return self.parent().base_ring()
465
466    def base_extend(self, R):
467        """
468        Return a copy of this polynomial but with coefficients in R.
469        """
470        S = sage.rings.polynomial_ring.PolynomialRing(R,
471                                      name = self.parent().variable_name())
472        return S(self)
473
474    def copy(self):
475        """
476        Return a copy of self.
477
478        EXAMPLES:
479        We create the polynomial $f=x+3$, then set $g=f$, and change
480        the coefficient of $x$ in $g$, which also changes the coefficient
481        of $x$ in $f$.  If we instead copy $f$, then changing the
482        coefficient of $x$ of $g$ does not change $f$.
483
484            sage: x = PolynomialRing(IntegerRing()).gen()
485            sage: f = x+3
486            sage: g = f
487            sage: g[1]=3
488            sage: f
489            3*x + 3
490            sage: g = f.copy()
491            sage: g[1]=5
492            sage: f
493            3*x + 3
494            sage: g
495            5*x + 3
496        """
497        return self.polynomial(self)
498
499    def degree(self):
500        """
501        Return the degree of this polynomial.  The zero polynomial
502        has degree -1.
503
504        EXAMPLES:
505            sage: x = ZZ['x'].0
506            sage: f = x^93 + 2*x + 1
507            sage: f.degree()
508            93
509            sage: x = PolynomialRing(QQ, sparse=True).gen()
510            sage: f = x^100000
511            sage: f.degree()
512            100000
513
514            sage: x = QQ['x'].0
515            sage: f = 2006*x^2006 - x^2 + 3
516            sage: f.degree()
517            2006
518            sage: f = 0*x
519            sage: f.degree()
520            -1
521            sage: f = x + 33
522            sage: f.degree()
523            1
524
525        AUTHORS:
526            -- Naqi Jaffery (2006-01-24): examples
527        """
528        raise NotImplementedError
529
530    def denominator(self):
531        """
532        Return the least common multiple of the denominators of
533        the entries of self, when this makes sense, i.e., when the
534        coefficients have a denominator function.
535
536        WARNING: This is not the denominator of the rational function
537        defined by self, which would always be 1 since self is a polynomial.
538
539        EXAMPLES:
540        First we compute the denominator of a polynomial with integer
541        coefficients, which is of course 1.
542            sage: x = PolynomialRing(IntegerRing()).gen()
543            sage: f = x^3 + 17*x + 1
544            sage: f.denominator()
545            1
546
547        Next we compute the denominator of a polynomial with rational coefficients.
548            sage: Q = RationalField()
549            sage: x = PolynomialRing(Q).gen()
550            sage: f = Q('1/17')*x^19 - Q('2/3')*x + Q('1/3'); f
551            1/17*x^19 - 2/3*x + 1/3
552            sage: f.denominator()
553            51
554
555        Finally, we try to compute the denominator of a polynomial with
556        coefficients in the real numbers, which is a ring whose elements
557        do not have a denominator method.
558            sage: R = RealField()
559            sage: x = PolynomialRing(R).gen()
560            sage: f = x + R('0.3'); f
561            1.0000000000000000*x + 0.29999999999999999
562            sage: f.denominator()
563            Traceback (most recent call last):
564            ...
565            AttributeError: 'mpfr.RealNumber' object has no attribute 'denominator'
566        """
567        if self.degree() == -1:
568            return 1
569        R = self.base_ring()
570        x = self.list()
571        d = x[0].denominator()
572        for y in x:
573            d = d.lcm(y.denominator())
574        return d
575
576    def derivative(self):
577        return self.polynomial([self[n]*n for n in xrange(1,self.degree()+1)])
578
579    def integral(self):
580        try:
581            return self.polynomial([0] + [self[n]/(n+1) for n in xrange(0,self.degree()+1)])
582        except TypeError:
583            raise ArithmeticError, "coefficients of integral of %s cannot be coerced into the base ring"%self
584
585
586    def dict(self):
587        X = {}
588        Y = self.list()
589        for i in xrange(len(Y)):
590            X[i] = Y[i]
591        return X
592
593    def factor(self):
594        r"""
595        Return the factorization of self.
596
597        INPUT:
598            a polynomial
599
600        OUTPUT:
601            Factorization -- the factorization of self
602
603        EXAMPLES:
604        We factor some polynomials over $\Q$.
605            sage: x = PolynomialRing(RationalField()).gen()
606            sage: f = (x^3 - 1)^2
607            sage: f.factor()
608            (x - 1)^2 * (x^2 + x + 1)^2
609            sage: f = 10*x^5 - 1
610            sage: f.factor()
611            (10*x^5 - 1)
612            sage: f = 10*x^5 - 10
613            sage: f.factor()
614            (10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
615
616
617        We factor a non-monic polynomial over the finite field $F_{25}$.
618            sage: k, a = GF(25,'a').objgen()
619            sage: R, x = PolynomialRing(k).objgen()
620            sage: f = 2*x^10 + 2*x + 2*a
621            sage: F = f.factor(); F
622            (2) * (x + a + 2) * (x^2 + (a + 1)*x + a + 2) * (x^2 + 3*x + 4*a + 4) *
623            (x^5 + (3*a + 4)*x^4 + (3*a + 3)*x^3 + 2*a*x^2 + (3*a + 1)*x + 3*a + 1)
624
625        Notice that the unit factor is included when we multiply $F$ back out.
626            sage: F.mul()
627            2*x^10 + 2*x + 2*a
628
629        Factorization also works even if the variable of the finite field is nefariously
630        labeled "x".
631            sage: R, x = PolynomialRing(GF(3^2, 'x')).objgen()
632            sage: f = x^10 +7*x -13
633            sage: f.factor()
634            (x + 2*x + 1) * (x + x) * (x^4 + 2*x*x^3 + (x + 1)*x + 2) * (x^4 + (x + 2)*x^3 + (2*x + 2)*x + 2)
635            sage: f.parent().base_ring().assign_names(['a'])
636            sage: f.factor()
637            (x + 2*a + 1) * (x + a) * (x^4 + 2*a*x^3 + (a + 1)*x + 2) * (x^4 + (a + 2)*x^3 + (2*a + 2)*x + 2)
638
639            sage: k, a = GF(9,'x').objgen()
640            sage: x = PolynomialRing(k,'x0').gen()
641            sage: f = x^3 + x + 1
642            sage: f.factor()
643            (x0 + 2*x + 1) * (x0 + x) * (x0 + 2)
644
645            sage: f = 0*x
646            sage: f.factor()
647            Traceback (most recent call last):
648            ...
649            ValueError: factorization of 0 not defined
650
651            sage: f = x^0
652            sage: f.factor()
653            1
654        """
655
656        # PERFORMANCE NOTE:
657        #     In many tests with SMALL degree PARI is substantially
658        #     better than NTL.  (And magma is better yet.)  And the
659        #     timing difference has nothing to do with moving Python
660        #     data to NTL and back.
661        #     For large degree ( > 1500) in the one test I tried, NTL was
662        #     *much* better than MAGMA, and far better than PARI.  So probably
663        #     NTL's implementation is asymptotically better.  I could use
664        #     PARI for smaller degree over other rings besides Z, and use
665        #     NTL in general.
666
667        R = self.parent().base_ring()
668        if self.degree() < 0:
669            raise ValueError, "factorization of 0 not defined"
670        G = None
671
672        from sage.rings.number_field.all import is_NumberField
673
674        if integer_mod_ring.is_IntegerModRing(R) or finite_field.is_FiniteField(R) or \
675               isinstance(R, (integer_ring.IntegerRing, rational_field.RationalField)):
676
677            G = list(self._pari_('x').factor())
678
679        elif is_NumberField(R):
680
681            v = [x._pari_("a") for x in reversed(self.list())]
682            f = pari(v).Pol()
683            G = list(f.factor())
684
685
686        if G is None:
687            raise NotImplementedError
688        return self._factor_pari_helper(G)
689
690    def _factor_pari_helper(self, G, unit=None):
691        pols = G[0]
692        exps = G[1]
693        F = []
694        R = self.parent()
695        c = R.base_ring()(1)
696        for i in xrange(len(pols)):
697            f = R(pols[i])
698            e = int(exps[i])
700            F.append((f,e))
701        if unit is None:
703        if not unit.is_unit():
704            F.append((R(unit), 1))
705            unit = R.base_ring()(1)
706        return factorization.Factorization(F, unit)
707
708    def _lcm(self, other):
709        """
710        Let f and g be two polynomials.  Then this function
711        returns the monic least common multiple of f and g.
712        """
713        f = self*other
714        g = self.gcd(other)
715        q = f//
716        return ~(q[q.degree()])*# make monic  (~ is inverse in python)
717
718    def is_constant(self):
719        return self.degree() <= 0
720
721    def constant_coefficient(self):
722        return self[0]
723
724    def is_monic(self):
725        """
726        Returns True if this polynomial is monic.  The zero
727        polynomial is by definition not monic.
728
729        EXAMPLES:
730            sage: x = QQ['x'].0
731            sage: f = x + 33
732            sage: f.is_monic()
733            True
734            sage: f = 0*x
735            sage: f.is_monic()
736            False
737            sage: f = 3*x^3 + x^4 + x^2
738            sage: f.is_monic()
739            True
740            sage: f = 2*x^2 + x^3 + 56*x^5
741            sage: f.is_monic()
742            False
743
744        AUTHORS:
745            -- Naqi Jaffery (2006-01-24): examples
746        """
747        return not self.is_zero() and self[self.degree()] == 1
748
749    def is_unit(self):
750        if self.degree() > 0:
751            return False
752        return self[0].is_unit()
753
754    def is_gen(self):
755        return self._is_gen
756
757    def is_zero(self):
758        return self.degree() == -1
759
761        return self[self.degree()]
762
763    def monic(self):
764        """
765        Return this polynomial divided by its leading coefficient.
766        Does not change this polynomial.
767
768        EXAMPLES:
769            sage: x = QQ['x'].0
770            sage: f = 2*x^2 + x^3 + 56*x^5
771            sage: f.monic()
772            x^5 + 1/56*x^3 + 1/28*x^2
773            sage: f = (1/4)*x^2 + 3*x + 1
774            sage: f.monic()
775            x^2 + 12*x + 4
776
777    The following happens because $f = 0$ cannot be made into a monic polynomial
778            sage: f = 0*x
779            sage: f.monic()
780            Traceback (most recent call last):
781            ...
782            ZeroDivisionError: rational division by zero
783
784        Notice that the monic version of a polynomial over the
785        integers is defined over the rationals.
786            sage: x = ZZ['x'].0
787            sage: f = 3*x^19 + x^2 - 37
788            sage: g = f.monic(); g
789            x^19 + 1/3*x^2 - 37/3
790            sage: g.parent()
791            Univariate Polynomial Ring in x over Rational Field
792
793
794        AUTHORS:
795            -- Naqi Jaffery (2006-01-24): examples
796        """
797        if self.is_monic():
798            return self
800        R = self.parent()
801        if a.parent() != R.base_ring():
802            S = R.base_extend(a.parent())
803            return a*S(self)
804        else:
805            return a*self
806
807
808    def list(self):
809        raise NotImplementedError
810
811    def newton_raphson(self, n, x0):
812        """
813        Return a list of n iterative approximations to a root of this
814        polynomial, computed using the Newton-Raphson method.
815
816        The Newton-Raphson method is an iterative root-finding algorithm.
817        For f(x) a polynomial, as is the case here, this is essentially
818        the same as Horner's method.
819
820        INPUT:
821           n -- an integer (=the number of iterations),
822           x0 -- an initial guess x0.
823
824        OUTPUT:
825           A list of numbers hopefully approximating a root of f(x)=0.
826
827           ** If one of the iterates is a critical point of f then
828              a ZeroDivisionError exception is raised.
829
830        EXAMPLES:
831            sage: x = PolynomialRing(RealField(), 'x').gen()
832            sage: f = x^2 - 2
833            sage: f.newton_raphson(4, 1)
834            [1.5000000000000000, 1.4166666666666667, 1.4142156862745099, 1.4142135623746899]
835
836        AUTHORS: David Joyner and William Stein (2005-11-28)
837        """
838        n = integer.Integer(n)
839        df = self.derivative()
840        def newton(z):
841            return z -  self(z) / df(z)
842        K = self.parent().base_ring()
843        a = K(x0)
844        L = []
845        for i in range(n):
846            a = newton(a)
847            L.append(a)
848        return L
849
850    def polynomial(self, *args, **kwds):
851        return self.parent()(*args, **kwds)
852
853    def _pari_(self, variable=None):
854        """
855        Return polynomial as a PARI object.  Note that
856        the variable will be "x" unless you explicitly specify
857        otherwise, no matter what the polynomial indeterminate
858        is.
859        """
860        try:
861            return self.__pari
862        except AttributeError:
863            v = list(reversed(self.list()))
864            try:
865                v = [x._pari_() for x in v]
866            except AttributeError:
867                pass
868            if variable is None:
869                variable = self.parent().variable_name()
870            self.__pari = pari(v).Pol(variable)
871            return self.__pari
872
873    def _pari_init_(self):
874        return str(self._pari_())
875
876    def resultant(self, other, flag=0):
877        raise NotImplementedError
878
879        ## This should be switched to use NTL, which can apparently compute
880        ## resultants!
881        ##        void XGCD(ZZ& r, ZZX& s, ZZX& t, const ZZX& a, const ZZX& b,
882        ##          long deterministic=0);
883        ##// r = resultant of a and b; if r != 0, then computes s and t such
884        ##// that: a*s + b*t = r; otherwise s and t not affected.  if
885        ##// !deterministic, then resultant computation may use a randomized
886        ##// strategy that errs with probability no more than 2^{-80}.
887        #m = magma.Magma()
888        #cmd = "R<%s> := PolynomialRing(RationalField()); "%self.parent().variable_name() + \
889        #      "Resultant(%s, %s);"%(self,other)
890        #s = m.cmd(cmd)
891        #i = s.find("\r")
892        #return eval(s[:i])
893
894    def reverse(self):
895        v = list(self.list())
896        v.reverse()
897        return self.parent()(v)
898
899    def roots(self):
900        """
901        Return all roots of this polynomial.
902
903        EXAMPLES:
904            sage: x = PolynomialRing(RationalField()).gen()
905            sage: f = x^3 - 1
906            sage: f.roots()
907            [(1, 1)]
908            sage: f = (x^3 - 1)^2
909            sage: f.roots()
910            [(1, 2)]
911
912            sage: f = -19*x + 884736
913            sage: f.roots()
914            [(884736/19, 1)]
915            sage: (f^20).roots()
916            [(884736/19, 20)]
917        """
918        seq = []
919        try:
920            rts = self.factor()
921        except NotImplementedError:
922            raise NotImplementedError, "root finding for this polynomial not implemented"
923        for fac in rts:
924            g = fac[0]
925            if g.degree() == 1:
926                seq.append((-g[0]/g[1],fac[1]))
927        return seq
928
929    def valuation(self):
930        r"""
931        If $f = a_r x^r + a_{r+1}x^{r+1} + \cdots$, with $a_r$ nonzero,
932        then the valuation of $f$ is $r$.  The valuation of the zero
933        polynomial is $\infty$.
934        """
935        if self.is_zero():
936            return infinity
937        for i in xrange(self.degree()+1):
938            if self[i] != 0:
939                return i
940        raise RuntimeError, "bug in computing valuation of polynomial"
941
942    def name(self):
943        return self.parent().variable_name()
944
945    def _xgcd(self, other):
946        r"""
947        Extended gcd of self and polynomial other.
948
949        Returns g, u, and v such that
950              \code{g = u*self + v*other.}
951
952        EXAMPLES:
953            sage: P, x = PolynomialRing(QQ).objgen()
954            sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
955            sage: g, u, v = F.xgcd(G)
956            sage: g, u, v
957            (27*x^2 + 54, 1, -x^2 - 3*x - 9)
958            sage: u*F + v*G
959            27*x^2 + 54
960            sage: x.xgcd(P(0))
961            (1, 0, x)
962            sage: f = P(0)
963            sage: f.xgcd(x)
964            (x, 0, 1)
965        """
966        if other.is_zero():
967            R = self.parent()
968            return R(1), R(0), self
969        # Algorithm 3.2.2 of Cohen, GTM 138
970        R = self.parent()
971        A = self
972        B = other
973        U = R(1)
974        G = A
975        V1 = R(0)
976        V3 = B
977        while V3.is_nonzero():
978            Q, R = G.quo_rem(V3)
979            T = U - V1*Q
980            U = V1
981            G = V3
982            V1 = T
983            V3 = R
984        V = (G-A*U)//B
985        return G, U, V
986
987    def is_irreducible(self):
988        F = self.factor()
989        if len(F) > 1 or F[0][1] > 1:
990            return False
991        return True
992
993
994    def truncate(self, n):
995        r"""
996        Replace this polynomial by $\sum a_m x^m$ where the sum is
997        over $m < n$.  The resulting polynomial is equivalent to self
998        modulo $x^n$.
999        """
1000        return self.parent()(self[:int(n)], check=False)
1001
1002
1003class Polynomial_generic_dense(Polynomial):
1004    """
1005    A generic dense polynomial.
1006
1007    EXAMPLES:
1008        sage: R, x = PolynomialRing(PolynomialRing(Q)).objgen()
1009        sage: f = x^3 - x + 17
1010        sage: type(f)
1011        <class 'sage.rings.polynomial_element.Polynomial_generic_dense'>
1013        True
1014    """
1015    def __init__(self, parent, x=None, check=True, is_gen=False, construct=False):
1016        Polynomial.__init__(self, parent, is_gen=is_gen)
1017        if x == None:
1018            self.__coeffs = []
1019            return
1020        R = parent.base_ring()
1021#        if isinstance(x, Polynomial) and x.parent() == self.parent():
1022#            x = list(x.list())
1023        if isinstance(x, Polynomial):
1024            if x.parent() == self.parent():
1025                x = list(x.list())
1026            elif x.parent() == R:
1027                x = [x]
1028            else:
1029                x = [R(a) for a in x.list()]
1030                check = False
1031                #raise TypeError, "Cannot coerce %s into %s."%(x, parent)
1032        elif isinstance(x, dict):
1033            zero = R(0)
1034            n = max(x.keys())
1035            v = [zero for _ in xrange(n+1)]
1036            for i, z in x.iteritems():
1037                v[i] = z
1038            x = v
1039        elif isinstance(x, gen):
1040            x = [R(w) for w in reversed(x.Vec())]
1041            check = True
1042        elif not isinstance(x, list):
1043            x = [x]   # constant polynomials
1044        if check:
1045            self.__coeffs = [R(z) for z in x]
1046        else:
1047            self.__coeffs = x
1048        if check:
1049            self.__normalize()
1050
1051    def __normalize(self):
1052        x = self.__coeffs
1053        n = len(x)-1
1054        while n>=0 and x[n] == 0:
1055            del x[n]
1056            n -= 1
1057
1058    def __getitem__(self,n):
1059        if n < 0 or n >= len(self.__coeffs):
1060            return self.base_ring()(0)
1061        return self.__coeffs[n]
1062
1063    def __getslice__(self, i, j):
1064        if i < 0:
1065            i = 0
1066        v = self.__coeffs[i:j]
1067        zero = self.base_ring()(0)
1068        for k in xrange(len(self.__coeffs),j):
1069            v.append(zero)
1070        return v
1071
1072    def __setitem__(self, n, value):
1073        if self._is_gen:
1074            raise ValueError, "the generator cannot be changed"
1075        n = int(n)
1076        value = self.base_ring()(value)
1077        if n >= 0 and n < len(self.__coeffs):
1078            self.__coeffs[n] = value
1079            if n == len(self.__coeffs) and value == 0:
1080                self.__normalize()
1081        elif n < 0:
1082            raise IndexError, "polynomial coefficient index must be nonnegative"
1083        elif value != 0:
1084            zero = self.base_ring()(0)
1085            for _ in xrange(len(self.__coeffs), n):
1086                self.__coeffs.append(zero)
1087            self.__coeffs.append(value)
1088
1089    def list(self):
1090        return self.__coeffs
1091
1092    def degree(self):
1093        return len(self.__coeffs) - 1
1094
1095
1096class Polynomial_generic_sparse(Polynomial):
1097    """
1098    A generic sparse polynomial.
1099
1100    EXAMPLES:
1101        sage: R, x = PolynomialRing(PolynomialRing(Q), sparse=True).objgen()
1102        sage: f = x^3 - x + 17
1103        sage: type(f)
1104        <class 'sage.rings.polynomial_element.Polynomial_generic_sparse'>
1106        True
1107    """
1108    def __init__(self, parent, x=None, check=True, is_gen=False, construct=False):
1109        Polynomial.__init__(self, parent, is_gen=is_gen)
1110        if x == None:
1111            self.__coeffs = {}
1112            return
1113        R = parent.base_ring()
1114        if isinstance(x, Polynomial):
1115            if x.parent() == self.parent():
1116                x = dict(x.dict())
1117            elif x.parent() == R:
1118                x = {0:x}
1119            else:
1120                w = {}
1121                for n, c in x.dict().iteritems():
1122                    w[n] = R(c)
1123                #raise TypeError, "Cannot coerce %s into %s."%(x, parent)
1124        elif isinstance(x, list):
1125            y = {}
1126            for i in xrange(len(x)):
1127                if x[i] != 0:
1128                    y[i] = x[i]
1129            x = y
1130        elif not isinstance(x, dict):
1131            x = {0:x}   # constant polynomials
1132        elif isinstance(x, gen):
1133            x = [R(w) for w in reversed(x.Vec())]
1134            check = True
1135        if check:
1136            self.__coeffs = {}
1137            for i, z in x.iteritems():
1138                self.__coeffs[i] = R(z)
1139        else:
1140            self.__coeffs = x
1141        if check:
1142            self.__normalize()
1143
1144
1145    def __normalize(self):
1146        x = self.__coeffs
1147        zero = self.base_ring()(0)
1148        D = [n for n, z in x.iteritems() if z == 0]
1149        for n in D:
1150            del x[n]
1151
1152    def __getitem__(self,n):
1153        if not self.__coeffs.has_key(n):
1154            return self.base_ring()(0)
1155        return self.__coeffs[n]
1156
1157    def __getslice__(self, i, j):
1158        if i < 0:
1159            i = 0
1160        zero = self.base_ring()(0)
1161        v = [zero for _ in xrange(i,j)]
1162        x = self.__coeffs
1163        for k in set(x.keys()).intersection(set(xrange(i,j))):
1164            v[k] = x[k]
1165        return v
1166
1167    def __setitem__(self, n, value):
1168        if self._is_gen:
1169            raise ValueError, "the generator cannot be changed"
1170        n = int(n)
1171        value = self.base_ring()(value)
1172        x = self.__coeffs
1173        if n < 0:
1174            raise IndexError, "polynomial coefficient index must be nonnegative"
1175        if value == 0:
1176            if x.has_key(n):
1177                del x[n]
1178        else:
1179            x[n] = value
1180
1181    def list(self):
1182        zero = self.base_ring()(0)
1183        v = [zero for _ in xrange(self.degree()+1)]
1184        for n, x in self.__coeffs.iteritems():
1185            v[n] = x
1186        return v
1187
1188    #def _pari_(self, variable=None):
1189    #    if variable is None:
1190    #        return self.__pari
1191    #    else:
1192    #        return self.__pari.subst('x',variable)
1193
1194    def degree(self):
1195        v = self.__coeffs.keys()
1196        if len(v) == 0:
1197            return -1
1198        return max(v)
1199
1200
1201class Polynomial_generic_field(Polynomial, euclidean_domain_element.EuclideanDomainElement):
1202    def __init__(self, parent, is_gen=False, construct=False):
1203        Polynomial.__init__(self, parent, is_gen=is_gen)
1204
1205    def quo_rem(self, other):
1206        """
1207        Returns a tuple (quotient, remainder) where
1208            self = quotient*other + remainder.
1209
1210        EXAMPLES:
1211            sage: K = NumberField(x**ZZ(2)-ZZ(2),'t')
1212            sage: P, x = PolynomialRing(K).objgen()
1213            sage: x.quo_rem(K(1))
1214            (x, 0)
1215            sage: x.xgcd(K(1))
1216            (1, 0, 1)
1217        """
1218        other = self.parent()(other)
1219        if other.is_zero():
1220            raise ZeroDivisionError, "other (=%s) must be nonzero"%other
1221
1222        # This is algorithm 3.1.1 in Cohen GTM 138
1223        A = self
1224        B = other
1225        R = A
1226        Q = self.polynomial(0)
1227        X = self.parent().gen()
1228        while R.degree() >= B.degree():
1230            Q += S
1231            R -= S*B
1232        return (Q, R)
1233
1234    def _gcd(self, other):
1235        """
1236        Return the GCD of self and other, as a monic polynomial.
1237        """
1238        g = euclidean_domain_element.EuclideanDomainElement._gcd(self, other)
1240        if c.is_unit():
1241            return (1/c)*g
1242        return g
1243
1244
1245class Polynomial_generic_sparse_field(Polynomial_generic_sparse, Polynomial_generic_field):
1246    """
1247    EXAMPLES:
1248        sage: R, x = PolynomialRing(RealField(), sparse=True).objgen()
1249        sage: f = x^3 - x + 17
1250        sage: type(f)
1251        <class 'sage.rings.polynomial_element.Polynomial_generic_sparse_field'>
1253        True
1254    """
1255    def __init__(self, parent, x=None, check=True, is_gen = False, construct=False):
1256        Polynomial_generic_sparse.__init__(self, parent, x, check, is_gen)
1257
1258
1259class Polynomial_generic_dense_field(Polynomial_generic_dense, Polynomial_generic_field):
1260    def __init__(self, parent, x=None, check=True, is_gen = False, construct=False):
1261        Polynomial_generic_dense.__init__(self, parent, x, check, is_gen)
1262
1263
1264class Polynomial_rational_dense(Polynomial_generic_field):
1265    """
1266    A dense polynomial over the rational numbers.
1267    """
1268    def __init__(self, parent, x=None, check=True, is_gen=False, construct=False):
1269        Polynomial.__init__(self, parent, is_gen=is_gen)
1270
1271        if construct:
1272            self.__poly = x
1273            return
1274
1275        self.__poly = pari([]).Pol()
1276
1277        if x is None:
1278            return         # leave initialized to 0 polynomial.
1279
1280
1281        if fraction_field_element.is_FractionFieldElement(x):
1282            if x.denominator() != 1:
1283                raise TypeError, "denominator (=%s) must be 1"%x.denominator()
1284            else:
1285                x = x.numerator()
1286
1287        if isinstance(x, Polynomial):
1288            if x.parent() == self.parent():
1289                self.__poly = x.__poly.copy()
1290                return
1291            else:
1292                x = [QQ(a) for a in x.list()]
1293                check = False
1294
1295        if isinstance(x, dict):
1296            zero = QQ(0)
1297            n = max(x.keys())
1298            v = [zero for _ in xrange(n+1)]
1299            for i, z in x.iteritems():
1300                v[i] = z
1301            x = v
1302
1303        elif isinstance(x, gen):
1304            f = x.Pol()
1305            self.__poly = f
1306            assert self.__poly.type() == "t_POL"
1307            return
1308
1309        elif not isinstance(x, list):
1310            x = [x]   # constant polynomials
1311
1312        if check:
1313            x = [QQ(z) for z in x]
1314
1315        self.__list = list(x)
1316        while len(self.__list) > 0 and self.__list[-1] == 0:
1317            del self.__list[-1]
1318
1319        x.reverse()
1320
1321        # NOTE: It is much faster to convert to string and let pari's parser at it,
1322        # which is why we pass str(x) in.
1323        self.__poly = pari(str(x)).Pol()
1324        assert self.__poly.type() == "t_POL"
1325
1326    def _repr(self, name=None):
1327        if name is None:
1328            name = self.parent().variable_name()
1329        return str(self.__poly).replace("x", name)
1330
1331    def _repr_(self):
1332        return self._repr()
1333
1334    def __reduce__(self):
1335        return Polynomial_rational_dense, \
1336               (self.parent(), self.list(), False, self.is_gen())
1337
1338    def __getitem__(self, n):
1339        return QQ(self.__poly[n])
1340
1341    def __getslice__(self, i, j):
1342        return [QQ(self.__poly[k]) for k in range(i,j)]
1343
1344    def _pow(self, n):
1345        if self.degree() <= 0:
1346            return self.parent()(self[0]**n)
1347        if n < 0:
1348            return (~self)**(-n)
1349        return Polynomial_rational_dense(self.parent(), self.__poly**n, construct=True)
1350
1352        return Polynomial_rational_dense(self.parent(),
1353                                         self.__poly + right.__poly, construct=True)
1354
1355    def is_irreducible(self):
1356        try:
1357            return self.__poly.polisirreducible()
1358        except NotImplementedError:
1359            F = self.__poly.factor()
1360            if len(F) > 1 or F[0][1] > 1:
1361                return False
1362            return True
1363
1364    def galois_group(self, pari_group=False, use_kash=False):
1365        r"""
1366        Return the Galois group of f as a permutation group.
1367
1368        INPUT:
1369            self -- an irreducible polynomial
1370
1371            pari_group -- bool (default: False); if True instead return
1372                          the Galois group as a PARI group.  This has
1373                          a useful label in it, and may be slightly faster
1374                          since it doesn't require looking up a group in
1375                          Gap.  To get a permutation group from a PARI
1376                          group P, type PermutationGroup(P).
1377
1378            use_kash --   bool (default: False); if True use KASH's Galois
1379                          command instead of using the PARI C library.
1380                          An attempt is always made to use KASH if the
1381                          degree of the polynomial is >= 12.
1382
1383        ALGORITHM: The Galois group is computed using PARI in C
1384        library mode, or possibly kash if available.
1385
1386        \note{ The PARI documentation contains the following warning:
1387        The method used is that of resolvent polynomials and is
1388        sensitive to the current precision. The precision is updated
1389        internally but, in very rare cases, a wrong result may be
1390        returned if the initial precision was not sufficient.}
1391
1392        EXAMPLES:
1393            sage: f = x^4 - 17*x^3 - 2*x + 1
1394            sage: G = f.galois_group(); G            # uses optional database_gap package
1395            Transitive group number 5 of degree 4
1396            sage: G.gens()                           # uses optional database_gap package
1397            ((1,2,3,4), (1,2))
1398            sage: G.order()                          # uses optional database_gap package
1399            24
1400
1401        It is potentially useful to instead obtain the corresponding
1402        PARI group, which is little more than a $4$-tuple.  See the
1403        PARI manual for the exact details.  (Note that the third
1404        entry in the tuple is in the new standard ordering.)
1405            sage: f = x^4 - 17*x^3 - 2*x + 1
1406            sage: G = f.galois_group(pari_group=True); G
1407            PARI group [24, -1, 5, "S4"] of degree 4
1408            sage: PermutationGroup(G)                # uses optional database_gap package
1409            Transitive group number 5 of degree 4
1410
1411        You can use KASH to compute Galois groups as well.  The
1412        avantage is that KASH can compute Galois groups of fields up
1413        to degree 23, whereas PARI only goes to degree 11.  (In my
1414        not-so-thorough experiments PARI is faster than KASH.)
1415
1416            sage: f = x^4 - 17*x^3 - 2*x + 1
1417            sage: f.galois_group(use_kash=true)      # requires optional KASH
1418            Transitive group number 5 of degree 4
1419
1420        """
1421        from sage.groups.all import PariGroup, PermutationGroup, TransitiveGroup
1422        if self.degree() > 11 or use_kash:
1423            # TODO -- maybe use KASH if available or print message that user should install KASH?
1424            try:
1425                from sage.interfaces.all import kash
1426                s = self._repr(name='X')
1427                G = kash('Galois(%s)'%s)
1428                d = int(kash.eval('%s.ext1'%G.name()))
1429                n = int(kash.eval('%s.ext2'%G.name()))
1430                return TransitiveGroup(d, n)
1431            except RuntimeError:
1432                raise NotImplementedError, "Sorry, computation of Galois groups of fields of degree bigger than 11 is not yet implemented.  Try installing the optional free (closed source) KASH package, which supports up to degree $23$."
1433        G = self.__poly.polgalois()
1434        H = PariGroup(G, self.degree())
1435        if pari_group:
1436            return H
1437        else:
1438            return PermutationGroup(H)
1439
1440    def quo_rem(self, right):
1441        """
1442        Returns a tuple (quotient, remainder) where
1443            self = quotient*other + remainder.
1444        """
1445        if not isinstance(right, Polynomial_rational_dense):
1446            right = self.parent()(right)
1447        if right.parent() != self.parent():
1448            raise TypeError
1449        v = self.__poly.divrem(right.__poly)
1450        return Polynomial_rational_dense(self.parent(), v[0], construct=True), \
1451               Polynomial_rational_dense(self.parent(), v[1], construct=True)
1452
1453
1454    def _mul_(self, right):
1455        """
1456        EXAMPLES:
1457            sage: x = PolynomialRing(QQ).gen()
1458            sage: (x - QQ('2/3'))*(x^2 - 8*x + 16)
1459            x^3 - 26/3*x^2 + 64/3*x - 32/3
1460        """
1461        return self.parent()(self.__poly * right.__poly, construct=True)
1462
1463    def _sub_(self, right):
1464        return self.parent()(self.__poly - right.__poly, construct=True)
1465
1466    def __setitem__(self, n, value):
1467        try:
1468            del self.__list
1469        except AttributeError:
1470            pass
1471        if self._is_gen:
1472            raise ValueError, "the generator cannot be changed"
1473        n = int(n)
1474        if n < 0:
1475            raise IndexError, "n (=%s) must be >= 0"%n
1476        if n <= self.__poly.poldegree():
1477            self.__poly[n] = QQ(value)
1478        else:
1479            self.__poly = self.__poly + pari('(%s)*x^%s'%(QQ(value),n))
1480        if hasattr(self, "__list"):
1481            del self.__list
1482
1483    def complex_roots(self, flag=0):
1484        """
1485        Returns the complex roots of this polynomial.
1486        INPUT:
1487            flag -- optional, and can be
1488                    0: (default), uses Schonhage's method modified by Gourdon,
1489                    1: uses a modified Newton method.
1490        OUTPUT:
1491            list of complex roots of this polynomial, counted with multiplicities.
1492
1493        NOTE: Calls the pari function polroots.
1494
1495        EXAMPLE:
1496        We compute the roots of the characteristic polynomial of some Salem numbers:
1497            sage: R = PolynomialRing(QQ); x = R.gen()
1498            sage: f = 1 - x^2 - x^3 - x^4 + x^6
1499            sage: f.complex_roots()[0]
1500            0.71363917353690087
1501        """
1502        R = self.__poly.polroots(flag)
1503        C = complex_field.CC
1504        return [C(a) for a in R]
1505
1506    def copy(self):
1507        f = Polynomial_rational_dense(self.parent())
1508        f.__poly = self.__poly.copy()
1509        return f
1510
1511    def degree(self):
1512        """
1513        Return the degree of this polynomial.  The zero polynomial
1514        has degree -1.
1515        """
1516        return max(self.__poly.poldegree(), -1)
1517
1518    def discriminant(self):
1519        """
1520        EXAMPLES:
1521            sage: x = PolynomialRing(QQ).gen()
1522            sage: f = x^3 + 3*x - 17
1523            sage: f.discriminant()
1524            -7911
1525        """
1526        return QQ(self.__poly.poldisc())
1527
1528    def disc(self):
1529        """
1530        Same as discriminant().
1531        """
1532        return self.discriminant()
1533
1534    def factor_mod(self, p):
1535        """
1536        Return the factorization of self modulo the prime p.
1537
1538        INPUT:
1539            p -- prime
1540
1541        OUTPUT:
1542            factorization of self reduced modulo p.
1543        """
1544        p = integer.Integer(p)
1545        if not p.is_prime():
1546            raise ValueError, "p (=%s) must be prime"%p
1547        G = self._pari_().factormod(p)
1548        K = finite_field.FiniteField(p)
1549        R = sage.rings.polynomial_ring.PolynomialRing(K, name=self.parent().variable_name())
1551
1553        """
1554        Return p-adic factorization of self to given precision.
1555
1556        INPUT:
1557            p -- prime
1558            prec -- integer; the precision
1559
1560        OUTPUT:
1561            factorization of self reduced modulo p.
1562        """
1563        p = integer.Integer(p)
1564        if not p.is_prime():
1565            raise ValueError, "p (=%s) must be prime"%p
1566        prec = integer.Integer(prec)
1567        if prec <= 0:
1568            raise ValueError, "prec (=%s) must be positive"%prec
1571        R = sage.rings.polynomial_ring.PolynomialRing(K, name=self.parent().variable_name())
1573
1574    def list(self):
1575        """
1576        EXAMPLES:
1577            sage: x = PolynomialRing(QQ).gen()
1578            sage: f = x^3 + 3*x - QQ('17/13')
1579            sage: f.list()
1580            [-17/13, 3, 0, 1]
1581        """
1582        try:
1583            return self.__list
1584        except AttributeError:
1585            self.__list = [QQ(x) for x in reversed(self.__poly.Vec())]
1586            return self.__list
1587
1588    def rescale(self, a):
1589        """
1590        Return f(a*X).
1591        """
1592        b = 1
1593        c = []
1594        for i in range(self.degree()+1):
1595            c.append(self[i]*b)
1596            b *= a
1597        return self.parent()(c)
1598
1599    def resultant(self, other):
1600        """
1601        Returns the resultant of self and other, which must lie in the same
1602        polynomial ring.
1603
1604        INPUT:
1605            other -- a polynomial
1606        OUTPUT:
1607            an element of the base ring of the polynomial ring
1608
1609        NOTES:
1610            Implemented using pari's polresultant function.
1611
1612        EXAMPLES:
1613            sage: x = PolynomialRing(RationalField()).gen()
1614            sage: f = x^3 + x + 1;  g = x^3 - x - 1
1615            sage: f.resultant(g)
1616            -8
1617        """
1618        if not isinstance(other, Polynomial):
1619            other = self.polynomial(other)
1620        if self.parent() != other.parent():
1621            raise TypeError
1622        return QQ(str(self.__poly.polresultant(other.__poly, 0)))
1623
1624    def hensel_lift(self, p, e):
1625        """
1626        Assuming that self factors modulo $p$ into distinct factors,
1627        computes the Hensel lifts of these factors modulo $p^e$.  We
1628        assume that $p$ has integer coefficients.
1629        """
1630        p = integer.Integer(p)
1631        if not p.is_prime():
1632            raise ValueError, "p (=%s) must be prime"%p
1633        e = integer.Integer(e)
1634        if e < 1:
1635            raise ValueError, "e (=%s) must be at least 1"%e
1636        F = self.factor_mod(p)
1637        y = []
1638        for g, n in F:
1639            if n > 1:
1640                raise ArithmeticError, "The polynomial must be square free modulo p."
1641            y.append(g)
1642        H = self._pari_().polhensellift(y, p, e)
1643        R = integer_mod_ring.IntegerModRing(p**e)
1644        S = sage.rings.polynomial_ring.PolynomialRing(R, self.parent().variable_name())
1645        return [S(eval(str(m.Vec().Polrev().Vec()))) for m in H]
1646
1647class Polynomial_integer_dense(Polynomial, integral_domain_element.IntegralDomainElement):
1648    """
1649    A dense polynomial over the integers.
1650    """
1651    def __init__(self, parent, x=None, check=True, is_gen=False, construct=False):
1652        Polynomial.__init__(self, parent, is_gen=is_gen)
1653        if construct:
1654            if isinstance(x, ZZX_class):
1655                self.__poly = x
1656                return
1657            self.__poly = ZZX(x)
1658            return
1659
1660        self.__poly = ZZX([])
1661
1662        if x == None:
1663            return         # leave initialized to 0 polynomial.
1664
1665        if isinstance(x, Polynomial):
1666            if x.parent() == self.parent():
1667                self.__poly = x.__poly.copy()
1668                return
1669            else:
1670                x = [ZZ(a) for a in x.list()]
1671                check = False
1672
1673        if isinstance(x, dict):
1674            zero = ZZ(0)
1675            n = max(x.keys())
1676            v = [zero for _ in xrange(n+1)]
1677            for i, z in x.iteritems():
1678                v[i] = z
1679            x = v
1680
1681        elif isinstance(x, ZZX_class):
1682            self.__poly = x.copy()
1683            return
1684
1685        elif isinstance(x, gen):
1686            x = list(reversed(x.list()))
1687            check = False
1688
1689        elif isinstance(x, fraction_field_element.FractionFieldElement) and \
1690                 isinstance(x.numerator(), Polynomial_integer_dense):
1691            if x.denominator() == 1:
1692                x = x.numerator().__poly
1693                check = False
1694
1695        elif not isinstance(x, list):
1696            x = [x]   # constant polynomials
1697
1698        if check:
1699            x = [ZZ(z) for z in x]
1700
1701        self.__poly = ZZX(x)
1702
1703    def content(self):
1704        """
1705        Return the greatest common divisor of the coefficients of this
1706        polynomial.
1707        """
1708        return ZZ(self.__poly.content())
1709
1710    def ntl_ZZX(self):
1711        """
1712        Return underlying NTL representation of this polynomial.
1713        Additional bonus'' functionality may be available through
1714        this function.
1715        """
1716        return self.__poly
1717
1718    def __reduce__(self):
1719        return Polynomial_integer_dense, \
1720               (self.parent(), self.list(), False, self.is_gen())
1721
1722    def __getitem__(self, n):
1723        return ZZ(self.__poly[n])
1724
1725    def __getslice__(self, i, j):
1726        return [ZZ(self.__poly[k]) for k in range(i,j)]
1727
1728    def _pow(self, n):
1729        if self.degree() <= 0:
1730            return self.parent()(self[0]**n)
1731        if n < 0:
1732            return (~self)**(-n)
1733        return self.parent()(self.__poly**n, construct=True)
1734
1736        return self.parent()(self.__poly + right.__poly, construct=True)
1737
1738    def quo_rem(self, right):
1739        """
1740        Returns a tuple (quotient, remainder) where
1741            self = quotient*other + remainder.
1742        """
1743        if not isinstance(right, Polynomial_integer_dense):
1744            right = self.parent()(right)
1745        elif self.parent() != right.parent():
1746            raise TypeError
1747        v = self.__poly.quo_rem(right.__poly)
1748        return self.parent()(v[0], construct=True), \
1749               self.parent()(v[1], construct=True)
1750
1751    def gcd(self, right):
1752        """
1753        Return the GCD of self and other.  The leading
1754        coefficient need not be 1.
1755        """
1756        if not isinstance(right, Polynomial_integer_dense):
1757            right = self.parent()(right)
1758        elif self.parent() != right.parent():
1759            raise TypeError
1760        g = self.__poly.gcd(right.__poly)
1761        return self.parent()(g, construct=True)
1762
1763    def lcm(self, right):
1764        """
1765        Return the LCM of self and other, as a monic polynomial.
1766        """
1767        if not isinstance(right, Polynomial_integer_dense):
1768            right = self.parent()(right)
1769        elif self.parent() != right.parent():
1770            raise TypeError
1771        g = self.__poly.lcm(right.__poly)
1772        return self.parent()(g, construct=True)
1773
1774    def xgcd(self, right):
1775        """
1776        Return $g, u, v$ such that \code{g = u*self + v*right}.
1777
1778        If self and right are coprime as polynomials over the
1779        rationals, then $g$ is guaranteed to be the resultant of self
1780        and right, as a constant polynomial.
1781
1782        EXAMPLES:
1783            sage: P, x = PolynomialRing(ZZ).objgen()
1784            sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
1785            sage: g, u, v = F.xgcd(G)
1786            sage: g, u, v
1787            (27*x^2 + 54, 1, -x^2 - 3*x - 9)
1788            sage: u*F + v*G
1789            27*x^2 + 54
1790            sage: x.xgcd(P(0))
1791            (1, 0, x)
1792            sage: f = P(0)
1793            sage: f.xgcd(x)
1794            (x, 0, 1)
1795            sage: F = (x-3)^3; G = (x-15)^2
1796            sage: g, u, v = F.xgcd(G)
1797            sage: g, u, v
1798            (2985984, -432*x + 8208, 432*x^2 + 864*x + 14256)
1799            sage: u*F + v*G
1800            2985984
1801        """
1802        r, s, t = self.ntl_ZZX().xgcd(right.ntl_ZZX())
1803        K = self.base_ring()
1804        rr = K(str(r))   # optimize in future
1805        if rr == 0:
1806            QQ = sage.rings.rational_field.QQ
1807            f = self.base_extend(QQ)
1808            g, u, v = f.xgcd(right.base_extend(QQ))
1809            d = arith.lcm([g.denominator(), u.denominator(), v.denominator()])
1810            R = self.parent()
1811            return R(d*g), R(d*u), R(d*v)
1812        else:
1813            S = self.parent()
1814            return S(rr), S(s, construct=True), \
1815                   S(t, construct=True)
1816
1817
1818    def _mul_(self, right):
1819        """
1820        EXAMPLES:
1821            sage: x = PolynomialRing(ZZ).gen()
1822            sage: (x - 2)*(x^2 - 8*x + 16)
1823            x^3 - 10*x^2 + 32*x - 32
1824        """
1825        return self.parent()(self.__poly * right.__poly, construct=True)
1826
1827    def _sub_(self, right):
1828        return self.parent()(self.__poly - right.__poly, construct=True)
1829
1830    def __setitem__(self, n, value):
1831        if self._is_gen:
1832            raise ValueError, "the generator cannot be changed"
1833        n = int(n)
1834        if n < 0:
1835            raise IndexError, "n (=%s) must be >= 0"%n
1836        self.__poly[n] = int(value)
1837
1838    def complex_roots(self, flag=0):
1839        """
1840        Returns the complex roots of this polynomial.
1841        INPUT:
1842            flag -- optional, and can be
1843                    0: (default), uses Schonhage's method modified by Gourdon,
1844                    1: uses a modified Newton method.
1845        OUTPUT:
1846            list of complex roots of this polynomial, counted with multiplicities.
1847
1848        NOTE: Calls the pari function polroots.
1849
1850        EXAMPLE:
1851        We compute the roots of the characteristic polynomial of some Salem numbers:
1852            sage: R = PolynomialRing(ZZ); x = R.gen()
1853            sage: f = 1 - x^2 - x^3 - x^4 + x^6
1854            sage: f.complex_roots()[0]    # todo: known bug in PARI 2.2.10 !!
1855            0.71363917353690087
1856        """
1857        QQ = sage.rings.rational_field.RationalField()
1858        R = sage.rings.polynomial_ring.PolynomialRing(QQ)
1859        return R(self.list()).complex_roots()
1860
1861    def copy(self):
1862        f = Polynomial_integer_dense(self.parent())
1863        f.__poly = self.__poly.copy()
1864        return f
1865
1866    def degree(self):
1867        """
1868        Return the degree of this polynomial.  The zero polynomial
1869        has degree -1.
1870        """
1871        return max(self.__poly.degree(), -1)
1872
1873    def discriminant(self):
1874        """
1875        EXAMPLES:
1876            sage: x = PolynomialRing(ZZ).gen()
1877            sage: f = x^3 + 3*x - 17
1878            sage: f.discriminant()
1879            -7911
1880        """
1881        return ZZ(str(self.__poly.discriminant()))
1882
1883    def _pari_(self, variable='x'):
1884        return pari(str(self.__poly).replace(' ',',')).Pol(variable).polrecip()
1885
1886    def factor_mod(self, p):
1887        """
1888        Return the factorization of self modulo the prime p.
1889
1890        INPUT:
1891            p -- prime
1892
1893        OUTPUT:
1894            factorization of self reduced modulo p.
1895
1896        EXAMPLES:
1897            sage: x = Z['x'].0
1898            sage: f = -3*x*(x-2)*(x-9) + x
1899            sage: f.factor_mod(3)
1900            0
1901            sage: f = -3*x*(x-2)*(x-9)
1902            sage: f.factor_mod(3)
1903            Traceback (most recent call last):
1904            ...
1905            ValueError: factorization of 0 not defined
1906
1907            sage: f = 2*x*(x-2)*(x-9)
1908            sage: f.factor_mod(7)
1909            (2) * (x + 5)^2
1910        """
1911        p = integer.Integer(p)
1912        if not p.is_prime():
1913            raise ValueError, "p (=%s) must be prime"%p
1914        f = self._pari_()
1915        if f * pari('Mod(1,%s)'%p) == pari(0):
1916            raise ValueError, "factorization of 0 not defined"
1917        G = f.factormod(p)
1918        k = finite_field.FiniteField(p)
1919        R = sage.rings.polynomial_ring.PolynomialRing(k, name=self.parent().variable_name())
1921
1922
1924        """
1925        Return p-adic factorization of self to given precision.
1926
1927        INPUT:
1928            p -- prime
1929            prec -- integer; the precision
1930
1931        OUTPUT:
1932            factorization of self reduced modulo p.
1933        """
1934        p = integer.Integer(p)
1935        if not p.is_prime():
1936            raise ValueError, "p (=%s) must be prime"%p
1937        prec = integer.Integer(prec)
1938        if prec <= 0:
1939            raise ValueError, "prec (=%s) must be positive"%prec
1942        R = sage.rings.polynomial_ring.PolynomialRing(K, name=self.parent().variable_name())
1944
1945    def list(self):
1946        """
1947        EXAMPLES:
1948            sage: x = PolynomialRing(ZZ).gen()
1949            sage: f = x^3 + 3*x - 17
1950            sage: f.list()
1951            [-17, 3, 0, 1]
1952        """
1953        return [ZZ(str(self.__poly[i])) for i in xrange(self.degree()+1)]
1954
1955    def resultant(self, other):
1956        """
1957        Returns the resultant of self and other, which must lie in the same
1958        polynomial ring.
1959
1960        INPUT:
1961            other -- a polynomial
1962        OUTPUT:
1963            an element of the base ring of the polynomial ring
1964
1965        NOTES:
1966            Implemented using NTL's polresultant function.
1967
1968        EXAMPLES:
1969            sage: x = PolynomialRing(ZZ).gen()
1970            sage: f = x^3 + x + 1;  g = x^3 - x - 1
1971            sage: f.resultant(g)
1972            -8
1973        """
1974        if not isinstance(other, Polynomial) or self.parent() != other.parent():
1975            other = self.polynomial(other)
1976        return ZZ(str(self.__poly.resultant(other.__poly, 0)))
1977
1978    def ntl_set_directly(self, v):
1979        """
1980        Set the value of this polynomial directly from a vector or string.
1981
1982        Polynomials over the integers are stored internally using NTL's ZZX
1983        class.  Use this function to set the value of this polynomial using
1984        the NTL constructor, which is potentially quicker.   The input v
1985        is either a vector of ints or a string of the form '[ n1 n2 n3 ... ]'
1986        where the ni are integers and there are no commas between them.
1987        The optimal input format is the string format, since that's what NTL uses.
1988
1989        EXAMPLES:
1990            sage: R = PolynomialRing(ZZ)
1991            sage: R([1,2,3])
1992            3*x^2 + 2*x + 1
1993            sage: f = R(0)
1994            sage: f.ntl_set_directly([1,2,3])
1995            sage: f
1996            3*x^2 + 2*x + 1
1997            sage: f.ntl_set_directly('[1 2 3 4]')
1998            sage: f
1999            4*x^3 + 3*x^2 + 2*x + 1
2000        """
2001        if self._is_gen:
2002            raise TypeError, "Cannot change the value of the generator."
2003        self.__poly = ZZX(v)
2004        try:
2005            del self.__list
2006        except AttributeError:
2007            pass
2008
2009
2010
2011class Polynomial_dense_mod_n(Polynomial):
2012    """
2013    A dense polynomial over the integers modulo n, where n is composite.
2014
2015    EXAMPLES:
2016        sage: R, x = PolynomialRing(Integers(16)).objgen()
2017        sage: f = x^3 - x + 17
2019        True
2020    """
2021    def __init__(self, parent, x=None, check=True, is_gen=False, construct=False):
2022        Polynomial.__init__(self, parent, is_gen=is_gen)
2023
2024        if construct:
2025            if isinstance(x, ZZ_pX_class):
2026                self.__poly = x
2027                return
2028            parent._ntl_set_modulus()
2029            self.__poly = ZZ_pX(x)
2030            return
2031
2032        self.__poly = ZZ_pX([])
2033
2034        if x == None:
2035            return         # leave initialized to 0 polynomial.
2036
2037        if isinstance(x, Polynomial):
2038            if x.parent() == self.parent():
2039                parent._ntl_set_modulus()
2040                self.__poly = x.__poly.copy()
2041                return
2042            else:
2043                x = [ZZ._coerce_(a) for a in x.list()]
2044                check = False
2045
2046        if isinstance(x, dict):
2047            zero = ZZ(0)
2048            n = max(x.keys())
2049            v = [zero for _ in xrange(n+1)]
2050            for i, z in x.iteritems():
2051                v[i] = z
2052            x = v
2053
2054        elif isinstance(x, ZZX_class):
2055            self.__poly = x.copy()
2056            return
2057
2058        elif isinstance(x, gen) and x.type() == 't_POL':
2059            x = list(reversed(eval(str(x.lift().list()))))
2060            check = False
2061
2062        elif isinstance(x, fraction_field_element.FractionFieldElement) and \
2063                 isinstance(x.numerator(), Polynomial_dense_mod_n):
2064            if x.denominator() == 1:
2065                x = x.numerator().__poly
2066                check = False
2067
2068        elif not isinstance(x, list):
2069            x = [x]   # constant polynomials
2070
2071        if check:
2072            x = [ZZ(z) for z in x]
2073
2074        parent._ntl_set_modulus()
2075        self.__poly = ZZ_pX(x)
2076
2077    def __reduce__(self):
2078        return Polynomial_dense_mod_n, \
2079               (self.parent(), self.list(), False, self.is_gen())
2080
2081    def int_list(self):
2082        return eval(str(self.__poly).replace(' ',','))
2083
2084    def _pari_(self, variable='x'):
2085        return pari(str(list(reversed(self.int_list())))).Pol(variable) * \
2086               pari('Mod(1,%s)'%self.parent().base_ring().order())
2087
2088    def ntl_ZZ_pX(self):
2089        """
2090        Return underlying NTL representation of this polynomial.
2091        Additional bonus'' functionality is available through this
2092        function.
2093        """
2094        return self.__poly
2095
2096    def __getitem__(self, n):
2097        return self.base_ring()(self.__poly[n])
2098
2099    def __getslice__(self, i, j):
2100        R = self.base_ring()
2101        return [R(self.__poly[k]) for k in range(i,j)]
2102
2103    def _pow(self, n):
2104        n = int(n)
2105        if self.degree() <= 0:
2106            return self.parent()(self[0]**n)
2107        if n < 0:
2108            return (~self)**(-n)
2109        return self.parent()(self.__poly**n, construct=True)
2110
2112        return self.parent()(self.__poly + right.__poly, construct=True)
2113
2114    def quo_rem(self, right):
2115        """
2116        Returns a tuple (quotient, remainder) where
2117            self = quotient*other + remainder.
2118        """
2119        if not isinstance(right, Polynomial_dense_mod_n):
2120            right = self.parent()(right)
2121        elif self.parent() != right.parent():
2122            raise TypeError
2123        v = self.__poly.quo_rem(right.__poly)
2124        P = self.parent()
2125        return P(v[0], construct=True), P(v[1], construct=True)
2126
2127    def _mul_(self, right):
2128        """
2129        EXAMPLES:
2130            sage: x = PolynomialRing(Integers(100)).gen()
2131            sage: (x - 2)*(x^2 - 8*x + 16)
2132            x^3 + 90*x^2 + 32*x + 68
2133        """
2134        return self.parent()(self.__poly * right.__poly, construct=True)
2135
2136    def _sub_(self, right):
2137        return self.parent()(self.__poly - right.__poly, construct=True)
2138
2139    def __setitem__(self, n, value):
2140        if self._is_gen:
2141            raise ValueError, "the generator cannot be changed"
2142        n = int(n)
2143        if n < 0:
2144            raise IndexError, "n (=%s) must be >= 0"%n
2145        self.parent()._ntl_set_modulus()
2146        self.__poly[n] = int(value)
2147
2148    def copy(self):
2149        self.parent()._ntl_set_modulus()
2150        f = self.parent()()
2151        f.__poly = self.__poly.copy()
2152        return f
2153
2154    def degree(self):
2155        """
2156        Return the degree of this polynomial.  The zero polynomial
2157        has degree -1.
2158        """
2159        return max(self.__poly.degree(), -1)
2160
2161    def is_irreducible(self):
2162        return bool(self._pari_().polisirreducible())
2163
2164    def list(self):
2165        """
2166        EXAMPLES:
2167            sage: x = PolynomialRing(Integers(100)).gen()
2168            sage: f = x^3 + 3*x - 17
2169            sage: f.list()
2170            [83, 3, 0, 1]
2171        """
2172        R = self.base_ring()
2173        return [R(x) for x in self.int_list()]
2174
2175    def ntl_set_directly(self, v):
2176        r"""
2177        Set the value of this polynomial directly from a vector or string.
2178
2179        Polynomials over the integers modulo n are stored internally
2180        using NTL's ZZ_pX class.  Use this function to set the value
2181        of this polynomial using the NTL constructor, which is
2182        potentially \emph{very} fast.  The input v is either a vector
2183        of ints or a string of the form '[ n1 n2 n3 ... ]' where the
2184        ni are integers and there are no commas between them.  The
2185        optimal input format is the string format, since that's what
2186        NTL uses by default.
2187
2188        EXAMPLES:
2189            sage: R = PolynomialRing(Integers(100))
2190            sage: R([1,-2,3])
2191            3*x^2 + 98*x + 1
2192            sage: f = R(0)
2193            sage: f.ntl_set_directly([1,-2,3])
2194            sage: f
2195            3*x^2 + 98*x + 1
2196            sage: f.ntl_set_directly('[1 -2 3 4]')
2197            sage: f
2198            4*x^3 + 3*x^2 + 98*x + 1
2199        """
2200        if self._is_gen:
2201            raise TypeError, "Cannot change the value of the generator."
2202        self.parent()._ntl_set_modulus()
2203        self.__poly = ZZ_pX(v)
2204        try:
2205            del self.__list
2206        except AttributeError:
2207            pass
2208
2209class Polynomial_dense_mod_p(Polynomial_dense_mod_n, principal_ideal_domain_element.PrincipalIdealDomainElement):
2210    """
2211    A dense polynomial over the integers modulo p, where p is prime.
2212    """
2213    def __reduce__(self):
2214        return Polynomial_dense_mod_p, \
2215               (self.parent(), self.list(), False, self.is_gen())
2216
2217    def _gcd(self, right):
2218        """
2219        Return the GCD of self and other, as a monic polynomial.
2220        """
2221        if not isinstance(right, Polynomial_dense_mod_p):
2222            right = self.parent()(right)
2223        elif self.parent() != right.parent():
2224            raise TypeError
2225        g = self.ntl_ZZ_pX().gcd(right.ntl_ZZ_pX())
2226        return self.parent()(g, construct=True)
2227
2228    def _xgcd(self, right):
2229        """
2230        Return $g, u, v$ such that \code{g = u*self + v*right}.
2231        """
2232        r, s, t = self.ntl_ZZ_pX().xgcd(right.ntl_ZZ_pX())
2233        return self.parent()(r, construct=True), self.parent()(s, construct=True), \
2234               self.parent()(t, construct=True)
2235
2236    def resultant(self, other):
2237        """
2238        Returns the resultant of self and other, which must lie in the same
2239        polynomial ring.
2240
2241        INPUT:
2242            other -- a polynomial
2243        OUTPUT:
2244            an element of the base ring of the polynomial ring
2245
2246        EXAMPLES:
2247            sage: x = PolynomialRing(GF(19)).gen()
2248            sage: f = x^3 + x + 1;  g = x^3 - x - 1
2249            sage: f.resultant(g)
2250            11
2251        """
2252        if not isinstance(other, Polynomial) or self.parent() != other.parent():
2253            other = self.polynomial(other)
2254        self.parent()._ntl_set_modulus()
2255        return self.base_ring()(str(self.ntl_ZZ_pX().resultant(other.ntl_ZZ_pX())))
2256
2257    def discriminant(self):
2258        """
2259        EXAMPLES:
2260            sage: x = PolynomialRing(GF(19)).gen()
2261            sage: f = x^3 + 3*x - 17
2262            sage: f.discriminant()
2263            12
2264        """
2265        self.parent()._ntl_set_modulus()
2266        return self.base_ring()(str(self.ntl_ZZ_pX().discriminant()))
2267
2268    # PARI is way better than NTL for poly factor, and is called by default in the base class.
2269    #def factor(self, verbose=False):
2270    #    M = self.monic()
2271    #    self.parent()._ntl_set_modulus()
2272    #    F = [(self.parent()(f, construct=True), n) for f, n in M.ntl_ZZ_pX().factor(verbose)]
2273    #    return factorization.Factorization(F)
2274
2275
Note: See TracBrowser for help on using the repository browser.