source: sage/rings/number_field/number_field_element.pyx @ 4745:6171691f1422

Revision 4745:6171691f1422, 32.3 KB checked in by 'Martin Albrecht <malb@…, 6 years ago (diff)

merge
Line 
1"""
2Number Field Elements
3
4AUTHORS:
5    -- Joel B. Mohler (2007-03-09) - First reimplementation into pyrex
6"""
7
8# TODO -- relative extensions need to be completely rewritten, so one
9# can get easy access to representation of elements in their relative
10# form.  Functions like matrix below can't be done until relative
11# extensions are re-written this way.  Also there needs to be class
12# hierarchy for number field elements, integers, etc.  This is a
13# nontrivial project, and it needs somebody to attack it.  I'm amazed
14# how long this has gone unattacked.
15
16#*****************************************************************************
17#       Copyright (C) 2004, 2007 William Stein <wstein@gmail.com>
18#
19#  Distributed under the terms of the GNU General Public License (GPL)
20#
21#    This code is distributed in the hope that it will be useful,
22#    but WITHOUT ANY WARRANTY; without even the implied warranty of
23#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24#    General Public License for more details.
25#
26#  The full text of the GPL is available at:
27#
28#                  http://www.gnu.org/licenses/
29#*****************************************************************************
30
31import operator
32
33include "../../ext/stdsage.pxi"
34include '../../ext/interrupt.pxi'
35
36import sage.rings.field_element
37import sage.rings.infinity
38import sage.rings.polynomial.polynomial_element
39import sage.rings.polynomial.polynomial_ring
40import sage.rings.rational_field
41import sage.rings.rational
42import sage.rings.integer_ring
43import sage.rings.integer
44import sage.rings.arith
45
46import sage.rings.number_field.number_field
47
48from sage.libs.ntl.ntl cimport ntl_ZZ, ntl_ZZX
49from sage.rings.integer_ring cimport IntegerRing_class
50
51from sage.libs.all import pari_gen
52from sage.libs.pari.gen import PariError
53
54QQ = sage.rings.rational_field.QQ
55ZZ = sage.rings.integer_ring.ZZ
56Integer_sage = sage.rings.integer.Integer
57
58def is_NumberFieldElement(x):
59    return isinstance(x, NumberFieldElement)
60
61def __create__NumberFieldElement_version0(parent, poly):
62    return NumberFieldElement(parent, poly)
63
64cdef class NumberFieldElement(FieldElement):
65    """
66    An element of a number field.
67    """
68
69    cdef NumberFieldElement _new(self):
70        """
71        Quickly creates a new initialized NumberFieldElement with the same parent as self.
72        """
73        cdef NumberFieldElement x
74        x = PY_NEW(NumberFieldElement)
75        x._parent = self._parent
76        return x
77
78    def __init__(self, parent, f):
79        """
80        INPUT:
81            parent -- a number field
82            f -- defines an element of a number field.
83
84        EXAMPLES:
85        The following examples illustrate creation of elements of
86        number fields, and some basic arithmetic.
87
88        First we define a polynomial over Q.
89            sage: R.<x> = PolynomialRing(QQ)
90            sage: f = x^2 + 1
91
92        Next we use f to define the number field.
93            sage: K.<a> = NumberField(f); K
94            Number Field in a with defining polynomial x^2 + 1
95            sage: a = K.gen()
96            sage: a^2
97            -1
98            sage: (a+1)^2
99            2*a
100            sage: a^2
101            -1
102            sage: z = K(5); 1/z
103            1/5
104
105        We create a cube root of 2.
106            sage: K.<b> = NumberField(x^3 - 2)
107            sage: b = K.gen()
108            sage: b^3
109            2
110            sage: (b^2 + b + 1)^3
111            12*b^2 + 15*b + 19
112
113        This example illustrates save and load:
114            sage: K.<a> = NumberField(x^17 - 2)
115            sage: s = a^15 - 19*a + 3
116            sage: loads(s.dumps()) == s
117            True
118        """
119        sage.rings.field_element.FieldElement.__init__(self, parent)
120
121        cdef ntl_c_ZZ coeff
122        if isinstance(f, (int, long, Integer_sage)):
123            # set it up and exit immediately
124            # fast pathway
125            (<Integer>ZZ(f))._to_ZZ(&coeff)
126            SetCoeff( self.__numerator, 0, coeff )
127            conv_ZZ_int( self.__denominator, 1 )
128            return
129
130        ppr = parent.polynomial_ring()
131        if isinstance(parent, sage.rings.number_field.number_field.NumberField_extension):
132            ppr = parent.base_field().polynomial_ring()
133
134        if isinstance(f, pari_gen):
135            f = f.lift()
136            f = ppr(f)
137        if not isinstance(f, sage.rings.polynomial.polynomial_element.Polynomial):
138            f = ppr(f)
139        if f.degree() >= parent.degree():
140            if isinstance(parent, sage.rings.number_field.number_field.NumberField_extension):
141                f %= parent.absolute_polynomial()
142            else:
143                f %= parent.polynomial()
144
145        # Set Denominator
146        den = f.denominator()
147        (<Integer>ZZ(den))._to_ZZ(&self.__denominator)
148
149        cdef long i
150        num = f * den
151        for i from 0 <= i <= num.degree():
152            (<Integer>ZZ(num[i]))._to_ZZ(&coeff)
153            SetCoeff( self.__numerator, i, coeff )
154
155    def _lift_cyclotomic_element(self, new_parent):
156        """
157            Creates an element of the passed field from this field.  This is specific to creating elements in a
158        cyclotomic field from elements in another cyclotomic field.  This function aims to make this common
159        coercion extremely fast!
160
161        EXAMPLES:
162            sage: C.<zeta5>=CyclotomicField(5)
163            sage: CyclotomicField(10)(zeta5+1)  # The function _lift_cyclotomic_element does the heavy lifting in the background
164            zeta10^2 + 1
165            sage: (zeta5+1)._lift_cyclotomic_element(CyclotomicField(10))  # There is rarely a purpose to call this function directly
166            zeta10^2 + 1
167
168        AUTHOR:
169            Joel B. Mohler
170        """
171        # Right now, I'm a little confused why quadratic extension fields have a zeta_order function
172        # I would rather they not have this function since I don't want to do this isinstance check here.
173        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):
174            raise TypeError, "The field and the new parent field must both be cyclotomic fields."
175
176        try:
177            small_order = self.parent().zeta_order()
178            large_order = new_parent.zeta_order()
179        except AttributeError:
180            raise TypeError, "The field and the new parent field must both be cyclotomic fields."
181
182        try:
183            _rel = ZZ(large_order / small_order)
184        except TypeError:
185            raise TypeError, "The zeta_order of the new field must be a multiple of the zeta_order of the original."
186
187        cdef NumberFieldElement x
188        x = PY_NEW(NumberFieldElement)
189        x._parent = <ParentWithBase>new_parent
190        x.__denominator = self.__denominator
191        cdef ntl_c_ZZX result
192        cdef ntl_c_ZZ tmp
193        cdef int i
194        cdef int rel = _rel
195        cdef ntl_ZZX _num
196        cdef ntl_ZZ _den
197        _num, _den = new_parent.polynomial_ntl()
198        for i from 0 <= i <= deg(self.__numerator):
199            GetCoeff(tmp, self.__numerator, i)
200            SetCoeff(result, i*rel, tmp)
201        rem_ZZX(x.__numerator, result, _num.x[0])
202        return x
203
204    def __reduce__(self):
205        return __create__NumberFieldElement_version0, \
206               (self.parent(), self.polynomial())
207
208    def __repr__(self):
209        x = self.polynomial()
210        return str(x).replace(x.parent().variable_name(),self.parent().variable_name())
211
212    def _im_gens_(self, codomain, im_gens):
213        # NOTE -- if you ever want to change this so relative number fields are
214        # in terms of a root of a poly.
215        # The issue is that elements of a relative number field are represented in terms
216        # of a generator for the absolute field.  However the morphism gives the image
217        # of gen, which need not be a generator for the absolute field.  The morphism
218        # has to be *over* the relative element.
219        return codomain(self.polynomial()(im_gens[0]))
220
221    def _latex_(self):
222        """
223        Returns the latex representation for this element.
224
225        EXAMPLES:
226            sage: C,zeta12=CyclotomicField(12).objgen()
227            sage: latex(zeta12^4-zeta12)
228            \zeta_{12}^{2} - \zeta_{12} - 1
229        """
230        return self.polynomial()._latex_(name=self.parent().latex_variable_name())
231
232    def _pari_(self, var=None):
233        """
234        Return PARI C-library object corresponding to self.
235
236        EXAMPLES:
237            sage: k.<j> = QuadraticField(-1)
238            sage: j._pari_()
239            Mod(j, j^2 + 1)
240            sage: pari(j)
241            Mod(j, j^2 + 1)
242
243            sage: y = QQ['y'].gen()
244            sage: k.<j> = NumberField(y^3 - 2)
245            sage: pari(j)
246            Mod(j, j^3 - 2)
247
248        If you try do coerce a generator called I to PARI, hell may
249        break loose:
250            sage: k.<I> = QuadraticField(-1)
251            sage: pari(I)
252            Traceback (most recent call last):
253            ...
254            PariError: forbidden (45)
255
256        Instead, request the variable be named different for the coercion:
257            sage: I._pari_('i')
258            Mod(i, i^2 + 1)
259            sage: I._pari_('II')
260            Mod(II, II^2 + 1)
261        """
262        try:
263            return self.__pari[var]
264        except KeyError:
265            pass
266        except TypeError:
267            self.__pari = {}
268        if var is None:
269            var = self.parent().variable_name()
270        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
271            f = self.polynomial()._pari_()
272            g = str(self.parent().pari_relative_polynomial())
273            base = self.parent().base_ring()
274            gsub = base.gen()._pari_()
275            gsub = str(gsub).replace(base.variable_name(), "y")
276            g = g.replace("y", gsub)
277        else:
278            f = self.polynomial()._pari_()
279            gp = self.parent().polynomial()
280            g = gp._pari_()
281            gv = str(gp.parent().gen())
282            if var != 'x':
283                f = f.subst("x",var)
284            if var != gv:
285                g = g.subst(gv, var)
286        h = f.Mod(g)
287        self.__pari[var] = h
288        return h
289
290    def _pari_init_(self, var=None):
291        """
292        Return GP/PARI string representation of self.
293        """
294        if var == None:
295            var = self.parent().variable_name()
296        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
297            f = self.polynomial()._pari_()
298            g = str(self.parent().pari_relative_polynomial())
299            base = self.parent().base_ring()
300            gsub = base.gen()._pari_()
301            gsub = str(gsub).replace(base.variable_name(), "y")
302            g = g.replace("y", gsub)
303        else:
304            f = self.polynomial()._pari_().subst("x",var)
305            g = self.parent().polynomial()._pari_().subst("x",var)
306        return 'Mod(%s, %s)'%(f,g)
307
308    def __getitem__(self, n):
309        return self.polynomial()[n]
310
311    cdef int _cmp_c_impl(left, sage.structure.element.Element right) except -2:
312        cdef NumberFieldElement _right = right
313        return not (ZZX_equal(&left.__numerator, &_right.__numerator) and ZZ_equal(&left.__denominator, &_right.__denominator))
314
315    def __abs__(self):
316        return self.abs(i=0, prec=53)
317
318    def abs(self, i=0, prec=53):
319        """
320        Return the absolute value of this element with respect to the
321        ith complex embedding of parent, to the given precision.
322
323        EXAMPLES:
324            sage: z = CyclotomicField(7).gen()
325            sage: abs(z)
326            1.00000000000000
327            sage: abs(z^2 + 17*z - 3)
328            16.0604426799931
329            sage: K.<a> = NumberField(x^3+17)
330            sage: abs(a)
331            2.57128159065824
332            sage: a.abs(prec=100)
333            2.5712815906582353554531872087
334            sage: a.abs(1,100)
335            2.5712815906582353554531872087
336            sage: a.abs(2,100)
337            2.5712815906582353554531872087
338
339        Here's one where the absolute value depends on the embedding.
340            sage: K.<b> = NumberField(x^2-2)
341            sage: a = 1 + b
342            sage: a.abs(i=0)
343            2.41421356237309
344            sage: a.abs(i=1)
345            0.414213562373095
346        """
347        P = self.parent().complex_embeddings(prec)[i]
348        return abs(P(self))
349
350    def complex_embeddings(self, prec=53):
351        phi = self.parent().complex_embeddings(prec)
352        return [f(self) for f in phi]
353
354    def complex_embedding(self, prec=53, i=0):
355        return self.parent().complex_embeddings(prec)[i](self)
356
357    def __pow__(self, r, mod):
358        right = int(r)
359        if right != r:
360            raise NotImplementedError, "number field element to non-integral power not implemented"
361        if right < 0:
362            x = self.__invert__()
363            right *= -1
364            return sage.rings.arith.generic_power(x, right, one=self.parent()(1))
365        return sage.rings.arith.generic_power(self, right, one=self.parent()(1))
366       
367    def is_square(self):
368        return len(self.sqrt(all=True)) > 0
369       
370    def sqrt(self, all=False):
371        """
372        Returns the square root of this number in the given number field.
373       
374        EXAMPLES:
375            sage: K.<a> = NumberField(x^2 - 3)
376            sage: K(3).sqrt()
377            a
378            sage: K(3).sqrt(all=True)
379            [a, -a]
380            sage: K(a^10).sqrt()
381            9*a
382            sage: K(49).sqrt()
383            7
384            sage: K(1+a).sqrt()
385            Traceback (most recent call last):
386            ...
387            ValueError: a + 1 not a square in Number Field in a with defining polynomial x^2 - 3
388            sage: K(0).sqrt()
389            0
390            sage: K((7+a)^2).sqrt(all=True)
391            [a + 7, -a - 7]
392           
393            sage: K.<a> = CyclotomicField(7)
394            sage: a.sqrt() 
395            a^4
396           
397            sage: K.<a> = NumberField(x^5 - x + 1)
398            sage: (a^4 + a^2 - 3*a + 2).sqrt()
399            a^3 - a^2
400
401        ALGORITHM:
402            Use Pari to factor $x^2$ - \code{self} in K.
403           
404        """
405        # For now, use pari's factoring abilities
406        R = sage.rings.polynomial.polynomial_ring.PolynomialRing(self._parent, 't')
407        f = R([-self, 0, 1])
408        roots = f.roots()
409        if all:
410            return [r[0] for r in roots]
411        elif len(roots) > 0:
412            return roots[0][0]
413        else:
414            raise ValueError, "%s not a square in %s"%(self, self._parent)
415
416    cdef void _reduce_c_(self):
417        """
418        Pull out common factors from the numerator and denominator!
419        """
420        cdef ntl_c_ZZ gcd
421        cdef ntl_c_ZZ t1
422        cdef ntl_c_ZZX t2
423        content(t1, self.__numerator)
424        GCD_ZZ(gcd, t1, self.__denominator)
425        if sign(gcd) != sign(self.__denominator):
426            negate(t1, gcd)
427            gcd = t1
428        div_ZZX_ZZ(t2, self.__numerator, gcd)
429        div_ZZ_ZZ(t1, self.__denominator, gcd)
430        self.__numerator = t2
431        self.__denominator = t1
432
433    cdef ModuleElement _add_c_impl(self, ModuleElement right):
434        cdef NumberFieldElement x
435        cdef NumberFieldElement _right = right
436        x = self._new()
437        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
438        cdef ntl_c_ZZX t1, t2
439        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
440        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
441        add_ZZX(x.__numerator, t1, t2)
442        x._reduce_c_()
443        return x
444
445    cdef ModuleElement _sub_c_impl(self, ModuleElement right):
446        cdef NumberFieldElement x
447        cdef NumberFieldElement _right = right
448        x = self._new()
449        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
450        cdef ntl_c_ZZX t1, t2
451        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
452        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
453        sub_ZZX(x.__numerator, t1, t2)
454        x._reduce_c_()
455        return x
456
457    cdef RingElement _mul_c_impl(self, RingElement right):
458        """
459        Returns the product of self and other as elements of a number field.
460
461        EXAMPLES:
462            sage: C.<zeta12>=CyclotomicField(12)
463            sage: zeta12*zeta12^11
464            1
465        """
466        cdef NumberFieldElement x
467        cdef NumberFieldElement _right = right
468        x = self._new()
469        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
470        cdef ntl_c_ZZ parent_den
471        cdef ntl_c_ZZX parent_num
472        self._parent_poly_c_( &parent_num, &parent_den )
473        _sig_on
474        MulMod_ZZX(x.__numerator, self.__numerator, _right.__numerator, parent_num)
475        _sig_off
476        x._reduce_c_()
477        return x
478
479        #NOTES: In LiDIA, they build a multiplication table for the
480        #number field, so it's not necessary to reduce modulo the
481        #defining polynomial every time:
482        #     src/number_fields/algebraic_num/order.cc: compute_table
483        # but asymptotically fast poly multiplication means it's
484        # actually faster to *not* build a table!?!
485
486    cdef RingElement _div_c_impl(self, RingElement right):
487        """
488        Returns the product of self and other as elements of a number field.
489
490        EXAMPLES:
491            sage: C.<I>=CyclotomicField(4)
492            sage: 1/I
493            -I
494        """
495        cdef NumberFieldElement x
496        cdef NumberFieldElement _right = right
497        cdef ntl_c_ZZX inv_num
498        cdef ntl_c_ZZ inv_den
499        _right._invert_c_(&inv_num, &inv_den)
500        x = self._new()
501        mul_ZZ(x.__denominator, self.__denominator, inv_den)
502        cdef ntl_c_ZZ parent_den
503        cdef ntl_c_ZZX parent_num
504        self._parent_poly_c_( &parent_num, &parent_den )
505        _sig_on
506        MulMod_ZZX(x.__numerator, self.__numerator, inv_num, parent_num)
507        _sig_off
508        x._reduce_c_()
509        return x
510
511    def __floordiv__(self, other):
512        return self / other
513
514    cdef ModuleElement _neg_c_impl(self):
515        cdef NumberFieldElement x
516        x = self._new()
517        mul_ZZX_long(x.__numerator, self.__numerator, -1)
518        x.__denominator = self.__denominator
519        return x
520
521    def __int__(self):
522        """
523        EXAMPLES:
524            sage: C.<I>=CyclotomicField(4)
525            sage: int(1/I)
526            Traceback (most recent call last):
527            ...
528            TypeError: cannot coerce nonconstant polynomial to int
529            sage: int(I*I)
530            -1
531        """
532        return int(self.polynomial())
533
534    def __long__(self):
535        return long(self.polynomial())
536
537    cdef void _parent_poly_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
538        cdef long i
539        cdef ntl_c_ZZ coeff
540        cdef ntl_ZZX _num
541        cdef ntl_ZZ _den
542        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
543            # ugly temp code
544            f = self.parent().absolute_polynomial()
545
546            __den = f.denominator()
547            (<Integer>ZZ(__den))._to_ZZ(den)
548
549            __num = f * __den
550            for i from 0 <= i <= __num.degree():
551                (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
552                SetCoeff( num[0], i, coeff )
553        else:
554            _num, _den = self.parent().polynomial_ntl()
555            num[0] = _num.x[0]
556            den[0] = _den.x[0]
557
558    cdef void _invert_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
559        """
560        Computes the numerator and denominator of the multiplicative inverse of this element.
561
562        Suppose that this element is x/d and the parent mod'ding polynomial is M/D.  The NTL function
563        XGCD( r, s, t, a, b ) computes r,s,t such that $r=s*a+t*b$.  We compute
564        XGCD( r, s, t, x*D, M*d ) and set
565        num=s*D*d
566        den=r
567
568        EXAMPLES:
569            I'd love to, but since we are dealing with c-types, I can't at this level.
570            Check __invert__ for doc-tests that rely on this functionality.
571        """
572        cdef ntl_c_ZZ parent_den
573        cdef ntl_c_ZZX parent_num
574        self._parent_poly_c_( &parent_num, &parent_den )
575
576        cdef ntl_c_ZZX t # unneeded except to be there
577        cdef ntl_c_ZZX a, b
578        mul_ZZX_ZZ( a, self.__numerator, parent_den )
579        mul_ZZX_ZZ( b, parent_num, self.__denominator )
580        XGCD_ZZX( den[0], num[0],  t, a, b, 1 )
581        mul_ZZX_ZZ( num[0], num[0], parent_den )
582        mul_ZZX_ZZ( num[0], num[0], self.__denominator )
583
584    def __invert__(self):
585        """
586        Returns the multiplicative inverse of self in the number field.
587
588        EXAMPLES:
589            sage: C.<I>=CyclotomicField(4)
590            sage: ~I
591            -I
592            sage: (2*I).__invert__()
593            -1/2*I
594        """
595        if IsZero_ZZX(self.__numerator):
596            raise ZeroDivisionError
597        cdef NumberFieldElement x
598        x = self._new()
599        self._invert_c_(&x.__numerator, &x.__denominator)
600        x._reduce_c_()
601        return x
602#        K = self.parent()
603#        quotient = K(1)._pari_('x') / self._pari_('x')
604#        if isinstance(K, sage.rings.number_field.number_field.NumberField_extension):
605#            return K(K.pari_rnf().rnfeltreltoabs(quotient))
606#        else:
607#            return K(quotient)
608
609    def _integer_(self):
610        """
611        Returns a rational integer if this element is actually a rational integer.
612
613        EXAMPLES:
614            sage: C.<I>=CyclotomicField(4)
615            sage: (~I)._integer_()
616            Traceback (most recent call last):
617            ...
618            TypeError: Unable to coerce -I to an integer
619            sage: (2*I*I)._integer_()
620            -2
621        """
622        if deg(self.__numerator) >= 1:
623            raise TypeError, "Unable to coerce %s to an integer"%self
624        return ZZ(self._rational_())
625
626    def _rational_(self):
627        """
628        Returns a rational number if this element is actually a rational number.
629
630        EXAMPLES:
631            sage: C.<I>=CyclotomicField(4)
632            sage: (~I)._rational_()
633            Traceback (most recent call last):
634            ...
635            TypeError: Unable to coerce -I to a rational
636            sage: (I*I/2)._rational_()
637            -1/2
638        """
639        if deg(self.__numerator) >= 1:
640            raise TypeError, "Unable to coerce %s to a rational"%self
641        cdef Integer num
642        num = PY_NEW(Integer)
643        ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
644        return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
645
646    def conjugate(self):
647        """
648        Return the complex conjugate of the number field element.  Currently,
649        this is implemented for cyclotomic fields and quadratic extensions of Q. 
650        It seems likely that there are other number fields for which the idea of
651        a conjugate would be easy to compute.
652
653        EXAMPLES:
654            sage: k.<I> = QuadraticField(-1)
655            sage: I.conjugate()
656            -I
657            sage: (I/(1+I)).conjugate()
658            -1/2*I + 1/2
659            sage: z6=CyclotomicField(6).gen(0)
660            sage: (2*z6).conjugate()
661            -2*zeta6 + 2
662
663            sage: K.<b> = NumberField(x^3 - 2)
664            sage: b.conjugate()
665            Traceback (most recent call last):
666            ...
667            NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
668        """
669        coeffs = self.parent().polynomial().list()
670        if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
671            # polynomial looks like x^2+d
672            # i.e. we live in a quadratic extension of QQ
673            if coeffs[0] > 0:
674                gen = self.parent().gen()
675                return self.polynomial()(-gen)
676            else:
677                return self
678        elif isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
679            # We are in a cyclotomic field
680            # Replace the generator zeta_n with (zeta_n)^(n-1)
681            gen = self.parent().gen()
682            return self.polynomial()(gen ** (gen.multiplicative_order()-1))
683        else:
684            raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
685
686    def polynomial(self):
687        coeffs = []
688        cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
689        cdef Integer numCoeff
690        cdef int i
691        for i from 0 <= i <= deg(self.__numerator):
692            numCoeff = PY_NEW(Integer)
693            ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
694            coeffs.append( numCoeff / den )
695        return QQ['x'](coeffs)
696
697    def denominator(self):
698        """
699        Return the denominator of this element, which is by definition
700        the denominator of the corresponding polynomial
701        representation.  I.e., elements of number fields are
702        represented as a polynomial (in reduced form) modulo the
703        modulus of the number field, and the denominator is the
704        denominator of this polynomial.
705
706        EXAMPLES:
707            sage: K.<z> = CyclotomicField(3)
708            sage: a = 1/3 + (1/5)*z
709            sage: print a.denominator()
710            15
711        """
712        return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
713
714    def _set_multiplicative_order(self, n):
715        self.__multiplicative_order = n
716
717    def multiplicative_order(self):
718        if self.__multiplicative_order is not None:
719            return self.__multiplicative_order
720
721        if deg(self.__numerator) == 0:
722            if self._rational_() == 1:
723                self.__multiplicative_order = 1
724                return self.__multiplicative_order
725            if self._rational_() == -1:
726                self.__multiplicative_order = 2
727                return self.__multiplicative_order
728
729        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
730            t = self.parent().multiplicative_order_table()
731            f = self.polynomial()
732            if t.has_key(f):
733                self.__multiplicative_order = t[f]
734                return self.__multiplicative_order
735
736        ####################################################################
737        # VERY DUMB Algorithm to compute the multiplicative_order of
738        # an element x of a number field K.
739        #
740        # 1. Find an integer B such that if n>=B then phi(n) > deg(K).
741        #    For this use that for n>6 we have phi(n) >= log_2(n)
742        #    (to see this think about the worst prime factorization
743        #    in the multiplicative formula for phi.)
744        # 2. Compute x, x^2, ..., x^B in order to determine the multiplicative_order.
745        #
746        # todo-- Alternative: Only do the above if we don't require an optional
747        # argument which gives a multiple of the order, which is usually
748        # something available in any actual application.
749        #
750        # BETTER TODO: Factor cyclotomic polynomials over K to determine
751        # possible orders of elements?  Is there something even better?
752        #
753        ####################################################################
754        d = self.parent().degree()
755        B = max(7, 2**d+1)
756        x = self
757        i = 1
758        while i < B:
759            if x == 1:
760                self.__multiplicative_order = i
761                return self.__multiplicative_order
762            x *= self
763            i += 1
764
765        # it must have infinite order
766        self.__multiplicative_order = sage.rings.infinity.infinity
767        return self.__multiplicative_order
768
769    def trace(self):
770        K = self.parent().base_ring()
771        return K(self._pari_('x').trace())
772
773    def norm(self):
774        K = self.parent().base_ring()
775        return K(self._pari_('x').norm())
776
777    def charpoly(self, var):
778        r"""
779        The characteristic polynomial of this element over $\Q$.
780
781        EXAMPLES:
782
783        We compute the charpoly of cube root of $3$.
784
785            sage: R.<x> = QQ[]
786            sage: K.<a> = NumberField(x^3-2)
787            sage: a.charpoly('x')
788            x^3 - 2
789
790        We construct a relative extension and find the characteristic
791        polynomial over $\Q$.
792
793            sage: S.<X> = K[]
794            sage: L.<b> = NumberField(X^3 + 17)
795            sage: L
796            Extension by X^3 + 17 of the Number Field in a with defining polynomial x^3 - 2
797            sage: a = L.0; a
798            b
799            sage: a.charpoly('x')
800            x^9 + 57*x^6 + 165*x^3 + 6859
801            sage: a.charpoly('y')
802            y^9 + 57*y^6 + 165*y^3 + 6859
803        """
804        R = self.parent().base_ring()[var]
805        if not isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
806            return R(self._pari_('x').charpoly())
807        else:
808            g = self.polynomial()  # in QQ[x]
809            f = self.parent().pari_polynomial()  # # field is QQ[x]/(f)
810            return R( (g._pari_('x').Mod(f)).charpoly() )
811
812## This might be useful for computing relative charpoly.
813## BUT -- currently I don't even know how to view elements
814## as being in terms of the right thing, i.e., this code
815## below as is lies.
816##             nf = self.parent()._pari_base_nf()
817##             prp = self.parent().pari_relative_polynomial()
818##             elt = str(self.polynomial()._pari_())
819##             return R(nf.rnfcharpoly(prp, elt))
820##         # return self.matrix().charpoly('x')
821
822    def minpoly(self, var='x'):
823        """
824        Return the minimal polynomial of this number field element.
825
826        EXAMPLES:
827            sage: K.<a> = NumberField(x^2+3)
828            sage: a.minpoly('x')
829            x^2 + 3
830            sage: R.<X> = K['X']
831            sage: L.<b> = K.extension(X^2-(22 + a))
832            sage: b.minpoly('t')
833            t^4 + (-44)*t^2 + 487
834            sage: b^2 - (22+a)
835            0       
836        """
837        return self.charpoly(var).radical() # square free part of charpoly
838
839    def matrix(self):
840        r"""
841        The matrix of right multiplication by the element on the power
842        basis $1, x, x^2, \ldots, x^{d-1}$ for the number field.  Thus
843        the {\em rows} of this matrix give the images of each of the $x^i$.
844
845        EXAMPLES:
846
847        Regular number field:
848            sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
849            sage: M = a.matrix(); M
850            [0 1 0]
851            [0 0 1]
852            [5 0 0]
853            sage: M.base_ring() is QQ
854            True
855
856        """
857##         Relative number field:
858##             sage: L.<b> = K.extension(K['x'].0^2 - 2)
859##             sage: 1*b, b*b, b**3, b**6
860##             (b, b^2, b^3, 6*b^4 - 10*b^3 - 12*b^2 - 60*b - 17)
861##             sage: L.pari_rnf().rnfeltabstorel(b._pari_())
862##             x - y
863##             sage: L.pari_rnf().rnfeltabstorel((b**2)._pari_())
864##             2
865##             sage: M = b.matrix(); M
866##             [0 1]
867##             [3 0]
868##             sage: M.base_ring() is K
869##             True
870
871#         Absolute number field:
872#             sage: M = L.absolute_field().gen().matrix(); M
873#             [  0   1   0   0   0   0]
874#             [  0   0   1   0   0   0]
875#             [  0   0   0   1   0   0]
876#             [  0   0   0   0   1   0]
877#             [  0   0   0   0   0   1]
878#             [  2 -90 -27 -10   9   0]
879#             sage: M.base_ring() is QQ
880#             True
881
882#         More complicated relative number field:
883#             sage: L.<b> = K.extension(K['x'].0^2 - a); L
884#             Extension by x^2 + -a of the Number Field in a with defining polynomial x^3 - 5
885#             sage: M = b.matrix(); M
886#             [0 1]
887#             [a 0]
888#             sage: M.base_ring()
889#             sage: M.base_ring() is K
890#             True
891        # Mutiply each power of field generator on
892        # the left by this element; make matrix
893        # whose rows are the coefficients of the result,
894        # and transpose.
895        if self.__matrix is None:
896            K = self.parent()
897            v = []
898            x = K.gen()
899            a = K(1)
900            d = K.degree()
901            for n in range(d):
902                v += (a*self).list()
903                a *= x
904            k = K.base_ring()
905            import sage.matrix.matrix_space
906            M = sage.matrix.matrix_space.MatrixSpace(k, d)
907            self.__matrix = M(v)
908        return self.__matrix
909
910    def list(self):
911        """
912        EXAMPLE:
913            sage: K.<z> = CyclotomicField(3)
914            sage: (2+3/5*z).list()
915            [2, 3/5]
916            sage: (5*z).list()
917            [0, 5]
918            sage: K(3).list()
919            [3, 0]
920        """
921        P = self.parent()
922        # The algorithm below is total nonsense, unless the parent of self is an
923        # absolute extension.
924        if isinstance(P, sage.rings.number_field.number_field.NumberField_extension):
925            raise NotImplementedError
926        n = self.parent().degree()
927        v = self.polynomial().list()[:n]
928        z = sage.rings.rational.Rational(0)
929        return v + [z]*(n - len(v))
Note: See TracBrowser for help on using the repository browser.