source: sage/rings/number_field/number_field_element.pyx @ 4603:585de1f30617

Revision 4603:585de1f30617, 32.2 KB checked in by Robert Bradshaw <robertwb@…>, 6 years ago (diff)

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