source: sage/rings/number_field/number_field_element.pyx @ 5944:911f3a41f0a2

Revision 5944:911f3a41f0a2, 34.6 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Fix some issues exposed by doctesting.
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            sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
466            sage: a^3
467            -2/3*a - 1
468            sage: a^3+a
469            1/3*a - 1
470        """
471        cdef NumberFieldElement x
472        cdef NumberFieldElement _right = right
473        cdef ntl_c_ZZ parent_den
474        cdef ntl_c_ZZX parent_num
475        self._parent_poly_c_( &parent_num, &parent_den )
476        # an ugly hack fix for the fact that MulMod doesn't handle non-monic polynomials
477        # I expect that PARI will win out over NTL for reasons of speed and things like this
478        # that will be the elegant fix
479        if ZZX_is_monic( &parent_num ):
480            x = self._new()
481            _sig_on
482            mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
483            MulMod_ZZX(x.__numerator, self.__numerator, _right.__numerator, parent_num)
484            _sig_off
485            x._reduce_c_()
486            return x
487        else:
488            return self.parent()(self._pari_()*right._pari_())
489            #  Hmm, this next bit is not so straight-forward as I thought it should be
490            # I'll get back to this when I benchmark
491#            mul_ZZX(x.__numerator, self.__numerator, _right.__numerator)
492#            if ZZX_degree(&x.__numerator) >= ZZX_degree(&parent_num):
493#                PseudoRem_ZZX(x.__numerator, x.__numerator, parent_num)
494#                mul_ZZ(x.__denominator, x.__denominator, parent_den)
495
496        #NOTES: In LiDIA, they build a multiplication table for the
497        #number field, so it's not necessary to reduce modulo the
498        #defining polynomial every time:
499        #     src/number_fields/algebraic_num/order.cc: compute_table
500        # but asymptotically fast poly multiplication means it's
501        # actually faster to *not* build a table!?!
502
503    cdef RingElement _div_c_impl(self, RingElement right):
504        """
505        Returns the quotient of self and other as elements of a number field.
506
507        EXAMPLES:
508            sage: C.<I>=CyclotomicField(4)
509            sage: 1/I
510            -I
511            sage: I/0
512            Traceback (most recent call last):
513            ...
514            ZeroDivisionError: Number field element division by zero
515           
516            sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
517            sage: a/a
518            1
519            sage: 1/a
520            -a^2 - 2/3
521            sage: a/0
522            Traceback (most recent call last):
523            ...
524            ZeroDivisionError: Number field element division by zero           
525        """
526        cdef NumberFieldElement x
527        cdef NumberFieldElement _right = right
528        cdef ntl_c_ZZX inv_num
529        cdef ntl_c_ZZ inv_den
530        cdef ntl_c_ZZ parent_den
531        cdef ntl_c_ZZX parent_num
532        if not _right:
533            raise ZeroDivisionError, "Number field element division by zero"
534        self._parent_poly_c_( &parent_num, &parent_den )
535        if ZZX_is_monic( &parent_num ):
536            _right._invert_c_(&inv_num, &inv_den)
537            x = self._new()
538            _sig_on
539            mul_ZZ(x.__denominator, self.__denominator, inv_den)
540            MulMod_ZZX(x.__numerator, self.__numerator, inv_num, parent_num)
541            _sig_off
542            x._reduce_c_()
543            return x
544        else:
545            return self.parent()(self._pari_()/right._pari_())
546
547    def __floordiv__(self, other):
548        return self / other
549
550    def __nonzero__(self):
551        return not IsZero_ZZX(self.__numerator)
552
553    cdef ModuleElement _neg_c_impl(self):
554        cdef NumberFieldElement x
555        x = self._new()
556        mul_ZZX_long(x.__numerator, self.__numerator, -1)
557        x.__denominator = self.__denominator
558        return x
559
560    def __int__(self):
561        """
562        EXAMPLES:
563            sage: C.<I>=CyclotomicField(4)
564            sage: int(1/I)
565            Traceback (most recent call last):
566            ...
567            TypeError: cannot coerce nonconstant polynomial to int
568            sage: int(I*I)
569            -1
570        """
571        return int(self.polynomial())
572
573    def __long__(self):
574        return long(self.polynomial())
575
576    cdef void _parent_poly_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
577        cdef long i
578        cdef ntl_c_ZZ coeff
579        cdef ntl_ZZX _num
580        cdef ntl_ZZ _den
581        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
582            # ugly temp code
583            f = self.parent().absolute_polynomial()
584
585            __den = f.denominator()
586            (<Integer>ZZ(__den))._to_ZZ(den)
587
588            __num = f * __den
589            for i from 0 <= i <= __num.degree():
590                (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
591                SetCoeff( num[0], i, coeff )
592        else:
593            _num, _den = self.parent().polynomial_ntl()
594            num[0] = _num.x[0]
595            den[0] = _den.x[0]
596
597    cdef void _invert_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
598        """
599        Computes the numerator and denominator of the multiplicative inverse of this element.
600
601        Suppose that this element is x/d and the parent mod'ding polynomial is M/D.  The NTL function
602        XGCD( r, s, t, a, b ) computes r,s,t such that $r=s*a+t*b$.  We compute
603        XGCD( r, s, t, x*D, M*d ) and set
604        num=s*D*d
605        den=r
606
607        EXAMPLES:
608            I'd love to, but since we are dealing with c-types, I can't at this level.
609            Check __invert__ for doc-tests that rely on this functionality.
610        """
611        cdef ntl_c_ZZ parent_den
612        cdef ntl_c_ZZX parent_num
613        self._parent_poly_c_( &parent_num, &parent_den )
614
615        cdef ntl_c_ZZX t # unneeded except to be there
616        cdef ntl_c_ZZX a, b
617        mul_ZZX_ZZ( a, self.__numerator, parent_den )
618        mul_ZZX_ZZ( b, parent_num, self.__denominator )
619        XGCD_ZZX( den[0], num[0],  t, a, b, 1 )
620        mul_ZZX_ZZ( num[0], num[0], parent_den )
621        mul_ZZX_ZZ( num[0], num[0], self.__denominator )
622
623    def __invert__(self):
624        """
625        Returns the multiplicative inverse of self in the number field.
626
627        EXAMPLES:
628            sage: C.<I>=CyclotomicField(4)
629            sage: ~I
630            -I
631            sage: (2*I).__invert__()
632            -1/2*I
633        """
634        if IsZero_ZZX(self.__numerator):
635            raise ZeroDivisionError
636        cdef NumberFieldElement x
637        x = self._new()
638        self._invert_c_(&x.__numerator, &x.__denominator)
639        x._reduce_c_()
640        return x
641#        K = self.parent()
642#        quotient = K(1)._pari_('x') / self._pari_('x')
643#        if isinstance(K, sage.rings.number_field.number_field.NumberField_extension):
644#            return K(K.pari_rnf().rnfeltreltoabs(quotient))
645#        else:
646#            return K(quotient)
647
648    def _integer_(self):
649        """
650        Returns a rational integer if this element is actually a rational integer.
651
652        EXAMPLES:
653            sage: C.<I>=CyclotomicField(4)
654            sage: (~I)._integer_()
655            Traceback (most recent call last):
656            ...
657            TypeError: Unable to coerce -I to an integer
658            sage: (2*I*I)._integer_()
659            -2
660        """
661        if deg(self.__numerator) >= 1:
662            raise TypeError, "Unable to coerce %s to an integer"%self
663        return ZZ(self._rational_())
664
665    def _rational_(self):
666        """
667        Returns a rational number if this element is actually a rational number.
668
669        EXAMPLES:
670            sage: C.<I>=CyclotomicField(4)
671            sage: (~I)._rational_()
672            Traceback (most recent call last):
673            ...
674            TypeError: Unable to coerce -I to a rational
675            sage: (I*I/2)._rational_()
676            -1/2
677        """
678        if deg(self.__numerator) >= 1:
679            raise TypeError, "Unable to coerce %s to a rational"%self
680        cdef Integer num
681        num = PY_NEW(Integer)
682        ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
683        return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
684
685    def conjugate(self):
686        """
687        Return the complex conjugate of the number field element.  Currently,
688        this is implemented for cyclotomic fields and quadratic extensions of Q. 
689        It seems likely that there are other number fields for which the idea of
690        a conjugate would be easy to compute.
691
692        EXAMPLES:
693            sage: k.<I> = QuadraticField(-1)
694            sage: I.conjugate()
695            -I
696            sage: (I/(1+I)).conjugate()
697            -1/2*I + 1/2
698            sage: z6=CyclotomicField(6).gen(0)
699            sage: (2*z6).conjugate()
700            -2*zeta6 + 2
701
702            sage: K.<b> = NumberField(x^3 - 2)
703            sage: b.conjugate()
704            Traceback (most recent call last):
705            ...
706            NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
707        """
708        coeffs = self.parent().polynomial().list()
709        if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
710            # polynomial looks like x^2+d
711            # i.e. we live in a quadratic extension of QQ
712            if coeffs[0] > 0:
713                gen = self.parent().gen()
714                return self.polynomial()(-gen)
715            else:
716                return self
717        elif isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
718            # We are in a cyclotomic field
719            # Replace the generator zeta_n with (zeta_n)^(n-1)
720            gen = self.parent().gen()
721            return self.polynomial()(gen ** (gen.multiplicative_order()-1))
722        else:
723            raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
724
725    def polynomial(self):
726        coeffs = []
727        cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
728        cdef Integer numCoeff
729        cdef int i
730        for i from 0 <= i <= deg(self.__numerator):
731            numCoeff = PY_NEW(Integer)
732            ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
733            coeffs.append( numCoeff / den )
734        return QQ['x'](coeffs)
735
736    def denominator(self):
737        """
738        Return the denominator of this element, which is by definition
739        the denominator of the corresponding polynomial
740        representation.  I.e., elements of number fields are
741        represented as a polynomial (in reduced form) modulo the
742        modulus of the number field, and the denominator is the
743        denominator of this polynomial.
744
745        EXAMPLES:
746            sage: K.<z> = CyclotomicField(3)
747            sage: a = 1/3 + (1/5)*z
748            sage: print a.denominator()
749            15
750        """
751        return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
752
753    def _set_multiplicative_order(self, n):
754        self.__multiplicative_order = n
755
756    def multiplicative_order(self):
757        if self.__multiplicative_order is not None:
758            return self.__multiplicative_order
759
760        if deg(self.__numerator) == 0:
761            if self._rational_() == 1:
762                self.__multiplicative_order = 1
763                return self.__multiplicative_order
764            if self._rational_() == -1:
765                self.__multiplicative_order = 2
766                return self.__multiplicative_order
767
768        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
769            t = self.parent().multiplicative_order_table()
770            f = self.polynomial()
771            if t.has_key(f):
772                self.__multiplicative_order = t[f]
773                return self.__multiplicative_order
774
775        ####################################################################
776        # VERY DUMB Algorithm to compute the multiplicative_order of
777        # an element x of a number field K.
778        #
779        # 1. Find an integer B such that if n>=B then phi(n) > deg(K).
780        #    For this use that for n>6 we have phi(n) >= log_2(n)
781        #    (to see this think about the worst prime factorization
782        #    in the multiplicative formula for phi.)
783        # 2. Compute x, x^2, ..., x^B in order to determine the multiplicative_order.
784        #
785        # todo-- Alternative: Only do the above if we don't require an optional
786        # argument which gives a multiple of the order, which is usually
787        # something available in any actual application.
788        #
789        # BETTER TODO: Factor cyclotomic polynomials over K to determine
790        # possible orders of elements?  Is there something even better?
791        #
792        ####################################################################
793        d = self.parent().degree()
794        B = max(7, 2**d+1)
795        x = self
796        i = 1
797        while i < B:
798            if x == 1:
799                self.__multiplicative_order = i
800                return self.__multiplicative_order
801            x *= self
802            i += 1
803
804        # it must have infinite order
805        self.__multiplicative_order = sage.rings.infinity.infinity
806        return self.__multiplicative_order
807
808    def trace(self):
809        K = self.parent().base_ring()
810        return K(self._pari_('x').trace())
811
812    def norm(self):
813        K = self.parent().base_ring()
814        return K(self._pari_('x').norm())
815
816    def charpoly(self, var):
817        r"""
818        The characteristic polynomial of this element over $\Q$.
819
820        EXAMPLES:
821
822        We compute the charpoly of cube root of $3$.
823
824            sage: R.<x> = QQ[]
825            sage: K.<a> = NumberField(x^3-2)
826            sage: a.charpoly('x')
827            x^3 - 2
828
829        We construct a relative extension and find the characteristic
830        polynomial over $\Q$.
831
832            sage: S.<X> = K[]
833            sage: L.<b> = NumberField(X^3 + 17)
834            sage: L
835            Extension by X^3 + 17 of the Number Field in a with defining polynomial x^3 - 2
836            sage: a = L.0; a
837            b
838            sage: a.charpoly('x')
839            x^9 + 57*x^6 + 165*x^3 + 6859
840            sage: a.charpoly('y')
841            y^9 + 57*y^6 + 165*y^3 + 6859
842        """
843        R = self.parent().base_ring()[var]
844        if not isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
845            return R(self._pari_('x').charpoly())
846        else:
847            g = self.polynomial()  # in QQ[x]
848            f = self.parent().pari_polynomial()  # # field is QQ[x]/(f)
849            return R( (g._pari_().Mod(f)).charpoly() )
850
851## This might be useful for computing relative charpoly.
852## BUT -- currently I don't even know how to view elements
853## as being in terms of the right thing, i.e., this code
854## below as is lies.
855##             nf = self.parent()._pari_base_nf()
856##             prp = self.parent().pari_relative_polynomial()
857##             elt = str(self.polynomial()._pari_())
858##             return R(nf.rnfcharpoly(prp, elt))
859##         # return self.matrix().charpoly('x')
860
861    def minpoly(self, var='x'):
862        """
863        Return the minimal polynomial of this number field element.
864
865        EXAMPLES:
866            sage: K.<a> = NumberField(x^2+3)
867            sage: a.minpoly('x')
868            x^2 + 3
869            sage: R.<X> = K['X']
870            sage: L.<b> = K.extension(X^2-(22 + a))
871            sage: b.minpoly('t')
872            t^4 + (-44)*t^2 + 487
873            sage: b^2 - (22+a)
874            0       
875        """
876        return self.charpoly(var).radical() # square free part of charpoly
877
878    def is_integral(self):
879        r"""
880        Determine if a number is in the ring of integers
881        of this number field.
882       
883        EXAMPLES:
884            sage: K.<a> = NumberField(x^2 + 23, 'a')
885            sage: a.is_integral()
886            True
887            sage: t = (1+a)/2
888            sage: t.is_integral()
889            True
890            sage: t.minpoly()
891            x^2 - x + 6
892            sage: t = a/2
893            sage: t.is_integral()
894            False
895            sage: t.minpoly()
896            x^2 + 23/4
897        """
898        return all([a in ZZ for a in self.minpoly()])
899
900    def matrix(self):
901        r"""
902        The matrix of right multiplication by the element on the power
903        basis $1, x, x^2, \ldots, x^{d-1}$ for the number field.  Thus
904        the {\em rows} of this matrix give the images of each of the $x^i$.
905
906        EXAMPLES:
907
908        Regular number field:
909            sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
910            sage: M = a.matrix(); M
911            [0 1 0]
912            [0 0 1]
913            [5 0 0]
914            sage: M.base_ring() is QQ
915            True
916
917        """
918##         Relative number field:
919##             sage: L.<b> = K.extension(K['x'].0^2 - 2)
920##             sage: 1*b, b*b, b**3, b**6
921##             (b, b^2, b^3, 6*b^4 - 10*b^3 - 12*b^2 - 60*b - 17)
922##             sage: L.pari_rnf().rnfeltabstorel(b._pari_())
923##             x - y
924##             sage: L.pari_rnf().rnfeltabstorel((b**2)._pari_())
925##             2
926##             sage: M = b.matrix(); M
927##             [0 1]
928##             [3 0]
929##             sage: M.base_ring() is K
930##             True
931
932#         Absolute number field:
933#             sage: M = L.absolute_field().gen().matrix(); M
934#             [  0   1   0   0   0   0]
935#             [  0   0   1   0   0   0]
936#             [  0   0   0   1   0   0]
937#             [  0   0   0   0   1   0]
938#             [  0   0   0   0   0   1]
939#             [  2 -90 -27 -10   9   0]
940#             sage: M.base_ring() is QQ
941#             True
942
943#         More complicated relative number field:
944#             sage: L.<b> = K.extension(K['x'].0^2 - a); L
945#             Extension by x^2 + -a of the Number Field in a with defining polynomial x^3 - 5
946#             sage: M = b.matrix(); M
947#             [0 1]
948#             [a 0]
949#             sage: M.base_ring()
950#             sage: M.base_ring() is K
951#             True
952        # Mutiply each power of field generator on
953        # the left by this element; make matrix
954        # whose rows are the coefficients of the result,
955        # and transpose.
956        if self.__matrix is None:
957            K = self.parent()
958            v = []
959            x = K.gen()
960            a = K(1)
961            d = K.degree()
962            for n in range(d):
963                v += (a*self).list()
964                a *= x
965            k = K.base_ring()
966            import sage.matrix.matrix_space
967            M = sage.matrix.matrix_space.MatrixSpace(k, d)
968            self.__matrix = M(v)
969        return self.__matrix
970
971    def list(self):
972        """
973        EXAMPLE:
974            sage: K.<z> = CyclotomicField(3)
975            sage: (2+3/5*z).list()
976            [2, 3/5]
977            sage: (5*z).list()
978            [0, 5]
979            sage: K(3).list()
980            [3, 0]
981        """
982        P = self.parent()
983        # The algorithm below is total nonsense, unless the parent of self is an
984        # absolute extension.
985        if isinstance(P, sage.rings.number_field.number_field.NumberField_extension):
986            raise NotImplementedError
987        n = self.parent().degree()
988        v = self.polynomial().list()[:n]
989        z = sage.rings.rational.Rational(0)
990        return v + [z]*(n - len(v))
Note: See TracBrowser for help on using the repository browser.