source: sage/rings/number_field/number_field_element.pyx @ 6429:a8ff34d156c9

Revision 6429:a8ff34d156c9, 54.2 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Fix some serious merge conflicts with ntl patch.
Line 
1"""
2Number Field Elements
3
4AUTHORS:
5    -- William Stein version before it got cython'd
6    -- Joel B. Mohler (2007-03-09): First reimplementation into cython
7    -- William Stein (2007-09-04): add doctests
8    -- Robert Bradshaw (2007-09-15): specialized classes for relative and absolute elements
9"""
10
11# TODO -- relative extensions need to be completely rewritten, so one
12# can get easy access to representation of elements in their relative
13# form.  Functions like matrix below can't be done until relative
14# extensions are re-written this way.  Also there needs to be class
15# hierarchy for number field elements, integers, etc.  This is a
16# nontrivial project, and it needs somebody to attack it.  I'm amazed
17# how long this has gone unattacked.
18
19# Relative elements need to be a derived class or something.  This is
20# terrible as it is now.
21
22#*****************************************************************************
23#       Copyright (C) 2004, 2007 William Stein <wstein@gmail.com>
24#
25#  Distributed under the terms of the GNU General Public License (GPL)
26#
27#    This code is distributed in the hope that it will be useful,
28#    but WITHOUT ANY WARRANTY; without even the implied warranty of
29#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
30#    General Public License for more details.
31#
32#  The full text of the GPL is available at:
33#
34#                  http://www.gnu.org/licenses/
35#*****************************************************************************
36
37import operator
38
39include '../../ext/interrupt.pxi'
40include '../../ext/python_int.pxi'
41include "../../ext/stdsage.pxi"
42cdef extern from *:
43    # TODO: move to stdsage.pxi
44    object PY_NEW_SAME_TYPE(object o)
45
46import sage.rings.field_element
47import sage.rings.infinity
48import sage.rings.polynomial.polynomial_element
49import sage.rings.polynomial.polynomial_ring
50import sage.rings.rational_field
51import sage.rings.rational
52import sage.rings.integer_ring
53import sage.rings.integer
54import sage.rings.arith
55
56import sage.rings.number_field.number_field
57
58from sage.libs.ntl.ntl_ZZ cimport ntl_ZZ
59from sage.libs.ntl.ntl_ZZX cimport ntl_ZZX
60from sage.rings.integer_ring cimport IntegerRing_class
61
62from sage.libs.all import pari_gen
63from sage.libs.pari.gen import PariError
64
65QQ = sage.rings.rational_field.QQ
66ZZ = sage.rings.integer_ring.ZZ
67Integer_sage = sage.rings.integer.Integer
68
69
70def is_NumberFieldElement(x):
71    """
72    Return True if x is of type NumberFieldElement, i.e., an
73    element of a number field.
74
75    EXAMPLES:
76        sage: is_NumberFieldElement(2)
77        False
78        sage: k.<a> = NumberField(x^7 + 17*x + 1)
79        sage: is_NumberFieldElement(a+1)
80        True
81    """
82    return PY_TYPE_CHECK(x, NumberFieldElement)
83
84def __create__NumberFieldElement_version0(parent, poly):
85    """
86    Used in unpickling elements of number fields.
87
88    EXAMPLES:
89    Since this is just used in unpickling, we unpickle.
90   
91        sage: k.<a> = NumberField(x^3 - 2)
92        sage: loads(dumps(a+1)) == a + 1
93        True       
94    """
95    return NumberFieldElement(parent, poly)
96
97def __create__NumberFieldElement_version1(parent, cls, poly):
98    """
99    Used in unpickling elements of number fields.
100
101    EXAMPLES:
102    Since this is just used in unpickling, we unpickle.
103   
104        sage: k.<a> = NumberField(x^3 - 2)
105        sage: loads(dumps(a+1)) == a + 1
106        True       
107    """
108    return cls(parent, poly)
109
110cdef class NumberFieldElement(FieldElement):
111    """
112    An element of a number field.
113
114    EXAMPLES:
115        sage: k.<a> = NumberField(x^3 + x + 1)
116        sage: a^3
117        -a - 1       
118    """
119    cdef NumberFieldElement _new(self):
120        """
121        Quickly creates a new initialized NumberFieldElement with the
122        same parent as self.
123        """
124        cdef NumberFieldElement x
125        x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
126        x._parent = self._parent
127        return x
128
129    def __init__(self, parent, f):
130        """
131        INPUT:
132            parent -- a number field
133            f -- defines an element of a number field.
134
135        EXAMPLES:
136        The following examples illustrate creation of elements of
137        number fields, and some basic arithmetic.
138
139        First we define a polynomial over Q.
140            sage: R.<x> = PolynomialRing(QQ)
141            sage: f = x^2 + 1
142
143        Next we use f to define the number field.
144            sage: K.<a> = NumberField(f); K
145            Number Field in a with defining polynomial x^2 + 1
146            sage: a = K.gen()
147            sage: a^2
148            -1
149            sage: (a+1)^2
150            2*a
151            sage: a^2
152            -1
153            sage: z = K(5); 1/z
154            1/5
155
156        We create a cube root of 2.
157            sage: K.<b> = NumberField(x^3 - 2)
158            sage: b = K.gen()
159            sage: b^3
160            2
161            sage: (b^2 + b + 1)^3
162            12*b^2 + 15*b + 19
163
164        This example illustrates save and load:
165            sage: K.<a> = NumberField(x^17 - 2)
166            sage: s = a^15 - 19*a + 3
167            sage: loads(s.dumps()) == s
168            True
169        """
170        sage.rings.field_element.FieldElement.__init__(self, parent)
171
172        cdef ZZ_c coeff
173        if isinstance(f, (int, long, Integer_sage)):
174            # set it up and exit immediately
175            # fast pathway
176            (<Integer>ZZ(f))._to_ZZ(&coeff)
177            ZZX_SetCoeff( self.__numerator, 0, coeff )
178            conv_ZZ_int( self.__denominator, 1 )
179            return
180           
181        elif isinstance(f, NumberFieldElement):
182            if PY_TYPE(self) is PY_TYPE(f):
183                self.__numerator = (<NumberFieldElement>f).__numerator
184                self.__denominator = (<NumberFieldElement>f).__denominator
185                return
186            else:
187                f = f.polynomial()
188
189        ppr = parent.polynomial_ring()
190        if isinstance(parent, sage.rings.number_field.number_field.NumberField_relative):
191            ppr = parent.base_field().polynomial_ring()
192
193        if isinstance(f, pari_gen):
194            f = f.lift()
195            f = ppr(f)
196        if not isinstance(f, sage.rings.polynomial.polynomial_element.Polynomial):
197            f = ppr(f)
198        if f.degree() >= parent.absolute_degree():
199            if f.variable_name() != 'x':
200                f = f.change_variable_name('x')
201            if isinstance(parent, sage.rings.number_field.number_field.NumberField_relative):
202                f %= parent.absolute_polynomial()
203            else:
204                f %= parent.polynomial()
205
206        # Set Denominator
207        den = f.denominator()
208        (<Integer>ZZ(den))._to_ZZ(&self.__denominator)
209
210        cdef long i
211        num = f * den
212        for i from 0 <= i <= num.degree():
213            (<Integer>ZZ(num[i]))._to_ZZ(&coeff)
214            ZZX_SetCoeff( self.__numerator, i, coeff )
215
216    def __new__(self, parent = None, f = None):
217        ZZX_construct(&self.__numerator)
218        ZZ_construct(&self.__denominator)
219
220    def __dealloc__(self):
221        ZZX_destruct(&self.__numerator)
222        ZZ_destruct(&self.__denominator)
223
224    def _lift_cyclotomic_element(self, new_parent):
225        """
226        Creates an element of the passed field from this field.  This
227        is specific to creating elements in a cyclotomic field from
228        elements in another cyclotomic field.  This function aims to
229        make this common coercion extremely fast!
230
231        EXAMPLES:
232            sage: C.<zeta5>=CyclotomicField(5)
233            sage: CyclotomicField(10)(zeta5+1)  # The function _lift_cyclotomic_element does the heavy lifting in the background
234            zeta10^2 + 1
235            sage: (zeta5+1)._lift_cyclotomic_element(CyclotomicField(10))  # There is rarely a purpose to call this function directly
236            zeta10^2 + 1
237
238        AUTHOR:
239            Joel B. Mohler
240        """
241        # Right now, I'm a little confused why quadratic extension fields have a zeta_order function
242        # I would rather they not have this function since I don't want to do this isinstance check here.
243        if not isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic) or not isinstance(new_parent, sage.rings.number_field.number_field.NumberField_cyclotomic):
244            raise TypeError, "The field and the new parent field must both be cyclotomic fields."
245
246        try:
247            small_order = self.parent().zeta_order()
248            large_order = new_parent.zeta_order()
249        except AttributeError:
250            raise TypeError, "The field and the new parent field must both be cyclotomic fields."
251
252        try:
253            _rel = ZZ(large_order / small_order)
254        except TypeError:
255            raise TypeError, "The zeta_order of the new field must be a multiple of the zeta_order of the original."
256
257        cdef NumberFieldElement x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
258        x._parent = <ParentWithBase>new_parent
259        x.__denominator = self.__denominator
260        cdef ZZX_c result
261        cdef ZZ_c tmp
262        cdef int i
263        cdef int rel = _rel
264        cdef ntl_ZZX _num
265        cdef ntl_ZZ _den
266        _num, _den = new_parent.polynomial_ntl()
267        for i from 0 <= i <= ZZX_deg(self.__numerator):
268            tmp = ZZX_coeff(self.__numerator, i)
269            ZZX_SetCoeff(result, i*rel, tmp)
270        rem_ZZX(x.__numerator, result, _num.x)
271        return x
272
273    def __reduce__(self):
274        """
275        Used in pickling number field elements.
276
277        EXAMPLES:
278            sage: k.<a> = NumberField(x^3 - 17*x^2 + 1)
279            sage: t = a.__reduce__(); t
280            (<built-in function __create__NumberFieldElement_version1>, (Number Field in a with defining polynomial x^3 - 17*x^2 + 1, <type 'sage.rings.number_field.number_field_element.NumberFieldElement_absolute'>, x))
281            sage: t[0](*t[1]) == a
282            True       
283        """
284        return __create__NumberFieldElement_version1, \
285               (self.parent(), type(self), self.polynomial())
286
287    def __repr__(self):
288        """
289        String representation of this number field element,
290        which is just a polynomial in the generator.
291
292        EXAMPLES:
293            sage: k.<a> = NumberField(x^2 + 2)
294            sage: b = (2/3)*a + 3/5
295            sage: b.__repr__()
296            '2/3*a + 3/5'       
297        """
298        x = self.polynomial()
299        return str(x).replace(x.parent().variable_name(),self.parent().variable_name())
300
301    def _im_gens_(self, codomain, im_gens):
302        """
303        This is used in computing homomorphisms between number fields.
304
305        EXAMPLES:
306            sage: k.<a> = NumberField(x^2 - 2)
307            sage: m.<b> = NumberField(x^4 - 2)
308            sage: phi = k.hom([b^2])
309            sage: phi(a+1)
310            b^2 + 1
311            sage: (a+1)._im_gens_(m, [b^2])
312            b^2 + 1       
313        """
314        # NOTE -- if you ever want to change this so relative number fields are
315        # in terms of a root of a poly.
316        # The issue is that elements of a relative number field are represented in terms
317        # of a generator for the absolute field.  However the morphism gives the image
318        # of gen, which need not be a generator for the absolute field.  The morphism
319        # has to be *over* the relative element.
320        return codomain(self.polynomial()(im_gens[0]))
321
322    def _latex_(self):
323        """
324        Returns the latex representation for this element.
325
326        EXAMPLES:
327            sage: C,zeta12=CyclotomicField(12).objgen()
328            sage: latex(zeta12^4-zeta12)
329            \zeta_{12}^{2} - \zeta_{12} - 1
330        """
331        return self.polynomial()._latex_(name=self.parent().latex_variable_name())
332
333    def _pari_(self, var='x'):
334        raise NotImplementedError, "NumberFieldElement sub-classes must override _pari_"
335
336    def _pari_init_(self, var='x'):
337        """
338        Return GP/PARI string representation of self. This is used for
339        converting this number field element to GP/PARI.  The returned
340        string defines a pari Mod in the variable is var, which is by
341        default 'x' -- not the name of the generator of the number
342        field.
343
344        INPUT:
345            var -- (default: 'x') the variable of the pari Mod.
346
347        EXAMPLES:
348            sage: K.<a> = NumberField(x^5 - x - 1)
349            sage: ((1 + 1/3*a)^4)._pari_init_()
350            'Mod(1/81*x^4 + 4/27*x^3 + 2/3*x^2 + 4/3*x + 1, x^5 - x - 1)'
351            sage: ((1 + 1/3*a)^4)._pari_init_('a')
352            'Mod(1/81*a^4 + 4/27*a^3 + 2/3*a^2 + 4/3*a + 1, a^5 - a - 1)'
353
354        Note that _pari_init_ can fail because of reserved words in PARI,
355        and since it actually works by obtaining the PARI representation
356        of something.
357            sage: K.<theta> = NumberField(x^5 - x - 1)
358            sage: b = (1/2 - 2/3*theta)^3; b
359            -8/27*theta^3 + 2/3*theta^2 - 1/2*theta + 1/8
360            sage: b._pari_init_('theta')
361            Traceback (most recent call last):
362            ...
363            PariError: unexpected character (2)
364
365        Fortunately pari_init returns everything in terms of x by default.
366            sage: pari(b)
367            Mod(-8/27*x^3 + 2/3*x^2 - 1/2*x + 1/8, x^5 - x - 1)
368        """
369        return repr(self._pari_(var=var))
370##         if var == None:
371##             var = self.parent().variable_name()
372##         if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_relative):
373##             f = self.polynomial()._pari_()
374##             g = str(self.parent().pari_relative_polynomial())
375##             base = self.parent().base_ring()
376##             gsub = base.gen()._pari_()
377##             gsub = str(gsub).replace(base.variable_name(), "y")
378##             g = g.replace("y", gsub)
379##         else:
380##             f = str(self.polynomial()).replace("x",var)
381##             g = str(self.parent().polynomial()).replace("x",var)
382##         return 'Mod(%s, %s)'%(f,g)
383
384    def __getitem__(self, n):
385        """
386        Return the n-th coefficient of this number field element, written
387        as a polynomial in the generator.
388
389        Note that $n$ must be between 0 and $d-1$, where $d$ is the
390        degree of the number field.
391
392        EXAMPLES:
393            sage: m.<b> = NumberField(x^4 - 1789)
394            sage: c = (2/3-4/5*b)^3; c
395            -64/125*b^3 + 32/25*b^2 - 16/15*b + 8/27
396            sage: c[0]
397            8/27
398            sage: c[2]
399            32/25
400            sage: c[3]
401            -64/125
402
403        We illustrate bounds checking:
404            sage: c[-1]
405            Traceback (most recent call last):
406            ...
407            IndexError: index must be between 0 and degree minus 1.
408            sage: c[4]
409            Traceback (most recent call last):
410            ...
411            IndexError: index must be between 0 and degree minus 1.
412
413        The list method implicitly calls __getitem__:
414            sage: list(c)
415            [8/27, -16/15, 32/25, -64/125]
416            sage: m(list(c)) == c
417            True           
418        """
419        if n < 0 or n >= self.parent().degree():     # make this faster.
420            raise IndexError, "index must be between 0 and degree minus 1."
421        return self.polynomial()[n]
422
423    cdef int _cmp_c_impl(left, sage.structure.element.Element right) except -2:
424        cdef NumberFieldElement _right = right
425        return not (ZZX_equal(&left.__numerator, &_right.__numerator) and ZZ_equal(&left.__denominator, &_right.__denominator))
426
427    def __abs__(self):
428        r"""
429        Return the numerical absolute value of this number field
430        element with respect to the first archimedean embedding, to 53
431        bits of precision.
432
433        This is the \code{abs( )} Python function.  If you want a different
434        embedding or precision, use \code{self.abs(...)}.
435
436        EXAMPLES:
437            sage: k.<a> = NumberField(x^3 - 2)
438            sage: abs(a)
439            1.25992104989487
440            sage: abs(a)^3
441            2.00000000000000
442            sage: a.abs(prec=128)
443            1.2599210498948731647672106072782283506       
444        """
445        return self.abs(prec=53, i=0)
446
447    def abs(self, prec=53, i=0):
448        """
449        Return the absolute value of this element with respect to the
450        ith complex embedding of parent, to the given precision.
451
452        INPUT:
453            prec -- (default: 53) integer bits of precision
454            i -- (default: ) integer, which embedding to use
455
456        EXAMPLES:
457            sage: z = CyclotomicField(7).gen()
458            sage: abs(z)
459            1.00000000000000
460            sage: abs(z^2 + 17*z - 3)
461            16.0604426799931
462            sage: K.<a> = NumberField(x^3+17)
463            sage: abs(a)
464            2.57128159065824
465            sage: a.abs(prec=100)
466            2.5712815906582353554531872087
467            sage: a.abs(prec=100,i=1)
468            2.5712815906582353554531872087
469            sage: a.abs(100, 2)
470            2.5712815906582353554531872087
471
472        Here's one where the absolute value depends on the embedding.
473            sage: K.<b> = NumberField(x^2-2)
474            sage: a = 1 + b
475            sage: a.abs(i=0)
476            2.41421356237309
477            sage: a.abs(i=1)
478            0.414213562373095
479        """
480        P = self.parent().complex_embeddings(prec)[i]
481        return abs(P(self))
482
483    def coordinates_in_terms_of_powers(self):
484        r"""
485        Let $\alpha$ be self.  Return a Python function that takes any
486        element of the parent of self in $\QQ(\alpha)$ and writes it in
487        terms of the powers of $\alpha$: $1, \alpha, \alpha^2, ...$.
488
489        (NOT CACHED).
490
491        EXAMPLES:
492        This function allows us to write elements of a number field in
493        terms of a different generator without having to construct a
494        whole separate number field.
495
496            sage: y = polygen(QQ,'y'); K.<beta> = NumberField(y^3 - 2); K
497            Number Field in beta with defining polynomial y^3 - 2
498            sage: alpha = beta^2 + beta + 1
499            sage: c = alpha.coordinates_in_terms_of_powers(); c
500            Coordinate function that writes elements in terms of the powers of beta^2 + beta + 1
501            sage: c(beta)
502            [-2, -3, 1]
503            sage: c(alpha)
504            [0, 1, 0]
505            sage: c((1+beta)^5)
506            [3, 3, 3]
507            sage: c((1+beta)^10)
508            [54, 162, 189]
509       
510        This function works even if self only generates a subfield
511        of this number field.
512            sage: k.<a> = NumberField(x^6 - 5)
513            sage: alpha = a^3
514            sage: c = alpha.coordinates_in_terms_of_powers()
515            sage: c((2/3)*a^3 - 5/3)
516            [-5/3, 2/3]
517            sage: c
518            Coordinate function that writes elements in terms of the powers of a^3
519            sage: c(a)
520            Traceback (most recent call last):
521            ...
522            ArithmeticError: vector is not in free module
523        """
524        K = self.parent()
525        V, from_V, to_V = K.absolute_vector_space()
526        h = K(1)
527        B = [to_V(h)]
528        f = self.minpoly()
529        for i in range(f.degree()-1):
530            h *= self
531            B.append(to_V(h))
532        W = V.span_of_basis(B)
533        return CoordinateFunction(self, W, to_V)
534
535    def complex_embeddings(self, prec=53):
536        """
537        Return the images of this element in the floating point
538        complex numbers, to the given bits of precision.
539
540        INPUT:
541            prec -- integer (default: 53) bits of precision
542
543        EXAMPLES:
544            sage: k.<a> = NumberField(x^3 - 2)
545            sage: a.complex_embeddings()
546            [1.25992104989487, -0.629960524947437 + 1.09112363597172*I, -0.629960524947437 - 1.09112363597172*I]
547            sage: a.complex_embeddings(10)
548            [1.3, -0.63 + 1.1*I, -0.63 - 1.1*I]
549            sage: a.complex_embeddings(100)
550            [1.2599210498948731647672106073, -0.62996052494743658238360530364 + 1.0911236359717214035600726142*I, -0.62996052494743658238360530364 - 1.0911236359717214035600726142*I]
551        """
552        phi = self.parent().complex_embeddings(prec)
553        return [f(self) for f in phi]
554
555    def complex_embedding(self, prec=53, i=0):
556        """
557        Return the i-th embedding of self in the complex numbers, to
558        the given precision.
559
560        EXAMPLES:
561            sage: k.<a> = NumberField(x^3 - 2)
562            sage: a.complex_embedding()
563            1.25992104989487
564            sage: a.complex_embedding(10)
565            1.3
566            sage: a.complex_embedding(100)
567            1.2599210498948731647672106073
568            sage: a.complex_embedding(20, 1)
569            -0.62996 + 1.0911*I
570            sage: a.complex_embedding(20, 2)
571            -0.62996 - 1.0911*I
572        """
573        return self.parent().complex_embeddings(prec)[i](self)
574
575    def is_square(self, root=False):
576        """
577        Return True if self is a square in its parent number field and
578        otherwise return False.
579
580        INPUT:
581            root -- if True, also return a square root (or None if self
582                    is not a perfect square)
583
584        EXAMPLES:
585            sage: m.<b> = NumberField(x^4 - 1789)
586            sage: b.is_square()
587            False
588            sage: c = (2/3*b + 5)^2; c
589            4/9*b^2 + 20/3*b + 25
590            sage: c.is_square()
591            True
592            sage: c.is_square(True)
593            (True, 2/3*b + 5)
594
595        We also test the functional notation.
596            sage: is_square(c, True)
597            (True, 2/3*b + 5)
598            sage: is_square(c)
599            True
600            sage: is_square(c+1)
601            False
602        """
603        v = self.sqrt(all=True)
604        t = len(v) > 0
605        if root:
606            if t:
607                return t, v[0]
608            else:
609                return False, None
610        else:
611            return t
612       
613    def sqrt(self, all=False):
614        """
615        Returns the square root of this number in the given number field.
616       
617        EXAMPLES:
618            sage: K.<a> = NumberField(x^2 - 3)
619            sage: K(3).sqrt()
620            a
621            sage: K(3).sqrt(all=True)
622            [a, -a]
623            sage: K(a^10).sqrt()
624            9*a
625            sage: K(49).sqrt()
626            7
627            sage: K(1+a).sqrt()
628            Traceback (most recent call last):
629            ...
630            ValueError: a + 1 not a square in Number Field in a with defining polynomial x^2 - 3
631            sage: K(0).sqrt()
632            0
633            sage: K((7+a)^2).sqrt(all=True)
634            [a + 7, -a - 7]
635           
636            sage: K.<a> = CyclotomicField(7)
637            sage: a.sqrt() 
638            a^4
639           
640            sage: K.<a> = NumberField(x^5 - x + 1)
641            sage: (a^4 + a^2 - 3*a + 2).sqrt()
642            a^3 - a^2
643
644        ALGORITHM:
645            Use Pari to factor $x^2$ - \code{self} in K.
646           
647        """
648        # For now, use pari's factoring abilities
649        R = sage.rings.polynomial.polynomial_ring.PolynomialRing(self._parent, 't')
650        f = R([-self, 0, 1])
651        roots = f.roots()
652        if all:
653            return [r[0] for r in roots]
654        elif len(roots) > 0:
655            return roots[0][0]
656        else:
657            raise ValueError, "%s not a square in %s"%(self, self._parent)
658
659    cdef void _reduce_c_(self):
660        """
661        Pull out common factors from the numerator and denominator!
662        """
663        cdef ZZ_c gcd
664        cdef ZZ_c t1
665        cdef ZZX_c t2
666        content(t1, self.__numerator)
667        GCD_ZZ(gcd, t1, self.__denominator)
668        if sign(gcd) != sign(self.__denominator):
669            ZZ_negate(t1, gcd)
670            gcd = t1
671        div_ZZX_ZZ(t2, self.__numerator, gcd)
672        div_ZZ_ZZ(t1, self.__denominator, gcd)
673        self.__numerator = t2
674        self.__denominator = t1
675
676    cdef ModuleElement _add_c_impl(self, ModuleElement right):
677        cdef NumberFieldElement x
678        cdef NumberFieldElement _right = right
679        x = self._new()
680        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
681        cdef ZZX_c t1, t2
682        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
683        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
684        add_ZZX(x.__numerator, t1, t2)
685        x._reduce_c_()
686        return x
687
688    cdef ModuleElement _sub_c_impl(self, ModuleElement right):
689        cdef NumberFieldElement x
690        cdef NumberFieldElement _right = right
691        x = self._new()
692        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
693        cdef ZZX_c t1, t2
694        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
695        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
696        sub_ZZX(x.__numerator, t1, t2)
697        x._reduce_c_()
698        return x
699
700    cdef RingElement _mul_c_impl(self, RingElement right):
701        """
702        Returns the product of self and other as elements of a number field.
703
704        EXAMPLES:
705            sage: C.<zeta12>=CyclotomicField(12)
706            sage: zeta12*zeta12^11
707            1
708            sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
709            sage: a^3
710            -2/3*a - 1
711            sage: a^3+a
712            1/3*a - 1
713        """
714        cdef NumberFieldElement x
715        cdef NumberFieldElement _right = right
716        cdef ZZX_c temp
717        cdef ZZ_c temp1
718        cdef ZZ_c parent_den
719        cdef ZZX_c parent_num
720        self._parent_poly_c_( &parent_num, &parent_den )
721        x = self._new()
722        _sig_on
723        # MulMod doesn't handle non-monic polynomials.
724        # Therefore, we handle the non-monic case entirely separately.
725        if ZZX_is_monic( &parent_num ):
726            mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
727            MulMod_ZZX(x.__numerator, self.__numerator, _right.__numerator, parent_num)
728        else:
729            mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
730            mul_ZZX(x.__numerator, self.__numerator, _right.__numerator)
731            if ZZX_degree(&x.__numerator) >= ZZX_degree(&parent_num):
732                mul_ZZX_ZZ( x.__numerator, x.__numerator, parent_den )
733                mul_ZZX_ZZ( temp, parent_num, x.__denominator )
734                power_ZZ(temp1,LeadCoeff_ZZX(temp),ZZX_degree(&x.__numerator)-ZZX_degree(&parent_num)+1)
735                PseudoRem_ZZX(x.__numerator, x.__numerator, temp)
736                mul_ZZ(x.__denominator, x.__denominator, parent_den)
737                mul_ZZ(x.__denominator, x.__denominator, temp1)
738        _sig_off
739        x._reduce_c_()
740        return x
741
742        #NOTES: In LiDIA, they build a multiplication table for the
743        #number field, so it's not necessary to reduce modulo the
744        #defining polynomial every time:
745        #     src/number_fields/algebraic_num/order.cc: compute_table
746        # but asymptotically fast poly multiplication means it's
747        # actually faster to *not* build a table!?!
748
749    cdef RingElement _div_c_impl(self, RingElement right):
750        """
751        Returns the quotient of self and other as elements of a number field.
752
753        EXAMPLES:
754            sage: C.<I>=CyclotomicField(4)
755            sage: 1/I
756            -I
757            sage: I/0
758            Traceback (most recent call last):
759            ...
760            ZeroDivisionError: Number field element division by zero
761           
762            sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
763            sage: a/a
764            1
765            sage: 1/a
766            -a^2 - 2/3
767            sage: a/0
768            Traceback (most recent call last):
769            ...
770            ZeroDivisionError: Number field element division by zero
771        """
772        cdef NumberFieldElement x
773        cdef NumberFieldElement _right = right
774        cdef ZZX_c inv_num
775        cdef ZZ_c inv_den
776        cdef ZZ_c parent_den
777        cdef ZZX_c parent_num
778        cdef ZZX_c temp
779        cdef ZZ_c temp1
780        if not _right:
781            raise ZeroDivisionError, "Number field element division by zero"
782        self._parent_poly_c_( &parent_num, &parent_den )
783        x = self._new()
784        _sig_on
785        _right._invert_c_(&inv_num, &inv_den)
786        if ZZX_is_monic( &parent_num ):
787            mul_ZZ(x.__denominator, self.__denominator, inv_den)
788            MulMod_ZZX(x.__numerator, self.__numerator, inv_num, parent_num)
789        else:
790            mul_ZZ(x.__denominator, self.__denominator, inv_den)
791            mul_ZZX(x.__numerator, self.__numerator, inv_num)
792            if ZZX_degree(&x.__numerator) >= ZZX_degree(&parent_num):
793                mul_ZZX_ZZ( x.__numerator, x.__numerator, parent_den )
794                mul_ZZX_ZZ( temp, parent_num, x.__denominator )
795                power_ZZ(temp1,LeadCoeff_ZZX(temp),ZZX_degree(&x.__numerator)-ZZX_degree(&parent_num)+1)
796                PseudoRem_ZZX(x.__numerator, x.__numerator, temp)
797                mul_ZZ(x.__denominator, x.__denominator, parent_den)
798                mul_ZZ(x.__denominator, x.__denominator, temp1)
799        x._reduce_c_()
800        _sig_off
801        return x
802
803    def __floordiv__(self, other):
804        """
805        Return the quotient of self and other.  Since these are field
806        elements the floor division is exactly the same as usual
807        division.
808
809        EXAMPLES:
810            sage: m.<b> = NumberField(x^4 + x^2 + 2/3)
811            sage: c = (1+b) // (1-b); c
812            3/4*b^3 + 3/4*b^2 + 3/2*b + 1/2
813            sage: (1+b) / (1-b) == c
814            True
815            sage: c * (1-b)
816            b + 1       
817        """
818        return self / other
819
820    def __nonzero__(self):
821        """
822        Return True if this number field element is nonzero.
823
824        EXAMPLES:
825            sage: m.<b> = CyclotomicField(17)
826            sage: m(0).__nonzero__()
827            False
828            sage: b.__nonzero__()
829            True
830
831        Nonzero is used by the bool command:
832            sage: bool(b + 1)
833            True
834            sage: bool(m(0))
835            False
836        """
837        return not IsZero_ZZX(self.__numerator)
838
839    cdef ModuleElement _neg_c_impl(self):
840        cdef NumberFieldElement x
841        x = self._new()
842        mul_ZZX_long(x.__numerator, self.__numerator, -1)
843        x.__denominator = self.__denominator
844        return x
845
846    def __int__(self):
847        """
848        Attempt to convert this number field element to a Python integer,
849        if possible.
850       
851        EXAMPLES:
852            sage: C.<I>=CyclotomicField(4)
853            sage: int(1/I)
854            Traceback (most recent call last):
855            ...
856            TypeError: cannot coerce nonconstant polynomial to int
857            sage: int(I*I)
858            -1
859
860            sage: K.<a> = NumberField(x^10 - x - 1)
861            sage: int(a)
862            Traceback (most recent call last):
863            ...
864            TypeError: cannot coerce nonconstant polynomial to int
865            sage: int(K(9390283))
866            9390283
867
868        The semantics are like in Python, so the value does not have
869        to preserved.
870            sage: int(K(393/29))
871            13           
872        """
873        return int(self.polynomial())
874
875    def __long__(self):
876        """
877        Attempt to convert this number field element to a Python long,
878        if possible.
879       
880        EXAMPLES:
881            sage: K.<a> = NumberField(x^10 - x - 1)
882            sage: long(a)
883            Traceback (most recent call last):
884            ...
885            TypeError: cannot coerce nonconstant polynomial to long
886            sage: long(K(1234))
887            1234L
888
889        The value does not have to be preserved, in the case of fractions.
890            sage: long(K(393/29))
891            13L       
892        """
893        return long(self.polynomial())
894
895    cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
896        raise NotImplementedError, "NumberFieldElement subclasses must override _parent_poly_c_()"
897        cdef long i
898        cdef ZZ_c coeff
899        cdef ntl_ZZX _num
900        cdef ntl_ZZ _den
901        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_relative):
902            # ugly temp code
903            f = self.parent().absolute_polynomial()
904
905            __den = f.denominator()
906            (<Integer>ZZ(__den))._to_ZZ(den)
907
908            __num = f * __den
909            for i from 0 <= i <= __num.degree():
910                (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
911                ZZX_SetCoeff( num[0], i, coeff )
912        else:
913            _num, _den = self.parent().polynomial_ntl()
914            num[0] = _num.x
915            den[0] = _den.x
916
917    cdef void _invert_c_(self, ZZX_c *num, ZZ_c *den):
918        """
919        Computes the numerator and denominator of the multiplicative inverse of this element.
920
921        Suppose that this element is x/d and the parent mod'ding polynomial is M/D.  The NTL function
922        XGCD( r, s, t, a, b ) computes r,s,t such that $r=s*a+t*b$.  We compute
923        XGCD( r, s, t, x*D, M*d ) and set
924        num=s*D*d
925        den=r
926
927        EXAMPLES:
928            I'd love to, but since we are dealing with c-types, I can't at this level.
929            Check __invert__ for doc-tests that rely on this functionality.
930        """
931        cdef ZZ_c parent_den
932        cdef ZZX_c parent_num
933        self._parent_poly_c_( &parent_num, &parent_den )
934
935        cdef ZZX_c t # unneeded except to be there
936        cdef ZZX_c a, b
937        mul_ZZX_ZZ( a, self.__numerator, parent_den )
938        mul_ZZX_ZZ( b, parent_num, self.__denominator )
939        XGCD_ZZX( den[0], num[0],  t, a, b, 1 )
940        mul_ZZX_ZZ( num[0], num[0], parent_den )
941        mul_ZZX_ZZ( num[0], num[0], self.__denominator )
942
943    def __invert__(self):
944        """
945        Returns the multiplicative inverse of self in the number field.
946
947        EXAMPLES:
948            sage: C.<I>=CyclotomicField(4)
949            sage: ~I
950            -I
951            sage: (2*I).__invert__()
952            -1/2*I
953        """
954        if IsZero_ZZX(self.__numerator):
955            raise ZeroDivisionError
956        cdef NumberFieldElement x
957        x = self._new()
958        self._invert_c_(&x.__numerator, &x.__denominator)
959        x._reduce_c_()
960        return x
961#        K = self.parent()
962#        quotient = K(1)._pari_('x') / self._pari_('x')
963#        if isinstance(K, sage.rings.number_field.number_field.NumberField_relative):
964#            return K(K.pari_rnf().rnfeltreltoabs(quotient))
965#        else:
966#            return K(quotient)
967
968    def _integer_(self):
969        """
970        Returns a rational integer if this element is actually a rational integer.
971
972        EXAMPLES:
973            sage: C.<I>=CyclotomicField(4)
974            sage: (~I)._integer_()
975            Traceback (most recent call last):
976            ...
977            TypeError: Unable to coerce -I to an integer
978            sage: (2*I*I)._integer_()
979            -2
980        """
981        if ZZX_deg(self.__numerator) >= 1:
982            raise TypeError, "Unable to coerce %s to an integer"%self
983        return ZZ(self._rational_())
984
985    def _rational_(self):
986        """
987        Returns a rational number if this element is actually a rational number.
988
989        EXAMPLES:
990            sage: C.<I>=CyclotomicField(4)
991            sage: (~I)._rational_()
992            Traceback (most recent call last):
993            ...
994            TypeError: Unable to coerce -I to a rational
995            sage: (I*I/2)._rational_()
996            -1/2
997        """
998        if ZZX_deg(self.__numerator) >= 1:
999            raise TypeError, "Unable to coerce %s to a rational"%self
1000        cdef Integer num
1001        num = PY_NEW(Integer)
1002        ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
1003        return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1004
1005    def conjugate(self):
1006        """
1007        Return the complex conjugate of the number field element.  Currently,
1008        this is implemented for cyclotomic fields and quadratic extensions of Q. 
1009        It seems likely that there are other number fields for which the idea of
1010        a conjugate would be easy to compute.
1011
1012        EXAMPLES:
1013            sage: k.<I> = QuadraticField(-1)
1014            sage: I.conjugate()
1015            -I
1016            sage: (I/(1+I)).conjugate()
1017            -1/2*I + 1/2
1018            sage: z6=CyclotomicField(6).gen(0)
1019            sage: (2*z6).conjugate()
1020            -2*zeta6 + 2
1021
1022            sage: K.<b> = NumberField(x^3 - 2)
1023            sage: b.conjugate()
1024            Traceback (most recent call last):
1025            ...
1026            NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
1027        """
1028        coeffs = self.parent().polynomial().list()
1029        if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
1030            # polynomial looks like x^2+d
1031            # i.e. we live in a quadratic extension of QQ
1032            if coeffs[0] > 0:
1033                gen = self.parent().gen()
1034                return self.polynomial()(-gen)
1035            else:
1036                return self
1037        elif isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
1038            # We are in a cyclotomic field
1039            # Replace the generator zeta_n with (zeta_n)^(n-1)
1040            gen = self.parent().gen()
1041            return self.polynomial()(gen ** (gen.multiplicative_order()-1))
1042        else:
1043            raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
1044
1045    def polynomial(self, var='x'):
1046        """
1047        Return the underlying polynomial corresponding to this
1048        number field element.
1049
1050        The resulting polynomial is currently *not* cached.
1051
1052        EXAMPLES:
1053            sage: K.<a> = NumberField(x^5 - x - 1)
1054            sage: f = (-2/3 + 1/3*a)^4; f
1055            1/81*a^4 - 8/81*a^3 + 8/27*a^2 - 32/81*a + 16/81
1056            sage: g = f.polynomial(); g
1057            1/81*x^4 - 8/81*x^3 + 8/27*x^2 - 32/81*x + 16/81
1058            sage: parent(g)
1059            Univariate Polynomial Ring in x over Rational Field
1060
1061        Note that the result of this function is not cached (should this
1062        be changed?):
1063            sage: g is f.polynomial()
1064            False       
1065        """
1066        return QQ[var](self._coefficients())
1067
1068    def _coefficients(self):
1069        """
1070        Return the coefficients of the underlying polynomial corresponding to this
1071        number field element.
1072
1073        OUTPUT:
1074             -- a list whose length corresponding to the degree of this element
1075                written in terms of a generator.
1076
1077        EXAMPLES:
1078           
1079        """
1080        coeffs = []
1081        cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1082        cdef Integer numCoeff
1083        cdef int i
1084        for i from 0 <= i <= ZZX_deg(self.__numerator):
1085            numCoeff = PY_NEW(Integer)
1086            ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
1087            coeffs.append( numCoeff / den )
1088        return coeffs
1089       
1090    cdef void _ntl_coeff_as_mpz(self, mpz_t* z, long i):
1091        if i > ZZX_deg(self.__numerator):
1092            mpz_set_ui(z[0], 0)
1093        else:
1094            ZZX_getitem_as_mpz(z, &self.__numerator, i)
1095       
1096    cdef void _ntl_denom_as_mpz(self, mpz_t* z):
1097        cdef Integer denom = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1098        mpz_set(z[0], denom.value)
1099
1100    def denominator(self):
1101        """
1102        Return the denominator of this element, which is by definition
1103        the denominator of the corresponding polynomial
1104        representation.  I.e., elements of number fields are
1105        represented as a polynomial (in reduced form) modulo the
1106        modulus of the number field, and the denominator is the
1107        denominator of this polynomial.
1108
1109        EXAMPLES:
1110            sage: K.<z> = CyclotomicField(3)
1111            sage: a = 1/3 + (1/5)*z
1112            sage: print a.denominator()
1113            15
1114        """
1115        return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1116
1117    def _set_multiplicative_order(self, n):
1118        """
1119        Set the multiplicative order of this number field element.
1120
1121        WARNING -- use with caution -- only for internal use!  End
1122        users should never call this unless they have a very good
1123        reason to do so.
1124
1125        EXAMPLES:
1126            sage: K.<a> = NumberField(x^2 + x + 1)
1127            sage: a._set_multiplicative_order(3)
1128            sage: a.multiplicative_order()
1129            3
1130
1131        You can be evil with this so be careful.  That's why the function
1132        name begins with an underscore.
1133            sage: a._set_multiplicative_order(389)
1134            sage: a.multiplicative_order()
1135            389       
1136        """
1137        self.__multiplicative_order = n
1138
1139    def multiplicative_order(self):
1140        """
1141        Return the multiplicative order of this number field element.
1142
1143        EXAMPLES:
1144            sage: K.<z> = CyclotomicField(5)
1145            sage: z.multiplicative_order()
1146            5
1147            sage: (-z).multiplicative_order()
1148            10
1149            sage: (1+z).multiplicative_order()
1150            +Infinity       
1151        """
1152        if self.__multiplicative_order is not None:
1153            return self.__multiplicative_order
1154
1155        if self.is_rational_c():
1156            self.__multiplicative_order = self._rational_().multiplicative_order()
1157            return self.__multiplicative_order
1158
1159        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
1160            t = self.parent()._multiplicative_order_table()
1161            f = self.polynomial()
1162            if t.has_key(f):
1163                self.__multiplicative_order = t[f]
1164                return self.__multiplicative_order
1165
1166        ####################################################################
1167        # VERY DUMB Algorithm to compute the multiplicative_order of
1168        # an element x of a number field K.
1169        #
1170        # 1. Find an integer B such that if n>=B then phi(n) > deg(K).
1171        #    For this use that for n>6 we have phi(n) >= log_2(n)
1172        #    (to see this think about the worst prime factorization
1173        #    in the multiplicative formula for phi.)
1174        # 2. Compute x, x^2, ..., x^B in order to determine the multiplicative_order.
1175        #
1176        # todo-- Alternative: Only do the above if we don't require an optional
1177        # argument which gives a multiple of the order, which is usually
1178        # something available in any actual application.
1179        #
1180        # BETTER TODO: Factor cyclotomic polynomials over K to determine
1181        # possible orders of elements?  Is there something even better?
1182        #
1183        ####################################################################
1184        d = self.parent().degree()
1185        B = max(7, 2**d+1)
1186        x = self
1187        i = 1
1188        while i < B:
1189            if x == 1:
1190                self.__multiplicative_order = i
1191                return self.__multiplicative_order
1192            x *= self
1193            i += 1
1194
1195        # it must have infinite order
1196        self.__multiplicative_order = sage.rings.infinity.infinity
1197        return self.__multiplicative_order
1198
1199    cdef bint is_rational_c(self):
1200        return ZZX_deg(self.__numerator) == 0
1201               
1202    def trace(self):
1203        """
1204        Return the trace of this number field element.
1205
1206        EXAMPLES:
1207            sage: K.<a> = NumberField(x^3 -132/7*x^2 + x + 1); K
1208            Number Field in a with defining polynomial x^3 - 132/7*x^2 + x + 1
1209            sage: a.trace()
1210            132/7
1211            sage: (a+1).trace() == a.trace() + 3
1212            True       
1213        """
1214        K = self.parent().base_ring()
1215        return K(self._pari_('x').trace())
1216
1217    def norm(self):
1218        """
1219        Return the norm of this number field element.
1220
1221        EXAMPLES:
1222            sage: K.<a> = NumberField(x^3 + x^2 + x + -132/7); K
1223            Number Field in a with defining polynomial x^3 + x^2 + x - 132/7
1224            sage: a.norm()
1225            132/7
1226            sage: K(0).norm()
1227            0       
1228        """
1229        K = self.parent().base_ring()
1230        return K(self._pari_('x').norm())
1231
1232    def charpoly(self, var='x'):
1233        raise NotImplementedError, "Subclasses of NumberFieldElement must override charpoly()"
1234
1235    def minpoly(self, var='x'):
1236        """
1237        Return the minimal polynomial of this number field element.
1238
1239        EXAMPLES:
1240            sage: K.<a> = NumberField(x^2+3)
1241            sage: a.minpoly('x')
1242            x^2 + 3
1243            sage: R.<X> = K['X']
1244            sage: L.<b> = K.extension(X^2-(22 + a))
1245            sage: b.minpoly('t')
1246            t^4 + (-44)*t^2 + 487
1247            sage: b^2 - (22+a)
1248            0       
1249        """
1250        return self.charpoly(var).radical() # square free part of charpoly
1251
1252    def is_integral(self):
1253        r"""
1254        Determine if a number is in the ring of integers
1255        of this number field.
1256       
1257        EXAMPLES:
1258            sage: K.<a> = NumberField(x^2 + 23, 'a')
1259            sage: a.is_integral()
1260            True
1261            sage: t = (1+a)/2
1262            sage: t.is_integral()
1263            True
1264            sage: t.minpoly()
1265            x^2 - x + 6
1266            sage: t = a/2
1267            sage: t.is_integral()
1268            False
1269            sage: t.minpoly()
1270            x^2 + 23/4
1271        """
1272        return all([a in ZZ for a in self.minpoly()])
1273
1274    def matrix(self):
1275        r"""
1276        The matrix of right multiplication by the element on the power
1277        basis $1, x, x^2, \ldots, x^{d-1}$ for the number field.  Thus
1278        the {\em rows} of this matrix give the images of each of the $x^i$.
1279
1280        EXAMPLES:
1281
1282        Regular number field:
1283            sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
1284            sage: M = a.matrix(); M
1285            [0 1 0]
1286            [0 0 1]
1287            [5 0 0]
1288            sage: M.base_ring() is QQ
1289            True
1290
1291        """
1292##         Relative number field:
1293##             sage: L.<b> = K.extension(K['x'].0^2 - 2)
1294##             sage: 1*b, b*b, b**3, b**6
1295##             (b, b^2, b^3, 6*b^4 - 10*b^3 - 12*b^2 - 60*b - 17)
1296##             sage: L.pari_rnf().rnfeltabstorel(b._pari_())
1297##             x - y
1298##             sage: L.pari_rnf().rnfeltabstorel((b**2)._pari_())
1299##             2
1300##             sage: M = b.matrix(); M
1301##             [0 1]
1302##             [3 0]
1303##             sage: M.base_ring() is K
1304##             True
1305
1306#         Absolute number field:
1307#             sage: M = L.absolute_field()[0].gen().matrix(); M
1308#             [  0   1   0   0   0   0]
1309#             [  0   0   1   0   0   0]
1310#             [  0   0   0   1   0   0]
1311#             [  0   0   0   0   1   0]
1312#             [  0   0   0   0   0   1]
1313#             [  2 -90 -27 -10   9   0]
1314#             sage: M.base_ring() is QQ
1315#             True
1316
1317#         More complicated relative number field:
1318#             sage: L.<b> = K.extension(K['x'].0^2 - a); L
1319#             Extension by x^2 + -a of the Number Field in a with defining polynomial x^3 - 5
1320#             sage: M = b.matrix(); M
1321#             [0 1]
1322#             [a 0]
1323#             sage: M.base_ring()
1324#             sage: M.base_ring() is K
1325#             True
1326        # Mutiply each power of field generator on
1327        # the left by this element; make matrix
1328        # whose rows are the coefficients of the result,
1329        # and transpose.
1330        if self.__matrix is None:
1331            K = self.parent()
1332            v = []
1333            x = K.gen()
1334            a = K(1)
1335            d = K.degree()
1336            for n in range(d):
1337                v += (a*self).list()
1338                a *= x
1339            k = K.base_ring()
1340            import sage.matrix.matrix_space
1341            M = sage.matrix.matrix_space.MatrixSpace(k, d)
1342            self.__matrix = M(v)
1343        return self.__matrix
1344
1345    def list(self):
1346        """
1347        Return list of coefficients of self written in terms of a power basis.
1348        """
1349        # Power basis list is total nonsense, unless the parent of self is an
1350        # absolute extension.
1351        raise NotImplementedError
1352       
1353       
1354cdef class NumberFieldElement_absolute(NumberFieldElement):
1355
1356    def _pari_(self, var='x'):
1357        """
1358        Return PARI C-library object corresponding to self.
1359
1360        EXAMPLES:
1361            sage: k.<j> = QuadraticField(-1)
1362            sage: j._pari_('j')
1363            Mod(j, j^2 + 1)
1364            sage: pari(j)
1365            Mod(x, x^2 + 1)
1366
1367            sage: y = QQ['y'].gen()
1368            sage: k.<j> = NumberField(y^3 - 2)
1369            sage: pari(j)
1370            Mod(x, x^3 - 2)
1371
1372        By default the variable name is 'x', since in PARI many variable
1373        names are reserved:
1374            sage: theta = polygen(QQ, 'theta')
1375            sage: M.<theta> = NumberField(theta^2 + 1)
1376            sage: pari(theta)
1377            Mod(x, x^2 + 1)
1378
1379        If you try do coerce a generator called I to PARI, hell may
1380        break loose:
1381            sage: k.<I> = QuadraticField(-1)
1382            sage: I._pari_('I')
1383            Traceback (most recent call last):
1384            ...
1385            PariError: forbidden (45)
1386
1387        Instead, request the variable be named different for the coercion:
1388            sage: pari(I)
1389            Mod(x, x^2 + 1)
1390            sage: I._pari_('i')
1391            Mod(i, i^2 + 1)
1392            sage: I._pari_('II')
1393            Mod(II, II^2 + 1)
1394        """
1395        try:
1396            return self.__pari[var]
1397        except KeyError:
1398            pass
1399        except TypeError:
1400            self.__pari = {}
1401        if var is None:
1402            var = self.parent().variable_name()
1403        f = self.polynomial()._pari_()
1404        gp = self.parent().polynomial()
1405        if gp.name() != 'x':
1406            gp = gp.change_variable_name('x')
1407        g = gp._pari_()
1408        gv = str(gp.parent().gen())
1409        if var != 'x':
1410            f = f.subst("x",var)
1411        if var != gv:
1412            g = g.subst(gv, var)
1413        h = f.Mod(g)
1414        self.__pari[var] = h
1415        return h
1416       
1417    cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
1418        cdef ntl_ZZX _num
1419        cdef ntl_ZZ _den
1420        _num, _den = self.parent().polynomial_ntl()
1421        num[0] = _num.x
1422        den[0] = _den.x
1423
1424    def charpoly(self, var='x'):
1425        r"""
1426        The characteristic polynomial of this element over $\Q$.
1427
1428        EXAMPLES:
1429
1430        We compute the charpoly of cube root of $2$.
1431
1432            sage: R.<x> = QQ[]
1433            sage: K.<a> = NumberField(x^3-2)
1434            sage: a.charpoly('x')
1435            x^3 - 2
1436
1437        """
1438        R = self.parent().base_ring()[var]
1439        return R(self._pari_('x').charpoly())
1440       
1441    def list(self):
1442        """
1443        Return list of coefficients of self written in terms of a power basis.
1444       
1445        EXAMPLE:
1446            sage: K.<z> = CyclotomicField(3)
1447            sage: (2+3/5*z).list()
1448            [2, 3/5]
1449            sage: (5*z).list()
1450            [0, 5]
1451            sage: K(3).list()
1452            [3, 0]
1453        """
1454        n = self.parent().degree()
1455        v = self._coefficients()
1456        z = sage.rings.rational.Rational(0)
1457        return v + [z]*(n - len(v))
1458       
1459               
1460
1461cdef class NumberFieldElement_relative(NumberFieldElement):
1462
1463    def _pari_(self, var='x'):
1464        """
1465        Return PARI C-library object corresponding to self.
1466
1467        EXAMPLES:
1468        By default the variable name is 'x', since in PARI many variable
1469        names are reserved.
1470            sage: y = QQ['y'].gen()
1471            sage: k.<j> = NumberField([y^3 - 2, y^2 - 7])
1472            sage: pari(j)
1473            Mod(42/5515*x^5 - 9/11030*x^4 - 196/1103*x^3 + 273/5515*x^2 + 10281/5515*x + 4459/11030, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
1474            sage: j^2
1475            7
1476            sage: pari(j)^2
1477            Mod(7, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
1478        """
1479        try:
1480            return self.__pari[var]
1481        except KeyError:
1482            pass
1483        except TypeError:
1484            self.__pari = {}
1485        if var is None:
1486            var = self.parent().variable_name()
1487        f = self.polynomial()._pari_()
1488        g = str(self.parent().pari_polynomial())
1489        base = self.parent().base_ring()
1490        gsub = base.gen()._pari_()
1491        gsub = str(gsub).replace('x', 'y')
1492        g = g.replace('y', gsub)
1493        h = f.Mod(g)
1494        self.__pari[var] = h
1495        return h
1496       
1497    cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
1498        cdef long i
1499        cdef ZZ_c coeff
1500        cdef ntl_ZZX _num
1501        cdef ntl_ZZ _den
1502        # ugly temp code
1503        f = self.parent().absolute_polynomial()
1504
1505        __den = f.denominator()
1506        (<Integer>ZZ(__den))._to_ZZ(den)
1507
1508        __num = f * __den
1509        for i from 0 <= i <= __num.degree():
1510            (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
1511            ZZX_SetCoeff( num[0], i, coeff )
1512
1513    def __repr__(self):
1514        K = self.parent()
1515        # Compute representation of self in terms of relative vector space.
1516        w = self.vector()
1517        R = K.base_field()[K.variable_name()]
1518        return repr(R(w.list()))
1519
1520    def vector(self):
1521        return self.parent().vector_space()[2](self)
1522
1523    def charpoly(self, var='x'):
1524        r"""
1525        The characteristic polynomial of this element over $\Q$.
1526
1527        EXAMPLES:
1528
1529        We construct a relative extension and find the characteristic
1530        polynomial over $\Q$.
1531
1532            sage: R.<x> = QQ[]
1533            sage: K.<a> = NumberField(x^3-2)
1534            sage: S.<X> = K[]
1535            sage: L.<b> = NumberField(X^3 + 17); L
1536            Number Field in b with defining polynomial X^3 + 17 over its base field
1537            sage: b.charpoly ()
1538            x^9 + 51*x^6 + 867*x^3 + 4913
1539            sage: b.charpoly()(b)
1540            0
1541            sage: a = L.0; a
1542            b
1543            sage: a.charpoly('x')
1544            x^9 + 51*x^6 + 867*x^3 + 4913
1545            sage: a.charpoly('y')
1546            y^9 + 51*y^6 + 867*y^3 + 4913
1547        """
1548        R = self.parent().base_ring()[var]
1549        g = self.polynomial()  # in QQ[x]
1550        f = self.parent().pari_polynomial()  # # field is QQ[x]/(f)
1551        return R( (g._pari_().Mod(f)).charpoly() )
1552
1553## This might be useful for computing relative charpoly.
1554## BUT -- currently I don't even know how to view elements
1555## as being in terms of the right thing, i.e., this code
1556## below as is lies.
1557##             nf = self.parent()._pari_base_nf()
1558##             prp = self.parent().pari_relative_polynomial()
1559##             elt = str(self.polynomial()._pari_())
1560##             return R(nf.rnfcharpoly(prp, elt))
1561##         # return self.matrix().charpoly('x')
1562
1563
1564cdef class OrderElement_absolute(NumberFieldElement_absolute):
1565    """
1566    Element of an order in an absolute number field.
1567
1568    EXAMPLES:
1569        sage: k.<a> = NumberField(x^2 + 1)
1570    """
1571    def __init__(self, order, f):
1572        K = order.number_field()
1573        NumberFieldElement_absolute.__init__(self, K, f)
1574        self._order = order
1575
1576cdef class OrderElement_relative(NumberFieldElement_relative):
1577    """
1578    Element of an order in a relative number field.
1579    """
1580    def __init__(self, order, f):
1581        K = order.number_field()
1582        NumberFieldElement_relative.__init__(self, K, f)
1583        self._order = order
1584
1585
1586
1587
1588class CoordinateFunction:
1589    def __init__(self, alpha, W, to_V):
1590        self.__alpha = alpha
1591        self.__W = W
1592        self.__to_V = to_V
1593        self.__K = alpha.parent()
1594
1595    def __repr__(self):
1596        return "Coordinate function that writes elements in terms of the powers of %s"%self.__alpha
1597
1598    def alpha(self):
1599        return self.__alpha
1600
1601    def __call__(self, x):
1602        return self.__W.coordinates(self.__to_V(self.__K(x)))
1603   
Note: See TracBrowser for help on using the repository browser.