source: sage/rings/number_field/number_field_element.pyx @ 4590:53c1ec355ca3

Revision 4590:53c1ec355ca3, 31.2 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

working on fixing number field arithmetic bug.
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    cdef void _reduce_c_(self):
368        """
369        Pull out common factors from the numerator and denominator!
370        """
371        cdef ntl_c_ZZ gcd
372        cdef ntl_c_ZZ t1
373        cdef ntl_c_ZZX t2
374        content(t1, self.__numerator)
375        GCD_ZZ(gcd, t1, self.__denominator)
376        if sign(gcd) != sign(self.__denominator):
377            negate(t1, gcd)
378            gcd = t1
379        div_ZZX_ZZ(t2, self.__numerator, gcd)
380        div_ZZ_ZZ(t1, self.__denominator, gcd)
381        self.__numerator = t2
382        self.__denominator = t1
383
384    cdef ModuleElement _add_c_impl(self, ModuleElement right):
385        cdef NumberFieldElement x
386        cdef NumberFieldElement _right = right
387        x = self._new()
388        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
389        cdef ntl_c_ZZX t1, t2
390        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
391        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
392        add_ZZX(x.__numerator, t1, t2)
393        x._reduce_c_()
394        return x
395
396    cdef ModuleElement _sub_c_impl(self, ModuleElement right):
397        cdef NumberFieldElement x
398        cdef NumberFieldElement _right = right
399        x = self._new()
400        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
401        cdef ntl_c_ZZX t1, t2
402        mul_ZZX_ZZ(t1, self.__numerator, _right.__denominator)
403        mul_ZZX_ZZ(t2, _right.__numerator, self.__denominator)
404        sub_ZZX(x.__numerator, t1, t2)
405        x._reduce_c_()
406        return x
407
408    cdef RingElement _mul_c_impl(self, RingElement right):
409        """
410        Returns the product of self and other as elements of a number field.
411
412        EXAMPLES:
413            sage: C.<zeta12>=CyclotomicField(12)
414            sage: zeta12*zeta12^11
415            1
416        """
417        cdef NumberFieldElement x
418        cdef NumberFieldElement _right = right
419        x = self._new()
420        mul_ZZ(x.__denominator, self.__denominator, _right.__denominator)
421        cdef ntl_c_ZZ parent_den
422        cdef ntl_c_ZZX parent_num
423        self._parent_poly_c_( &parent_num, &parent_den )
424        _sig_on
425        MulMod_ZZX(x.__numerator, self.__numerator, _right.__numerator, parent_num)
426        _sig_off
427        x._reduce_c_()
428        return x
429
430        #NOTES: In LiDIA, they build a multiplication table for the
431        #number field, so it's not necessary to reduce modulo the
432        #defining polynomial every time:
433        #     src/number_fields/algebraic_num/order.cc: compute_table
434        # but asymptotically fast poly multiplication means it's
435        # actually faster to *not* build a table!?!
436
437    cdef RingElement _div_c_impl(self, RingElement right):
438        """
439        Returns the product of self and other as elements of a number field.
440
441        EXAMPLES:
442            sage: C.<I>=CyclotomicField(4)
443            sage: 1/I
444            -I
445        """
446        cdef NumberFieldElement x
447        cdef NumberFieldElement _right = right
448        cdef ntl_c_ZZX inv_num
449        cdef ntl_c_ZZ inv_den
450        _right._invert_c_(&inv_num, &inv_den)
451        x = self._new()
452        mul_ZZ(x.__denominator, self.__denominator, inv_den)
453        cdef ntl_c_ZZ parent_den
454        cdef ntl_c_ZZX parent_num
455        self._parent_poly_c_( &parent_num, &parent_den )
456        _sig_on
457        MulMod_ZZX(x.__numerator, self.__numerator, inv_num, parent_num)
458        _sig_off
459        x._reduce_c_()
460        return x
461
462    def __floordiv__(self, other):
463        return self / other
464
465    cdef ModuleElement _neg_c_impl(self):
466        cdef NumberFieldElement x
467        x = self._new()
468        mul_ZZX_long(x.__numerator, self.__numerator, -1)
469        x.__denominator = self.__denominator
470        return x
471
472    def __int__(self):
473        """
474        EXAMPLES:
475            sage: C.<I>=CyclotomicField(4)
476            sage: int(1/I)
477            Traceback (most recent call last):
478            ...
479            TypeError: cannot coerce nonconstant polynomial to int
480            sage: int(I*I)
481            -1
482        """
483        return int(self.polynomial())
484
485    def __long__(self):
486        return long(self.polynomial())
487
488    cdef void _parent_poly_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
489        cdef long i
490        cdef ntl_c_ZZ coeff
491        cdef ntl_ZZX _num
492        cdef ntl_ZZ _den
493        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
494            # ugly temp code
495            f = self.parent().absolute_polynomial()
496
497            __den = f.denominator()
498            (<Integer>ZZ(__den))._to_ZZ(den)
499
500            __num = f * __den
501            for i from 0 <= i <= __num.degree():
502                (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
503                SetCoeff( num[0], i, coeff )
504        else:
505            _num, _den = self.parent().polynomial_ntl()
506            num[0] = _num.x[0]
507            den[0] = _den.x[0]
508
509    cdef void _invert_c_(self, ntl_c_ZZX *num, ntl_c_ZZ *den):
510        """
511        Computes the numerator and denominator of the multiplicative inverse of this element.
512
513        Suppose that this element is x/d and the parent mod'ding polynomial is M/D.  The NTL function
514        XGCD( r, s, t, a, b ) computes r,s,t such that $r=s*a+t*b$.  We compute
515        XGCD( r, s, t, x*D, M*d ) and set
516        num=s*D*d
517        den=r
518
519        EXAMPLES:
520            I'd love to, but since we are dealing with c-types, I can't at this level.
521            Check __invert__ for doc-tests that rely on this functionality.
522        """
523        cdef ntl_c_ZZ parent_den
524        cdef ntl_c_ZZX parent_num
525        self._parent_poly_c_( &parent_num, &parent_den )
526
527        cdef ntl_c_ZZX t # unneeded except to be there
528        cdef ntl_c_ZZX a, b
529        mul_ZZX_ZZ( a, self.__numerator, parent_den )
530        mul_ZZX_ZZ( b, parent_num, self.__denominator )
531        XGCD_ZZX( den[0], num[0],  t, a, b, 1 )
532        mul_ZZX_ZZ( num[0], num[0], parent_den )
533        mul_ZZX_ZZ( num[0], num[0], self.__denominator )
534
535    def __invert__(self):
536        """
537        Returns the multiplicative inverse of self in the number field.
538
539        EXAMPLES:
540            sage: C.<I>=CyclotomicField(4)
541            sage: ~I
542            -I
543            sage: (2*I).__invert__()
544            -1/2*I
545        """
546        if IsZero_ZZX(self.__numerator):
547            raise ZeroDivisionError
548        cdef NumberFieldElement x
549        x = self._new()
550        self._invert_c_(&x.__numerator, &x.__denominator)
551        x._reduce_c_()
552        return x
553#        K = self.parent()
554#        quotient = K(1)._pari_('x') / self._pari_('x')
555#        if isinstance(K, sage.rings.number_field.number_field.NumberField_extension):
556#            return K(K.pari_rnf().rnfeltreltoabs(quotient))
557#        else:
558#            return K(quotient)
559
560    def _integer_(self):
561        """
562        Returns a rational integer if this element is actually a rational integer.
563
564        EXAMPLES:
565            sage: C.<I>=CyclotomicField(4)
566            sage: (~I)._integer_()
567            Traceback (most recent call last):
568            ...
569            TypeError: Unable to coerce -I to an integer
570            sage: (2*I*I)._integer_()
571            -2
572        """
573        if deg(self.__numerator) >= 1:
574            raise TypeError, "Unable to coerce %s to an integer"%self
575        return ZZ(self._rational_())
576
577    def _rational_(self):
578        """
579        Returns a rational number if this element is actually a rational number.
580
581        EXAMPLES:
582            sage: C.<I>=CyclotomicField(4)
583            sage: (~I)._rational_()
584            Traceback (most recent call last):
585            ...
586            TypeError: Unable to coerce -I to a rational
587            sage: (I*I/2)._rational_()
588            -1/2
589        """
590        if deg(self.__numerator) >= 1:
591            raise TypeError, "Unable to coerce %s to a rational"%self
592        cdef Integer num
593        num = PY_NEW(Integer)
594        ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
595        return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
596
597    def conjugate(self):
598        """
599        Return the complex conjugate of the number field element.  Currently,
600        this is implemented for cyclotomic fields and quadratic extensions of Q. 
601        It seems likely that there are other number fields for which the idea of
602        a conjugate would be easy to compute.
603
604        EXAMPLES:
605            sage: k.<I> = QuadraticField(-1)
606            sage: I.conjugate()
607            -I
608            sage: (I/(1+I)).conjugate()
609            -1/2*I + 1/2
610            sage: z6=CyclotomicField(6).gen(0)
611            sage: (2*z6).conjugate()
612            -2*zeta6 + 2
613
614            sage: K.<b> = NumberField(x^3 - 2)
615            sage: b.conjugate()
616            Traceback (most recent call last):
617            ...
618            NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
619        """
620        coeffs = self.parent().polynomial().list()
621        if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
622            # polynomial looks like x^2+d
623            # i.e. we live in a quadratic extension of QQ
624            if coeffs[0] > 0:
625                gen = self.parent().gen()
626                return self.polynomial()(-gen)
627            else:
628                return self
629        elif isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
630            # We are in a cyclotomic field
631            # Replace the generator zeta_n with (zeta_n)^(n-1)
632            gen = self.parent().gen()
633            return self.polynomial()(gen ** (gen.multiplicative_order()-1))
634        else:
635            raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
636
637    def polynomial(self):
638        coeffs = []
639        cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
640        cdef Integer numCoeff
641        cdef int i
642        for i from 0 <= i <= deg(self.__numerator):
643            numCoeff = PY_NEW(Integer)
644            ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
645            coeffs.append( numCoeff / den )
646        return QQ['x'](coeffs)
647
648    def denominator(self):
649        """
650        Return the denominator of this element, which is by definition
651        the denominator of the corresponding polynomial
652        representation.  I.e., elements of number fields are
653        represented as a polynomial (in reduced form) modulo the
654        modulus of the number field, and the denominator is the
655        denominator of this polynomial.
656
657        EXAMPLES:
658            sage: K.<z> = CyclotomicField(3)
659            sage: a = 1/3 + (1/5)*z
660            sage: print a.denominator()
661            15
662        """
663        return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
664
665    def _set_multiplicative_order(self, n):
666        self.__multiplicative_order = n
667
668    def multiplicative_order(self):
669        if self.__multiplicative_order is not None:
670            return self.__multiplicative_order
671
672        if deg(self.__numerator) == 0:
673            if self._rational_() == 1:
674                self.__multiplicative_order = 1
675                return self.__multiplicative_order
676            if self._rational_() == -1:
677                self.__multiplicative_order = 2
678                return self.__multiplicative_order
679
680        if isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_cyclotomic):
681            t = self.parent().multiplicative_order_table()
682            f = self.polynomial()
683            if t.has_key(f):
684                self.__multiplicative_order = t[f]
685                return self.__multiplicative_order
686
687        ####################################################################
688        # VERY DUMB Algorithm to compute the multiplicative_order of
689        # an element x of a number field K.
690        #
691        # 1. Find an integer B such that if n>=B then phi(n) > deg(K).
692        #    For this use that for n>6 we have phi(n) >= log_2(n)
693        #    (to see this think about the worst prime factorization
694        #    in the multiplicative formula for phi.)
695        # 2. Compute x, x^2, ..., x^B in order to determine the multiplicative_order.
696        #
697        # todo-- Alternative: Only do the above if we don't require an optional
698        # argument which gives a multiple of the order, which is usually
699        # something available in any actual application.
700        #
701        # BETTER TODO: Factor cyclotomic polynomials over K to determine
702        # possible orders of elements?  Is there something even better?
703        #
704        ####################################################################
705        d = self.parent().degree()
706        B = max(7, 2**d+1)
707        x = self
708        i = 1
709        while i < B:
710            if x == 1:
711                self.__multiplicative_order = i
712                return self.__multiplicative_order
713            x *= self
714            i += 1
715
716        # it must have infinite order
717        self.__multiplicative_order = sage.rings.infinity.infinity
718        return self.__multiplicative_order
719
720    def trace(self):
721        K = self.parent().base_ring()
722        return K(self._pari_('x').trace())
723
724    def norm(self):
725        K = self.parent().base_ring()
726        return K(self._pari_('x').norm())
727
728    def charpoly(self, var):
729        r"""
730        The characteristic polynomial of this element over $\Q$.
731
732        EXAMPLES:
733
734        We compute the charpoly of cube root of $3$.
735
736            sage: R.<x> = QQ[]
737            sage: K.<a> = NumberField(x^3-2)
738            sage: a.charpoly('x')
739            x^3 - 2
740
741        We construct a relative extension and find the characteristic
742        polynomial over $\Q$.
743
744            sage: S.<X> = K[]
745            sage: L.<b> = NumberField(X^3 + 17)
746            sage: L
747            Extension by X^3 + 17 of the Number Field in a with defining polynomial x^3 - 2
748            sage: a = L.0; a
749            b
750            sage: a.charpoly('x')
751            x^9 + 57*x^6 + 165*x^3 + 6859
752            sage: a.charpoly('y')
753            y^9 + 57*y^6 + 165*y^3 + 6859
754        """
755        R = self.parent().base_ring()[var]
756        if not isinstance(self.parent(), sage.rings.number_field.number_field.NumberField_extension):
757            return R(self._pari_('x').charpoly())
758        else:
759            g = self.polynomial()  # in QQ[x]
760            f = self.parent().pari_polynomial()  # # field is QQ[x]/(f)
761            return R( (g._pari_('x').Mod(f)).charpoly() )
762
763## This might be useful for computing relative charpoly.
764## BUT -- currently I don't even know how to view elements
765## as being in terms of the right thing, i.e., this code
766## below as is lies.
767##             nf = self.parent()._pari_base_nf()
768##             prp = self.parent().pari_relative_polynomial()
769##             elt = str(self.polynomial()._pari_())
770##             return R(nf.rnfcharpoly(prp, elt))
771##         # return self.matrix().charpoly('x')
772
773    def minpoly(self, var='x'):
774        """
775        Return the minimal polynomial of this number field element.
776
777        EXAMPLES:
778            sage: K.<a> = NumberField(x^2+3)
779            sage: a.minpoly('x')
780            x^2 + 3
781            sage: R.<X> = K['X']
782            sage: L.<b> = K.extension(X^2-(22 + a))
783            sage: b.minpoly('t')
784            t^4 + (-44)*t^2 + 487
785            sage: b^2 - (22+a)
786            0       
787        """
788        # The minimal polynomial is square-free and
789        # divisible by same irreducible factors as
790        # the characteristic polynomial.
791        # TODO: factoring to find the square-free part is idiotic.
792        # Instead use a GCD algorithm!
793        f = sage.rings.polynomial.polynomial_ring.PolynomialRing(QQ, str(var))(1)
794        for g, _ in self.charpoly(var).factor():
795            f *= g
796        return f
797
798    def matrix(self):
799        r"""
800        The matrix of right multiplication by the element on the power
801        basis $1, x, x^2, \ldots, x^{d-1}$ for the number field.  Thus
802        the {\em rows} of this matrix give the images of each of the $x^i$.
803
804        EXAMPLES:
805
806        Regular number field:
807            sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
808            sage: M = a.matrix(); M
809            [0 1 0]
810            [0 0 1]
811            [5 0 0]
812            sage: M.base_ring() is QQ
813            True
814
815        """
816##         Relative number field:
817##             sage: L.<b> = K.extension(K['x'].0^2 - 2)
818##             sage: 1*b, b*b, b**3, b**6
819##             (b, b^2, b^3, 6*b^4 - 10*b^3 - 12*b^2 - 60*b - 17)
820##             sage: L.pari_rnf().rnfeltabstorel(b._pari_())
821##             x - y
822##             sage: L.pari_rnf().rnfeltabstorel((b**2)._pari_())
823##             2
824##             sage: M = b.matrix(); M
825##             [0 1]
826##             [3 0]
827##             sage: M.base_ring() is K
828##             True
829
830#         Absolute number field:
831#             sage: M = L.absolute_field().gen().matrix(); M
832#             [  0   1   0   0   0   0]
833#             [  0   0   1   0   0   0]
834#             [  0   0   0   1   0   0]
835#             [  0   0   0   0   1   0]
836#             [  0   0   0   0   0   1]
837#             [  2 -90 -27 -10   9   0]
838#             sage: M.base_ring() is QQ
839#             True
840
841#         More complicated relative number field:
842#             sage: L.<b> = K.extension(K['x'].0^2 - a); L
843#             Extension by x^2 + -a of the Number Field in a with defining polynomial x^3 - 5
844#             sage: M = b.matrix(); M
845#             [0 1]
846#             [a 0]
847#             sage: M.base_ring()
848#             sage: M.base_ring() is K
849#             True
850        # Mutiply each power of field generator on
851        # the left by this element; make matrix
852        # whose rows are the coefficients of the result,
853        # and transpose.
854        if self.__matrix is None:
855            K = self.parent()
856            v = []
857            x = K.gen()
858            a = K(1)
859            d = K.degree()
860            for n in range(d):
861                v += (a*self).list()
862                a *= x
863            k = K.base_ring()
864            import sage.matrix.matrix_space
865            M = sage.matrix.matrix_space.MatrixSpace(k, d)
866            self.__matrix = M(v)
867        return self.__matrix
868
869    def list(self):
870        """
871        EXAMPLE:
872            sage: K.<z> = CyclotomicField(3)
873            sage: (2+3/5*z).list()
874            [2, 3/5]
875            sage: (5*z).list()
876            [0, 5]
877            sage: K(3).list()
878            [3, 0]
879        """
880        P = self.parent()
881        # The algorithm below is total nonsense, unless the parent of self is an
882        # absolute extension.
883        if isinstance(P, sage.rings.number_field.number_field.NumberField_extension):
884            raise NotImplementedError
885        n = self.parent().degree()
886        v = self.polynomial().list()[:n]
887        z = sage.rings.rational.Rational(0)
888        return v + [z]*(n - len(v))
Note: See TracBrowser for help on using the repository browser.