Attachment 'number_field_element.pyx'

Download

   1 """
   2 Number Field Elements
   3 
   4 AUTHORS:
   5 
   6 - William Stein: version before it got Cython'd
   7 
   8 - Joel B. Mohler (2007-03-09): First reimplementation in Cython
   9 
  10 - William Stein (2007-09-04): add doctests
  11 
  12 - Robert Bradshaw (2007-09-15): specialized classes for relative and
  13   absolute elements
  14 
  15 - John Cremona (2009-05-15): added support for local and global
  16   logarithmic heights.
  17 
  18 """
  19 
  20 #*****************************************************************************
  21 #       Copyright (C) 2004, 2007 William Stein <wstein@gmail.com>
  22 #
  23 #  Distributed under the terms of the GNU General Public License (GPL)
  24 #
  25 #    This code is distributed in the hope that it will be useful,
  26 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  27 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28 #    General Public License for more details.
  29 #
  30 #  The full text of the GPL is available at:
  31 #
  32 #                  http://www.gnu.org/licenses/
  33 #*****************************************************************************
  34 
  35 import operator
  36 
  37 include '../../ext/interrupt.pxi'
  38 include '../../ext/python_int.pxi'
  39 include "../../ext/stdsage.pxi"
  40 
  41 import sage.rings.field_element
  42 import sage.rings.infinity
  43 import sage.rings.polynomial.polynomial_element
  44 import sage.rings.rational_field
  45 import sage.rings.rational
  46 import sage.rings.integer_ring
  47 import sage.rings.integer
  48 import sage.rings.arith
  49 
  50 import number_field
  51 
  52 from sage.rings.integer_ring cimport IntegerRing_class
  53 from sage.rings.rational cimport Rational
  54 
  55 from sage.modules.free_module_element import vector
  56 
  57 from sage.libs.all import pari_gen, pari
  58 from sage.libs.pari.gen import PariError
  59 from sage.structure.element cimport Element, generic_power_c
  60 
  61 QQ = sage.rings.rational_field.QQ
  62 ZZ = sage.rings.integer_ring.ZZ
  63 Integer_sage = sage.rings.integer.Integer
  64 
  65 from sage.rings.real_mpfi import RealInterval
  66 
  67 from sage.rings.complex_field import ComplexField
  68 CC = ComplexField(53)
  69 
  70 # this is a threshold for the charpoly() methods in this file
  71 # for degrees <= this threshold, pari is used
  72 # for degrees > this threshold, sage matrices are used
  73 # the value was decided by running a tuning script on a number of
  74 # architectures; you can find this script attached to trac
  75 # ticket 5213
  76 TUNE_CHARPOLY_NF = 25
  77 
  78 def is_NumberFieldElement(x):
  79     """
  80     Return True if x is of type NumberFieldElement, i.e., an element of
  81     a number field.
  82     
  83     EXAMPLES::
  84     
  85         sage: from sage.rings.number_field.number_field_element import is_NumberFieldElement
  86         sage: is_NumberFieldElement(2)
  87         False
  88         sage: k.<a> = NumberField(x^7 + 17*x + 1)
  89         sage: is_NumberFieldElement(a+1)
  90         True
  91     """
  92     return PY_TYPE_CHECK(x, NumberFieldElement)
  93 
  94 def __create__NumberFieldElement_version0(parent, poly):
  95     """
  96     Used in unpickling elements of number fields pickled under very old Sage versions.
  97     
  98     EXAMPLE::
  99     
 100         sage: k.<a> = NumberField(x^3 - 2)
 101         sage: R.<z> = QQ[]
 102         sage: sage.rings.number_field.number_field_element.__create__NumberFieldElement_version0(k, z^2 + z + 1)
 103         a^2 + a + 1
 104     """
 105     return NumberFieldElement(parent, poly)
 106 
 107 def __create__NumberFieldElement_version1(parent, cls, poly):
 108     """
 109     Used in unpickling elements of number fields.
 110     
 111     EXAMPLES:
 112 
 113     Since this is just used in unpickling, we unpickle.
 114     
 115     ::
 116     
 117         sage: k.<a> = NumberField(x^3 - 2)
 118         sage: loads(dumps(a+1)) == a + 1 # indirect doctest
 119         True
 120 
 121     This also gets called for unpickling order elements; we check that #6462 is
 122     fixed::
 123 
 124         sage: L = NumberField(x^3 - x - 1,'a'); OL = L.maximal_order(); w = OL.0
 125         sage: loads(dumps(w)) == w # indirect doctest
 126         True
 127     """
 128     return cls(parent, poly)
 129 
 130 def _inverse_mod_generic(elt, I):
 131     r""" 
 132     Return an inverse of elt modulo the given ideal. This is a separate
 133     function called from each of the OrderElement_xxx classes, since
 134     otherwise we'd have to have the same code three times over (there
 135     is no OrderElement_generic class - no multiple inheritance). See
 136     trac 4190.
 137     
 138     EXAMPLES::
 139     
 140         sage: OE = NumberField(x^3 - x + 2, 'w').ring_of_integers()
 141         sage: w = OE.ring_generators()[0]
 142         sage: from sage.rings.number_field.number_field_element import _inverse_mod_generic
 143         sage: _inverse_mod_generic(w, 13*OE)
 144         6*w^2 - 6
 145     """
 146     from sage.matrix.constructor import matrix
 147     R = elt.parent()
 148     try:
 149         I = R.ideal(I) 
 150     except ValueError:
 151         raise ValueError, "inverse is only defined modulo integral ideals"
 152     if I == 0:
 153         raise ValueError, "inverse is not defined modulo the zero ideal"
 154     n = R.absolute_degree()
 155     m = matrix(ZZ, map(R.coordinates, I.integral_basis() + [elt*s for s in R.gens()]))
 156     a, b = m.echelon_form(transformation=True)
 157     if a[0:n] != 1:
 158         raise ZeroDivisionError, "%s is not invertible modulo %s" % (elt, I)
 159     v = R.coordinates(1)
 160     y = R(0)
 161     for j in xrange(n):
 162         if v[j] != 0:
 163             y += v[j] * sum([b[j,i+n] * R.gen(i) for i in xrange(n)])
 164     return I.small_residue(y)
 165 
 166 __pynac_pow = False
 167 
 168 cdef class NumberFieldElement(FieldElement):
 169     """
 170     An element of a number field.
 171     
 172     EXAMPLES::
 173     
 174         sage: k.<a> = NumberField(x^3 + x + 1)
 175         sage: a^3
 176         -a - 1
 177     """
 178     cdef _new(self):
 179         """
 180         Quickly creates a new initialized NumberFieldElement with the same
 181         parent as self.
 182         """
 183         cdef NumberFieldElement x
 184         x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
 185         x._parent = self._parent
 186         x.__fld_numerator = self.__fld_numerator
 187         x.__fld_denominator = self.__fld_denominator
 188         return x
 189 
 190     cdef number_field(self):
 191         r"""
 192         
 193         Return the number field of self. Only accessible from Cython.
 194         EXAMPLE::
 195         
 196             sage: K.<a> = NumberField(x^3 + 3)
 197             sage: a._number_field() # indirect doctest
 198             Number Field in a with defining polynomial x^3 + 3
 199         """
 200         return self._parent
 201 
 202     def _number_field(self):
 203         r"""
 204         EXAMPLE::
 205         
 206             sage: K.<a> = NumberField(x^3 + 3)
 207             sage: a._number_field()
 208             Number Field in a with defining polynomial x^3 + 3
 209         """
 210         return self.number_field()
 211 
 212     def __init__(self, parent, f):
 213         """
 214         INPUT:
 215         
 216         
 217         -  ``parent`` - a number field
 218         
 219         -  ``f`` - defines an element of a number field.
 220         
 221         
 222         EXAMPLES:
 223 
 224         The following examples illustrate creation of elements of
 225         number fields, and some basic arithmetic.
 226         
 227         First we define a polynomial over Q::
 228         
 229             sage: R.<x> = PolynomialRing(QQ)
 230             sage: f = x^2 + 1
 231         
 232         Next we use f to define the number field::
 233         
 234             sage: K.<a> = NumberField(f); K
 235             Number Field in a with defining polynomial x^2 + 1
 236             sage: a = K.gen()
 237             sage: a^2
 238             -1
 239             sage: (a+1)^2
 240             2*a
 241             sage: a^2
 242             -1
 243             sage: z = K(5); 1/z
 244             1/5
 245         
 246         We create a cube root of 2::
 247         
 248             sage: K.<b> = NumberField(x^3 - 2)
 249             sage: b = K.gen()
 250             sage: b^3
 251             2
 252             sage: (b^2 + b + 1)^3
 253             12*b^2 + 15*b + 19
 254         
 255         We can create number field elements from PARI::
 256         
 257             sage: K.<a> = NumberField(x^3 - 17)
 258             sage: K(pari(42))
 259             42
 260             sage: K(pari("5/3"))
 261             5/3
 262             sage: K(pari("[3/2, -5, 0]~"))    # Uses Z-basis
 263             -5/3*a^2 + 5/3*a - 1/6
 264             sage: K(pari("-5/3*q^2 + 5/3*q - 1/6"))
 265             -5/3*a^2 + 5/3*a - 1/6
 266             sage: K(pari("Mod(-5/3*q^2 + 5/3*q - 1/6, q^3 - 17)"))
 267             -5/3*a^2 + 5/3*a - 1/6
 268             sage: K(pari("x^5/17"))
 269             a^2
 270 
 271         This example illustrates save and load::
 272         
 273             sage: K.<a> = NumberField(x^17 - 2)
 274             sage: s = a^15 - 19*a + 3
 275             sage: loads(s.dumps()) == s
 276             True
 277         """
 278         sage.rings.field_element.FieldElement.__init__(self, parent)
 279         self.__fld_numerator, self.__fld_denominator = parent.absolute_polynomial_ntl()
 280 
 281         cdef ZZ_c coeff
 282         if isinstance(f, (int, long, Integer_sage)):
 283             # set it up and exit immediately
 284             # fast pathway
 285             (<Integer>ZZ(f))._to_ZZ(&coeff)
 286             ZZX_SetCoeff( self.__numerator, 0, coeff )
 287             ZZ_conv_from_int( self.__denominator, 1 )
 288             return
 289             
 290         elif isinstance(f, NumberFieldElement):
 291             if PY_TYPE(self) is PY_TYPE(f):
 292                 self.__numerator = (<NumberFieldElement>f).__numerator
 293                 self.__denominator = (<NumberFieldElement>f).__denominator
 294                 return
 295             else:
 296                 f = f.polynomial()
 297 
 298         from sage.rings.number_field import number_field_rel
 299         if isinstance(parent, number_field_rel.NumberField_relative):
 300             ppr = parent.base_field().polynomial_ring()
 301         else:
 302             ppr = parent.polynomial_ring()
 303 
 304         if isinstance(f, pari_gen):
 305             if f.type() in ["t_INT", "t_FRAC", "t_POL"]:
 306                 pass
 307             elif f.type() == "t_POLMOD":
 308                 f = f.lift()
 309             else:
 310                 f = self.number_field().pari_nf().nfbasistoalg_lift(f)
 311         f = ppr(f)
 312         if f.degree() >= parent.absolute_degree():
 313             from sage.rings.number_field import number_field_rel
 314             if isinstance(parent, number_field_rel.NumberField_relative):
 315                 f %= ppr(parent.absolute_polynomial())
 316             else:
 317                 f %= parent.polynomial()
 318 
 319         # Set Denominator
 320         den = f.denominator()
 321         (<Integer>ZZ(den))._to_ZZ(&self.__denominator)
 322 
 323         num = f * den
 324         cdef long i
 325         for i from 0 <= i <= num.degree():
 326             (<Integer>ZZ(num[i]))._to_ZZ(&coeff)
 327             ZZX_SetCoeff( self.__numerator, i, coeff )
 328 
 329     def __cinit__(self):
 330         r"""
 331         Initialise C variables.
 332         
 333         EXAMPLE::
 334         
 335             sage: K.<b> = NumberField(x^3 - 2)
 336             sage: b = K.gen(); b # indirect doctest
 337             b
 338         """    
 339         ZZX_construct(&self.__numerator)
 340         ZZ_construct(&self.__denominator)
 341 
 342     def __dealloc__(self):
 343         ZZX_destruct(&self.__numerator)
 344         ZZ_destruct(&self.__denominator)
 345 
 346     def _lift_cyclotomic_element(self, new_parent, bint check=True, int rel=0):
 347         """
 348         Creates an element of the passed field from this field. This is
 349         specific to creating elements in a cyclotomic field from elements
 350         in another cyclotomic field, in the case that
 351         self.number_field()._n() divides new_parent()._n(). This
 352         function aims to make this common coercion extremely fast!
 353         
 354         More general coercion (i.e. of zeta6 into CyclotomicField(3)) is
 355         implemented in the _coerce_from_other_cyclotomic_field method
 356         of a CyclotomicField.
 357         
 358         EXAMPLES::
 359         
 360             sage: C.<zeta5>=CyclotomicField(5)
 361             sage: CyclotomicField(10)(zeta5+1)  # The function _lift_cyclotomic_element does the heavy lifting in the background
 362             zeta10^2 + 1
 363             sage: (zeta5+1)._lift_cyclotomic_element(CyclotomicField(10))  # There is rarely a purpose to call this function directly
 364             zeta10^2 + 1
 365             sage: cf4 = CyclotomicField(4)
 366             sage: cf1 = CyclotomicField(1) ; one = cf1.0
 367             sage: cf4(one)
 368             1
 369             sage: type(cf4(1))
 370             <type 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'>
 371             sage: cf33 = CyclotomicField(33) ; z33 = cf33.0
 372             sage: cf66 = CyclotomicField(66) ; z66 = cf66.0
 373             sage: z33._lift_cyclotomic_element(cf66)
 374             zeta66^2
 375             sage: z66._lift_cyclotomic_element(cf33)
 376             Traceback (most recent call last):
 377             ...
 378             TypeError: The zeta_order of the new field must be a multiple of the zeta_order of the original.
 379             sage: cf33(z66)
 380             -zeta33^17
 381         
 382         AUTHORS:
 383 
 384         - Joel B. Mohler
 385 
 386         - Craig Citro (fixed behavior for different representation of
 387           quadratic field elements)
 388         """
 389         if check:
 390             if not isinstance(self.number_field(), number_field.NumberField_cyclotomic) \
 391                    or not isinstance(new_parent, number_field.NumberField_cyclotomic):
 392                 raise TypeError, "The field and the new parent field must both be cyclotomic fields."
 393 
 394         if rel == 0:
 395             small_order = self.number_field()._n() 
 396             large_order = new_parent._n() 
 397 
 398             try:
 399                 rel = ZZ(large_order / small_order)
 400             except TypeError:
 401                 raise TypeError, "The zeta_order of the new field must be a multiple of the zeta_order of the original."
 402 
 403         ## degree 2 is handled differently, because elements are
 404         ## represented differently
 405         if new_parent.degree() == 2:
 406             return new_parent._element_class(new_parent, self)
 407 
 408         cdef NumberFieldElement x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
 409         x._parent = <ParentWithBase>new_parent
 410         x.__fld_numerator, x.__fld_denominator = new_parent.polynomial_ntl()
 411         x.__denominator = self.__denominator
 412         cdef ZZX_c result
 413         cdef ZZ_c tmp
 414         cdef int i
 415         cdef ntl_ZZX _num
 416         cdef ntl_ZZ _den
 417         for i from 0 <= i <= ZZX_deg(self.__numerator):
 418             tmp = ZZX_coeff(self.__numerator, i)
 419             ZZX_SetCoeff(result, i*rel, tmp)
 420         ZZX_rem(x.__numerator, result, x.__fld_numerator.x)
 421         return x
 422 
 423     def __reduce__(self):
 424         """
 425         Used in pickling number field elements.
 426         
 427         Note for developers: If this is changed, please also change the doctests of __create__NumberFieldElement_version1.
 428         
 429         EXAMPLES::
 430         
 431             sage: k.<a> = NumberField(x^3 - 17*x^2 + 1)
 432             sage: t = a.__reduce__(); t
 433             (<built-in function __create__NumberFieldElement_version1>, (Number Field in a with defining polynomial x^3 - 17*x^2 + 1, <type 'sage.rings.number_field.number_field_element.NumberFieldElement_absolute'>, x))
 434             sage: t[0](*t[1]) == a
 435             True
 436         """
 437         return __create__NumberFieldElement_version1, \
 438                (self.parent(), type(self), self.polynomial())
 439 
 440     def _repr_(self):
 441         """
 442         String representation of this number field element, which is just a
 443         polynomial in the generator.
 444         
 445         EXAMPLES::
 446         
 447             sage: k.<a> = NumberField(x^2 + 2)
 448             sage: b = (2/3)*a + 3/5
 449             sage: b._repr_()
 450             '2/3*a + 3/5'
 451         """
 452         x = self.polynomial()
 453         K = self.number_field()
 454         return str(x).replace(x.parent().variable_name(), K.variable_name())
 455 
 456     def _im_gens_(self, codomain, im_gens):
 457         """
 458         This is used in computing homomorphisms between number fields.
 459         
 460         EXAMPLES::
 461         
 462             sage: k.<a> = NumberField(x^2 - 2)
 463             sage: m.<b> = NumberField(x^4 - 2)
 464             sage: phi = k.hom([b^2])
 465             sage: phi(a+1)
 466             b^2 + 1
 467             sage: (a+1)._im_gens_(m, [b^2])
 468             b^2 + 1
 469         """
 470         # NOTE -- if you ever want to change this so relative number
 471         # fields are in terms of a root of a poly.  The issue is that
 472         # elements of a relative number field are represented in terms
 473         # of a generator for the absolute field.  However the morphism
 474         # gives the image of gen, which need not be a generator for
 475         # the absolute field.  The morphism has to be *over* the
 476         # relative element.
 477         return codomain(self.polynomial()(im_gens[0]))
 478 
 479     def _latex_(self):
 480         """
 481         Returns the latex representation for this element.
 482         
 483         EXAMPLES::
 484         
 485             sage: C,zeta12=CyclotomicField(12).objgen()
 486             sage: latex(zeta12^4-zeta12) # indirect doctest
 487             \zeta_{12}^{2} - \zeta_{12} - 1
 488         """
 489         return self.polynomial()._latex_(name=self.number_field().latex_variable_name())
 490 
 491     def _gap_init_(self):
 492         """
 493         Return gap string representation of self.
 494         
 495         EXAMPLES::
 496         
 497             sage: F=CyclotomicField(8)
 498             sage: p=F.gen()^2+2*F.gen()-3
 499             sage: p
 500             zeta8^2 + 2*zeta8 - 3
 501             sage: p._gap_init_() # The variable name $sage2 belongs to the gap(F) and is somehow random
 502             'GeneratorsOfField($sage2)[1]^2 + 2*GeneratorsOfField($sage2)[1] - 3'
 503             sage: gap(p._gap_init_())
 504             zeta8^2+2*zeta8-3
 505         """
 506         s = self._repr_()
 507         return s.replace(str(self.parent().gen()), 'GeneratorsOfField(%s)[1]'%sage.interfaces.gap.gap(self.parent()).name())
 508 
 509 
 510     def _pari_(self, var='x'):
 511         r"""
 512         Convert self to a Pari element.
 513         
 514         EXAMPLE::
 515         
 516             sage: K.<a> = NumberField(x^3 + 2)
 517             sage: (a + 2)._pari_()
 518             Mod(x + 2, x^3 + 2)
 519             sage: L.<b> = K.extension(x^2 + 2)
 520             sage: (b + a)._pari_()
 521             Mod(24/101*x^5 - 9/101*x^4 + 160/101*x^3 - 156/101*x^2 + 397/101*x + 364/101, x^6 + 6*x^4 - 4*x^3 + 12*x^2 + 24*x + 12)
 522         """
 523         raise NotImplementedError, "NumberFieldElement sub-classes must override _pari_"
 524 
 525     def _pari_init_(self, var='x'):
 526         """
 527         Return PARI/GP string representation of self. This is used for
 528         converting this number field element to PARI/GP. The returned
 529         string defines a pari Mod in the variable is var, which is by
 530         default 'x' - not the name of the generator of the number field.
 531         
 532         INPUT:
 533         
 534         
 535         -  ``var`` - (default: 'x') the variable of the pari
 536            Mod.
 537         
 538         
 539         EXAMPLES::
 540         
 541             sage: K.<a> = NumberField(x^5 - x - 1)
 542             sage: ((1 + 1/3*a)^4)._pari_init_()
 543             'Mod(1/81*x^4 + 4/27*x^3 + 2/3*x^2 + 4/3*x + 1, x^5 - x - 1)'
 544             sage: ((1 + 1/3*a)^4)._pari_init_('a')
 545             'Mod(1/81*a^4 + 4/27*a^3 + 2/3*a^2 + 4/3*a + 1, a^5 - a - 1)'
 546         
 547         Note that _pari_init_ can fail because of reserved words in
 548         PARI, and since it actually works by obtaining the PARI
 549         representation of something::
 550         
 551             sage: K.<theta> = NumberField(x^5 - x - 1)
 552             sage: b = (1/2 - 2/3*theta)^3; b
 553             -8/27*theta^3 + 2/3*theta^2 - 1/2*theta + 1/8
 554             sage: b._pari_init_('theta')
 555             Traceback (most recent call last):
 556             ...
 557             PariError:  (26)
 558         
 559         Fortunately pari_init returns everything in terms of x by
 560         default::
 561         
 562             sage: pari(b)
 563             Mod(-8/27*x^3 + 2/3*x^2 - 1/2*x + 1/8, x^5 - x - 1)
 564         """
 565         return repr(self._pari_(var=var))
 566 
 567     def __getitem__(self, n):
 568         """
 569         Return the n-th coefficient of this number field element, written
 570         as a polynomial in the generator.
 571         
 572         Note that `n` must be between 0 and `d-1`, where
 573         `d` is the degree of the number field.
 574         
 575         EXAMPLES::
 576         
 577             sage: m.<b> = NumberField(x^4 - 1789)
 578             sage: c = (2/3-4/5*b)^3; c
 579             -64/125*b^3 + 32/25*b^2 - 16/15*b + 8/27
 580             sage: c[0]
 581             8/27
 582             sage: c[2]
 583             32/25
 584             sage: c[3]
 585             -64/125
 586         
 587         We illustrate bounds checking::
 588         
 589             sage: c[-1]
 590             Traceback (most recent call last):
 591             ...
 592             IndexError: index must be between 0 and degree minus 1.
 593             sage: c[4]
 594             Traceback (most recent call last):
 595             ...
 596             IndexError: index must be between 0 and degree minus 1.
 597         
 598         The list method implicitly calls ``__getitem__``::
 599         
 600             sage: list(c)
 601             [8/27, -16/15, 32/25, -64/125]
 602             sage: m(list(c)) == c
 603             True
 604         """
 605         if n < 0 or n >= self.number_field().degree():     # make this faster. 
 606             raise IndexError, "index must be between 0 and degree minus 1."
 607         return self.polynomial()[n]
 608 
 609     def __richcmp__(left, right, int op):
 610         r"""
 611         EXAMPLE::
 612         
 613             sage: K.<a> = NumberField(x^3 - 3*x + 8)
 614             sage: a  + 1 > a # indirect doctest
 615             True
 616             sage: a + 1 < a # indirect doctest
 617             False
 618         """
 619         return (<Element>left)._richcmp(right, op)
 620 
 621     cdef int _cmp_c_impl(left, sage.structure.element.Element right) except -2:
 622         cdef NumberFieldElement _right = right
 623         return not (ZZX_equal(left.__numerator, _right.__numerator) and ZZ_equal(left.__denominator, _right.__denominator))
 624 
 625     def _random_element(self, num_bound=None, den_bound=None, distribution=None):
 626         """
 627         Return a new random element with the same parent as self.
 628 
 629         INPUT:
 630 
 631         - ``num_bound`` - Bound for the numerator of coefficients of result
 632 
 633         - ``den_bound`` - Bound for the denominator of coefficients of result
 634 
 635         - ``distribution`` - Distribution to use for coefficients of result
 636 
 637         EXAMPLES::
 638 
 639             sage: K.<a> = NumberField(x^3-2)
 640             sage: a._random_element()
 641             -1/2*a^2 - 4
 642             sage: K.<a> = NumberField(x^2-5)
 643             sage: a._random_element()
 644             -2*a - 1
 645         """
 646         cdef NumberFieldElement elt = self._new()
 647         elt._randomize(num_bound, den_bound, distribution)
 648         return elt
 649 
 650     cdef void _randomize(self, num_bound, den_bound, distribution):
 651         cdef int i
 652         cdef Integer denom_temp = PY_NEW(Integer)
 653         cdef Integer tmp_integer = PY_NEW(Integer)
 654         cdef ZZ_c ntl_temp
 655         cdef list coeff_list
 656         cdef Rational tmp_rational
 657 
 658         # It seems like a simpler approach would be to simply generate
 659         # random integers for each coefficient of self.__numerator
 660         # and an integer for self.__denominator. However, this would
 661         # generate things with a fairly fixed shape: in particular,
 662         # we'd be very unlikely to get elements like 1/3*a^3 + 1/7,
 663         # or anything where the denominators are actually unrelated
 664         # to one another. The extra code below is to make exactly
 665         # these kinds of results possible.
 666 
 667         if den_bound == 1:
 668             # in this case, we can skip all the business with LCMs,
 669             # storing a list of rationals, etc. this gives a factor of
 670             # two or so speedup ...
 671 
 672             # set the denominator
 673             mpz_set_si(denom_temp.value, 1)
 674             denom_temp._to_ZZ(&self.__denominator)
 675             for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
 676                 tmp_integer = <Integer>(ZZ.random_element(x=num_bound,
 677                                                    distribution=distribution))
 678                 tmp_integer._to_ZZ(&ntl_temp)
 679                 ZZX_SetCoeff(self.__numerator, i, ntl_temp)
 680             
 681         else:
 682             coeff_list = []
 683             mpz_set_si(denom_temp.value, 1)
 684             tmp_integer = PY_NEW(Integer)
 685             
 686             for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
 687                 tmp_rational = <Rational>(QQ.random_element(num_bound=num_bound,
 688                                                             den_bound=den_bound,
 689                                                             distribution=distribution))
 690                 coeff_list.append(tmp_rational)
 691                 mpz_lcm(denom_temp.value, denom_temp.value,
 692                         mpq_denref(tmp_rational.value))
 693 
 694             # now denom_temp has the denominator, and we just need to
 695             # scale the numerators and set everything appropriately
 696 
 697             # first, the denominator (easy)
 698             denom_temp._to_ZZ(&self.__denominator)
 699 
 700             # now the coefficients themselves.
 701             for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
 702                 # calculate the new numerator. if our old entry is
 703                 # p/q, and the lcm is k, it's just pk/q, which we
 704                 # also know is integral -- so we can use mpz_divexact
 705                 # below
 706                 tmp_rational = <Rational>(coeff_list[i])
 707                 mpz_mul(tmp_integer.value, mpq_numref(tmp_rational.value),
 708                         denom_temp.value)
 709                 mpz_divexact(tmp_integer.value, tmp_integer.value,
 710                              mpq_denref(tmp_rational.value))
 711                 
 712                 # now set the coefficient of self
 713                 tmp_integer._to_ZZ(&ntl_temp)
 714                 ZZX_SetCoeff(self.__numerator, i, ntl_temp)
 715 
 716     def __abs__(self):
 717         r"""
 718         Return the numerical absolute value of this number field element
 719         with respect to the first archimedean embedding, to double
 720         precision.
 721         
 722         This is the ``abs( )`` Python function. If you want a
 723         different embedding or precision, use
 724         ``self.abs(...)``.
 725         
 726         EXAMPLES::
 727         
 728             sage: k.<a> = NumberField(x^3 - 2)
 729             sage: abs(a)
 730             1.25992104989487
 731             sage: abs(a)^3
 732             2.00000000000000
 733             sage: a.abs(prec=128)
 734             1.2599210498948731647672106072782283506
 735         """
 736         return self.abs(prec=53, i=0)
 737 
 738     def abs(self, prec=53, i=0):
 739         r"""
 740         Return the absolute value of this element with respect to the
 741         `i`-th complex embedding of parent, to the given precision.
 742         
 743         If prec is 53 (the default), then the complex double field is
 744         used; otherwise the arbitrary precision (but slow) complex
 745         field is used.
 746         
 747         INPUT:
 748         
 749         
 750         -  ``prec`` - (default: 53) integer bits of precision
 751         
 752         -  ``i`` - (default: ) integer, which embedding to
 753            use
 754         
 755         
 756         EXAMPLES::
 757         
 758             sage: z = CyclotomicField(7).gen()
 759             sage: abs(z)
 760             1.00000000000000
 761             sage: abs(z^2 + 17*z - 3)
 762             16.0604426799931
 763             sage: K.<a> = NumberField(x^3+17)
 764             sage: abs(a)
 765             2.57128159065824
 766             sage: a.abs(prec=100)
 767             2.5712815906582353554531872087
 768             sage: a.abs(prec=100,i=1)
 769             2.5712815906582353554531872087
 770             sage: a.abs(100, 2)
 771             2.5712815906582353554531872087
 772         
 773         Here's one where the absolute value depends on the embedding.
 774         
 775         ::
 776         
 777             sage: K.<b> = NumberField(x^2-2)
 778             sage: a = 1 + b
 779             sage: a.abs(i=0)
 780             0.414213562373095
 781             sage: a.abs(i=1)
 782             2.41421356237309
 783         """
 784         P = self.number_field().complex_embeddings(prec)[i]
 785         return abs(P(self))
 786 
 787     def abs_non_arch(self, P, prec=None):
 788         r"""
 789         Return the non-archimedean absolute value of this element with
 790         respect to the prime `P`, to the given precision.
 791         
 792         INPUT:
 793         
 794         -  ``P`` - a prime ideal of the parent of self
 795         
 796         - ``prec`` (int) -- desired floating point precision (default:
 797           default RealField precision).
 798 
 799         OUTPUT:
 800 
 801         (real) the non-archimedean absolute value of this element with
 802         respect to the prime `P`, to the given precision.  This is the
 803         normalised absolute value, so that the underlying prime number
 804         `p` has absolute value `1/p`.
 805 
 806         
 807         EXAMPLES::
 808 
 809             sage: K.<a> = NumberField(x^2+5)
 810             sage: [1/K(2).abs_non_arch(P) for P in K.primes_above(2)]
 811             [2.00000000000000]
 812             sage: [1/K(3).abs_non_arch(P) for P in K.primes_above(3)]
 813             [3.00000000000000, 3.00000000000000]
 814             sage: [1/K(5).abs_non_arch(P) for P in K.primes_above(5)]
 815             [5.00000000000000]
 816 
 817         A relative example::
 818 
 819             sage: L.<b> = K.extension(x^2-5)
 820             sage: [b.abs_non_arch(P) for P in L.primes_above(b)]
 821             [0.447213595499958, 0.447213595499958]
 822         """
 823         from sage.rings.real_mpfr import RealField
 824         if prec is None:
 825             R = RealField()
 826         else:
 827             R = RealField(prec)
 828 
 829         if self.is_zero():
 830             return R.zero_element()
 831         val = self.valuation(P)
 832         nP = P.residue_class_degree()*P.absolute_ramification_index()
 833         return R(P.absolute_norm()) ** (-R(val) / R(nP))
 834 
 835     def coordinates_in_terms_of_powers(self):
 836         r"""
 837         Let `\alpha` be self. Return a callable object (of type 
 838         :class:`~CoordinateFunction`) that takes any element of the 
 839         parent of self in `\QQ(\alpha)` and writes it in terms of the 
 840         powers of `\alpha`: `1, \alpha, \alpha^2, ...`.
 841         
 842         (NOT CACHED).
 843         
 844         EXAMPLES:
 845 
 846         This function allows us to write elements of a number
 847         field in terms of a different generator without having to construct
 848         a whole separate number field.
 849         
 850         ::
 851         
 852             sage: y = polygen(QQ,'y'); K.<beta> = NumberField(y^3 - 2); K
 853             Number Field in beta with defining polynomial y^3 - 2
 854             sage: alpha = beta^2 + beta + 1
 855             sage: c = alpha.coordinates_in_terms_of_powers(); c
 856             Coordinate function that writes elements in terms of the powers of beta^2 + beta + 1
 857             sage: c(beta)
 858             [-2, -3, 1]
 859             sage: c(alpha)
 860             [0, 1, 0]
 861             sage: c((1+beta)^5)
 862             [3, 3, 3]
 863             sage: c((1+beta)^10)
 864             [54, 162, 189]
 865         
 866         This function works even if self only generates a subfield of this
 867         number field.
 868         
 869         ::
 870         
 871             sage: k.<a> = NumberField(x^6 - 5)
 872             sage: alpha = a^3
 873             sage: c = alpha.coordinates_in_terms_of_powers()
 874             sage: c((2/3)*a^3 - 5/3)
 875             [-5/3, 2/3]
 876             sage: c
 877             Coordinate function that writes elements in terms of the powers of a^3
 878             sage: c(a)
 879             Traceback (most recent call last):
 880             ...
 881             ArithmeticError: vector is not in free module
 882         """
 883         K = self.number_field()
 884         V, from_V, to_V = K.absolute_vector_space()
 885         h = K(1)
 886         B = [to_V(h)]
 887         f = self.absolute_minpoly()
 888         for i in range(f.degree()-1):
 889             h *= self
 890             B.append(to_V(h))
 891         W = V.span_of_basis(B)
 892         return CoordinateFunction(self, W, to_V)
 893 
 894     def complex_embeddings(self, prec=53):
 895         """
 896         Return the images of this element in the floating point complex
 897         numbers, to the given bits of precision.
 898         
 899         INPUT:
 900         
 901         
 902         -  ``prec`` - integer (default: 53) bits of precision
 903         
 904         
 905         EXAMPLES::
 906         
 907             sage: k.<a> = NumberField(x^3 - 2)
 908             sage: a.complex_embeddings()
 909             [-0.629960524947437 - 1.09112363597172*I, -0.629960524947437 + 1.09112363597172*I, 1.25992104989487]
 910             sage: a.complex_embeddings(10)
 911             [-0.63 - 1.1*I, -0.63 + 1.1*I, 1.3]
 912             sage: a.complex_embeddings(100)
 913             [-0.62996052494743658238360530364 - 1.0911236359717214035600726142*I, -0.62996052494743658238360530364 + 1.0911236359717214035600726142*I, 1.2599210498948731647672106073]
 914         """
 915         phi = self.number_field().complex_embeddings(prec)
 916         return [f(self) for f in phi]
 917 
 918     def complex_embedding(self, prec=53, i=0):
 919         """
 920         Return the i-th embedding of self in the complex numbers, to the
 921         given precision.
 922         
 923         EXAMPLES::
 924         
 925             sage: k.<a> = NumberField(x^3 - 2)
 926             sage: a.complex_embedding()
 927             -0.629960524947437 - 1.09112363597172*I
 928             sage: a.complex_embedding(10)
 929             -0.63 - 1.1*I
 930             sage: a.complex_embedding(100)
 931             -0.62996052494743658238360530364 - 1.0911236359717214035600726142*I
 932             sage: a.complex_embedding(20, 1)
 933             -0.62996 + 1.0911*I
 934             sage: a.complex_embedding(20, 2)
 935             1.2599
 936         """
 937         return self.number_field().complex_embeddings(prec)[i](self)
 938 
 939     def _mpfr_(self, R):
 940         """
 941         EXAMPLES::
 942 
 943             sage: k.<a> = NumberField(x^2 + 1)
 944             sage: RR(a^2)
 945             -1.00000000000000
 946             sage: RR(a)
 947             Traceback (most recent call last):
 948             ...
 949             TypeError: cannot convert a to real number
 950 
 951             sage: (a^2)._mpfr_(RR)
 952             -1.00000000000000
 953         """
 954         C = R.complex_field()
 955         tres = C(self)
 956         try:
 957             return R(tres)
 958         except TypeError:
 959             raise TypeError, "cannot convert %s to real number"%(self)
 960 
 961     def __float__(self):
 962         """
 963         EXAMPLES::
 964 
 965             sage: k.<a> = NumberField(x^2 + 1)
 966             sage: float(a^2)
 967             -1.0
 968             sage: float(a)
 969             Traceback (most recent call last):
 970             ...
 971             TypeError: cannot convert a to real number
 972 
 973             sage: (a^2).__float__()
 974             -1.0
 975         """
 976         tres = CC(self)
 977         try:
 978             return float(tres)
 979         except TypeError:
 980             raise TypeError, "cannot convert %s to real number"%(self)
 981 
 982     def _complex_double_(self, CDF):
 983         """
 984         EXAMPLES::
 985 
 986             sage: k.<a> = NumberField(x^2 + 1)
 987             sage: abs(CDF(a))
 988             1.0
 989         """
 990         return CDF(CC(self))
 991 
 992     def __complex__(self):
 993         """
 994         EXAMPLES::
 995 
 996             sage: k.<a> = NumberField(x^2 + 1)
 997             sage: complex(a)
 998             1j
 999             sage: a.__complex__()
1000             1j
1001         """
1002         return complex(CC(self))
1003 
1004     def factor(self):
1005         """
1006         Return factorization of this element into prime elements and a unit.
1007 
1008         OUTPUT:
1009 
1010         (Factorization) If all the prime ideals in the support are
1011         principal, the output is a Factorization as a product of prime
1012         elements raised to appropriate powers, with an appropriate
1013         unit factor.
1014 
1015         Raise ValueError if the factorization of the
1016         ideal (self) contains a non-principal prime ideal.
1017         
1018         EXAMPLES::
1019         
1020             sage: K.<i> = NumberField(x^2+1)
1021             sage: (6*i + 6).factor()
1022             (-i) * (i + 1)^3 * 3
1023         
1024         In the following example, the class number is 2.  If a factorization
1025         in prime elements exists, we will find it::
1026         
1027             sage: K.<a> = NumberField(x^2-10)
1028             sage: factor(169*a + 531)
1029             (-6*a - 19) * (-2*a + 9) * (-3*a - 1)
1030             sage: factor(K(3))
1031             Traceback (most recent call last):
1032             ...
1033             ValueError: Non-principal ideal in factorization
1034 
1035         Factorization of 0 is not allowed::
1036 
1037             sage: K.<i> = QuadraticField(-1)
1038             sage: K(0).factor()
1039             Traceback (most recent call last):
1040             ...
1041             ArithmeticError: Factorization of 0 not defined.
1042 
1043         """
1044         if self.is_zero():
1045             raise ArithmeticError, "Factorization of 0 not defined."
1046 
1047         K = self.parent()
1048         fac = K.ideal(self).factor()
1049         # Check whether all prime ideals in `fac` are principal
1050         for P,e in fac:
1051             if not P.is_principal():
1052                 raise ValueError, "Non-principal ideal in factorization"
1053         element_fac = [(P.gens_reduced()[0],e) for P,e in fac]
1054         # Compute the product of the p^e to figure out the unit
1055         from sage.misc.all import prod
1056         element_product = prod([p**e for p,e in element_fac], K(1))
1057         from sage.structure.all import Factorization
1058         return Factorization(element_fac, unit=self/element_product)
1059 
1060     def is_totally_positive(self):
1061         """
1062         Returns True if self is positive for all real embeddings of its
1063         parent number field. We do nothing at complex places, so e.g. any
1064         element of a totally complex number field will return True.
1065         
1066         EXAMPLES::
1067         
1068             sage: F.<b> = NumberField(x^3-3*x-1)
1069             sage: b.is_totally_positive()
1070             False
1071             sage: (b^2).is_totally_positive()
1072             True
1073 
1074         TESTS:
1075         
1076         Check that the output is correct even for numbers that are
1077         very close to zero (ticket #9596)::
1078 
1079             sage: K.<sqrt2> = QuadraticField(2)
1080             sage: a = 30122754096401; b = 21300003689580
1081             sage: (a/b)^2 > 2
1082             True
1083             sage: (a/b+sqrt2).is_totally_positive()
1084             True
1085             sage: r = RealField(3020)(2).sqrt()*2^3000
1086             sage: a = floor(r)/2^3000
1087             sage: b = ceil(r)/2^3000
1088             sage: (a+sqrt2).is_totally_positive()
1089             False
1090             sage: (b+sqrt2).is_totally_positive()
1091             True
1092 
1093         Check that 0 is handled correctly::
1094 
1095             sage: K.<a> = NumberField(x^5+4*x+1)
1096             sage: K(0).is_totally_positive()
1097             False
1098         """
1099         for v in self.number_field().embeddings(sage.rings.qqbar.AA):
1100             if v(self) <= 0:
1101                 return False
1102         return True    
1103 
1104     def is_square(self, root=False):
1105         """
1106         Return True if self is a square in its parent number field and
1107         otherwise return False.
1108         
1109         INPUT:
1110         
1111         
1112         -  ``root`` - if True, also return a square root (or
1113            None if self is not a perfect square)
1114         
1115         
1116         EXAMPLES::
1117         
1118             sage: m.<b> = NumberField(x^4 - 1789)
1119             sage: b.is_square()
1120             False
1121             sage: c = (2/3*b + 5)^2; c
1122             4/9*b^2 + 20/3*b + 25
1123             sage: c.is_square()
1124             True
1125             sage: c.is_square(True)
1126             (True, 2/3*b + 5)
1127         
1128         We also test the functional notation.
1129         
1130         ::
1131         
1132             sage: is_square(c, True)
1133             (True, 2/3*b + 5)
1134             sage: is_square(c)
1135             True
1136             sage: is_square(c+1)
1137             False
1138         """
1139         v = self.sqrt(all=True)
1140         t = len(v) > 0
1141         if root:
1142             if t:
1143                 return t, v[0]
1144             else:
1145                 return False, None
1146         else:
1147             return t
1148         
1149     def sqrt(self, all=False):
1150         """
1151         Returns the square root of this number in the given number field.
1152         
1153         EXAMPLES::
1154         
1155             sage: K.<a> = NumberField(x^2 - 3)
1156             sage: K(3).sqrt()
1157             a
1158             sage: K(3).sqrt(all=True)
1159             [a, -a]
1160             sage: K(a^10).sqrt()
1161             9*a
1162             sage: K(49).sqrt()
1163             7
1164             sage: K(1+a).sqrt()
1165             Traceback (most recent call last):
1166             ...
1167             ValueError: a + 1 not a square in Number Field in a with defining polynomial x^2 - 3
1168             sage: K(0).sqrt()
1169             0
1170             sage: K((7+a)^2).sqrt(all=True)
1171             [a + 7, -a - 7]
1172         
1173         ::
1174         
1175             sage: K.<a> = CyclotomicField(7)
1176             sage: a.sqrt()  
1177             a^4
1178         
1179         ::
1180         
1181             sage: K.<a> = NumberField(x^5 - x + 1)
1182             sage: (a^4 + a^2 - 3*a + 2).sqrt()
1183             a^3 - a^2
1184         
1185         ALGORITHM: Use Pari to factor `x^2` - ``self``
1186         in K.
1187         """
1188         # For now, use pari's factoring abilities
1189         R = self.number_field()['t']
1190         f = R([-self, 0, 1])
1191         roots = f.roots()
1192         if all:
1193             return [r[0] for r in roots]
1194         elif len(roots) > 0:
1195             return roots[0][0]
1196         else:
1197             try:
1198                 # This is what integers, rationals do...
1199                 from sage.all import SR, sqrt
1200                 return sqrt(SR(self))
1201             except TypeError:
1202                 raise ValueError, "%s not a square in %s"%(self, self._parent)
1203             
1204     def nth_root(self, n, all=False):
1205         r"""
1206         Return an nth root of self in the given number field.
1207         
1208         EXAMPLES::
1209         
1210             sage: K.<a> = NumberField(x^4-7)
1211             sage: K(7).nth_root(2)
1212             a^2
1213             sage: K((a-3)^5).nth_root(5)
1214             a - 3
1215         
1216         ALGORITHM: Use Pari to factor `x^n` - ``self``
1217         in K.
1218         """
1219         R = self.number_field()['t']
1220         if not self:
1221             return [self] if all else self
1222         f = (R.gen(0) << (n-1)) - self
1223         roots = f.roots()
1224         if all:
1225             return [r[0] for r in roots]
1226         elif len(roots) > 0:
1227             return roots[0][0]
1228         else:
1229             raise ValueError, "%s not a %s-th root in %s"%(self, n, self._parent)
1230         
1231     def __pow__(base, exp, dummy):
1232         """
1233         EXAMPLES::
1234 
1235             sage: K.<sqrt2> = QuadraticField(2)
1236             sage: sqrt2^2
1237             2
1238             sage: sqrt2^5
1239             4*sqrt2
1240             sage: (1+sqrt2)^100
1241             66992092050551637663438906713182313772*sqrt2 + 94741125149636933417873079920900017937
1242             sage: (1+sqrt2)^-1
1243             sqrt2 - 1
1244 
1245         If the exponent is not integral, perform this operation in
1246         the symbolic ring::
1247             
1248             sage: sqrt2^(1/5)
1249             2^(1/10)
1250             sage: sqrt2^sqrt2
1251             2^(1/2*sqrt(2))
1252 
1253         TESTS::
1254 
1255             sage: 2^I
1256             2^I
1257         """
1258         if (PY_TYPE_CHECK(base, NumberFieldElement) and
1259             (PY_TYPE_CHECK(exp, Integer) or PY_TYPE_CHECK_EXACT(exp, int) or exp in ZZ)):
1260             return generic_power_c(base, exp, None)
1261         else:
1262             from sage.symbolic.power_helper import try_symbolic_power
1263             return try_symbolic_power(base, exp)
1264 
1265     cdef void _reduce_c_(self):
1266         """
1267         Pull out common factors from the numerator and denominator!
1268         """
1269         cdef ZZ_c gcd
1270         cdef ZZ_c t1
1271         cdef ZZX_c t2
1272         ZZX_content(t1, self.__numerator)
1273         ZZ_GCD(gcd, t1, self.__denominator)
1274         if ZZ_sign(gcd) != ZZ_sign(self.__denominator):
1275             ZZ_negate(t1, gcd)
1276             gcd = t1
1277         ZZX_div_ZZ(t2, self.__numerator, gcd)
1278         ZZ_div(t1, self.__denominator, gcd)
1279         self.__numerator = t2
1280         self.__denominator = t1
1281 
1282     cpdef ModuleElement _add_(self, ModuleElement right):
1283         r"""
1284         EXAMPLE::
1285         
1286             sage: K.<s> = QuadraticField(2)
1287             sage: s + s # indirect doctest
1288             2*s
1289             sage: s + ZZ(3) # indirect doctest
1290             s + 3
1291         """
1292         cdef NumberFieldElement x
1293         cdef NumberFieldElement _right = right
1294         x = self._new()
1295         ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1296         cdef ZZX_c t1, t2
1297         ZZX_mul_ZZ(t1, self.__numerator, _right.__denominator)
1298         ZZX_mul_ZZ(t2, _right.__numerator, self.__denominator)
1299         ZZX_add(x.__numerator, t1, t2)
1300         x._reduce_c_()
1301         return x
1302 
1303     cpdef ModuleElement _sub_(self, ModuleElement right):
1304         r"""
1305         EXAMPLES::
1306         
1307             sage: K.<a> = NumberField(x^3 + 2)
1308             sage: (a/2) - (a + 3) # indirect doctest
1309             -1/2*a - 3
1310         """
1311         cdef NumberFieldElement x
1312         cdef NumberFieldElement _right = right
1313         x = self._new()
1314         ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1315         cdef ZZX_c t1, t2
1316         ZZX_mul_ZZ(t1, self.__numerator, _right.__denominator)
1317         ZZX_mul_ZZ(t2, _right.__numerator, self.__denominator)
1318         ZZX_sub(x.__numerator, t1, t2)
1319         x._reduce_c_()
1320         return x
1321 
1322     cpdef RingElement _mul_(self, RingElement right):
1323         """
1324         Returns the product of self and other as elements of a number
1325         field.
1326         
1327         EXAMPLES::
1328         
1329             sage: C.<zeta12>=CyclotomicField(12)
1330             sage: zeta12*zeta12^11
1331             1
1332             sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
1333             sage: a^3 # indirect doctest
1334             -2/3*a - 1
1335             sage: a^3+a # indirect doctest
1336             1/3*a - 1
1337         """
1338         cdef NumberFieldElement x
1339         cdef NumberFieldElement _right = right
1340         cdef ZZX_c temp
1341         cdef ZZ_c temp1
1342         x = self._new()
1343         _sig_on
1344         # MulMod doesn't handle non-monic polynomials.
1345         # Therefore, we handle the non-monic case entirely separately.
1346 
1347         if ZZ_IsOne(ZZX_LeadCoeff(self.__fld_numerator.x)):
1348             ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1349             ZZX_MulMod(x.__numerator, self.__numerator, _right.__numerator, self.__fld_numerator.x)
1350         else:
1351             ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1352             ZZX_mul(x.__numerator, self.__numerator, _right.__numerator)
1353             if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
1354                 ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
1355                 ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
1356                 ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
1357                 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
1358                 ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
1359                 ZZ_mul(x.__denominator, x.__denominator, temp1)
1360         _sig_off
1361         x._reduce_c_()
1362         return x
1363 
1364         #NOTES: In LiDIA, they build a multiplication table for the
1365         #number field, so it's not necessary to reduce modulo the
1366         #defining polynomial every time:
1367         #     src/number_fields/algebraic_num/order.cc: compute_table
1368         # but asymptotically fast poly multiplication means it's
1369         # actually faster to *not* build a table!?! 
1370 
1371     cpdef RingElement _div_(self, RingElement right):
1372         """
1373         Returns the quotient of self and other as elements of a number
1374         field.
1375         
1376         EXAMPLES::
1377         
1378             sage: C.<I>=CyclotomicField(4)
1379             sage: 1/I # indirect doctest
1380             -I
1381             sage: I/0 # indirect doctest
1382             Traceback (most recent call last):
1383             ...
1384             ZeroDivisionError: rational division by zero
1385         
1386         ::
1387         
1388             sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
1389             sage: a/a # indirect doctest
1390             1
1391             sage: 1/a # indirect doctest
1392             -a^2 - 2/3
1393             sage: a/0 # indirect doctest
1394             Traceback (most recent call last):
1395             ...
1396             ZeroDivisionError: Number field element division by zero
1397         """
1398         cdef NumberFieldElement x
1399         cdef NumberFieldElement _right = right
1400         cdef ZZX_c inv_num
1401         cdef ZZ_c inv_den
1402         cdef ZZX_c temp
1403         cdef ZZ_c temp1
1404         if not _right:
1405             raise ZeroDivisionError, "Number field element division by zero"
1406         x = self._new()
1407         _sig_on
1408         _right._invert_c_(&inv_num, &inv_den)
1409         if ZZ_IsOne(ZZX_LeadCoeff(self.__fld_numerator.x)):
1410             ZZ_mul(x.__denominator, self.__denominator, inv_den)
1411             ZZX_MulMod(x.__numerator, self.__numerator, inv_num, self.__fld_numerator.x)
1412         else:
1413             ZZ_mul(x.__denominator, self.__denominator, inv_den)
1414             ZZX_mul(x.__numerator, self.__numerator, inv_num)
1415             if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
1416                 ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
1417                 ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
1418                 ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
1419                 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
1420                 ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
1421                 ZZ_mul(x.__denominator, x.__denominator, temp1)
1422         x._reduce_c_()
1423         _sig_off
1424         return x
1425 
1426     def __floordiv__(self, other):
1427         """
1428         Return the quotient of self and other. Since these are field
1429         elements the floor division is exactly the same as usual division.
1430         
1431         EXAMPLES::
1432         
1433             sage: m.<b> = NumberField(x^4 + x^2 + 2/3)
1434             sage: c = (1+b) // (1-b); c
1435             3/4*b^3 + 3/4*b^2 + 3/2*b + 1/2
1436             sage: (1+b) / (1-b) == c
1437             True
1438             sage: c * (1-b)
1439             b + 1
1440         """
1441         return self / other
1442 
1443     def __nonzero__(self):
1444         """
1445         Return True if this number field element is nonzero.
1446         
1447         EXAMPLES::
1448         
1449             sage: m.<b> = CyclotomicField(17)
1450             sage: m(0).__nonzero__()
1451             False
1452             sage: b.__nonzero__()
1453             True
1454         
1455         Nonzero is used by the bool command::
1456         
1457             sage: bool(b + 1)
1458             True
1459             sage: bool(m(0))
1460             False
1461         """
1462         return not IsZero_ZZX(self.__numerator)
1463 
1464     cpdef ModuleElement _neg_(self):
1465         r"""
1466         EXAMPLE::
1467         
1468             sage: K.<a> = NumberField(x^3 + 2)
1469             sage: -a # indirect doctest
1470             -a
1471         """
1472         cdef NumberFieldElement x
1473         x = self._new()
1474         ZZX_mul_long(x.__numerator, self.__numerator, -1)
1475         x.__denominator = self.__denominator
1476         return x
1477 
1478     def __copy__(self):
1479         r"""
1480         EXAMPLE::
1481         
1482             sage: K.<a> = NumberField(x^3 + 2)
1483             sage: b = copy(a)
1484             sage: b == a
1485             True
1486             sage: b is a
1487             False
1488         """
1489         cdef NumberFieldElement x
1490         x = self._new()
1491         x.__numerator = self.__numerator
1492         x.__denominator = self.__denominator
1493         return x
1494 
1495     def __int__(self):
1496         """
1497         Attempt to convert this number field element to a Python integer,
1498         if possible.
1499         
1500         EXAMPLES::
1501         
1502             sage: C.<I>=CyclotomicField(4)
1503             sage: int(1/I)
1504             Traceback (most recent call last):
1505             ...
1506             TypeError: cannot coerce nonconstant polynomial to int
1507             sage: int(I*I)
1508             -1
1509         
1510         ::
1511         
1512             sage: K.<a> = NumberField(x^10 - x - 1)
1513             sage: int(a)
1514             Traceback (most recent call last):
1515             ...
1516             TypeError: cannot coerce nonconstant polynomial to int
1517             sage: int(K(9390283))
1518             9390283
1519         
1520         The semantics are like in Python, so the value does not have to
1521         preserved.
1522         
1523         ::
1524         
1525             sage: int(K(393/29))
1526             13
1527         """
1528         return int(self.polynomial())
1529 
1530     def __long__(self):
1531         """
1532         Attempt to convert this number field element to a Python long, if
1533         possible.
1534         
1535         EXAMPLES::
1536         
1537             sage: K.<a> = NumberField(x^10 - x - 1)
1538             sage: long(a)
1539             Traceback (most recent call last):
1540             ...
1541             TypeError: cannot coerce nonconstant polynomial to long
1542             sage: long(K(1234))
1543             1234L
1544         
1545         The value does not have to be preserved, in the case of fractions.
1546         
1547         ::
1548         
1549             sage: long(K(393/29))
1550             13L
1551         """
1552         return long(self.polynomial())
1553 
1554     cdef void _invert_c_(self, ZZX_c *num, ZZ_c *den):
1555         """
1556         Computes the numerator and denominator of the multiplicative
1557         inverse of this element.
1558         
1559         Suppose that this element is x/d and the parent mod'ding polynomial
1560         is M/D. The NTL function XGCD( r, s, t, a, b ) computes r,s,t such
1561         that `r=s*a+t*b`. We compute XGCD( r, s, t, x\*D, M\*d )
1562         and set num=s\*D\*d den=r
1563         
1564         EXAMPLES:
1565 
1566         I'd love to, but since we are dealing with c-types, I
1567         can't at this level. Check __invert__ for doc-tests that rely
1568         on this functionality.
1569         """
1570         cdef ZZX_c t # unneeded except to be there
1571         cdef ZZX_c a, b
1572         ZZX_mul_ZZ( a, self.__numerator, self.__fld_denominator.x )
1573         ZZX_mul_ZZ( b, self.__fld_numerator.x, self.__denominator )
1574         ZZX_XGCD( den[0], num[0],  t, a, b, 1 )
1575         ZZX_mul_ZZ( num[0], num[0], self.__fld_denominator.x )
1576         ZZX_mul_ZZ( num[0], num[0], self.__denominator )
1577 
1578     def __invert__(self):
1579         """
1580         Returns the multiplicative inverse of self in the number field.
1581         
1582         EXAMPLES::
1583         
1584             sage: C.<I>=CyclotomicField(4)
1585             sage: ~I
1586             -I
1587             sage: (2*I).__invert__()
1588             -1/2*I
1589         """
1590         if IsZero_ZZX(self.__numerator):
1591             raise ZeroDivisionError
1592         cdef NumberFieldElement x
1593         x = self._new()
1594         self._invert_c_(&x.__numerator, &x.__denominator)
1595         x._reduce_c_()
1596         return x
1597 
1598     def _integer_(self, Z=None):
1599         """
1600         Returns an integer if this element is actually an integer.
1601         
1602         EXAMPLES::
1603         
1604             sage: C.<I>=CyclotomicField(4)
1605             sage: (~I)._integer_()
1606             Traceback (most recent call last):
1607             ...
1608             TypeError: Unable to coerce -I to an integer
1609             sage: (2*I*I)._integer_()
1610             -2
1611         """
1612         if ZZX_deg(self.__numerator) >= 1:
1613             raise TypeError, "Unable to coerce %s to an integer"%self
1614         return ZZ(self._rational_())
1615 
1616     def _rational_(self):
1617         """
1618         Returns a rational number if this element is actually a rational
1619         number.
1620         
1621         EXAMPLES::
1622         
1623             sage: C.<I>=CyclotomicField(4)
1624             sage: (~I)._rational_()
1625             Traceback (most recent call last):
1626             ...
1627             TypeError: Unable to coerce -I to a rational
1628             sage: (I*I/2)._rational_()
1629             -1/2
1630         """
1631         if ZZX_deg(self.__numerator) >= 1:
1632             raise TypeError, "Unable to coerce %s to a rational"%self
1633         cdef Integer num
1634         num = PY_NEW(Integer)
1635         ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
1636         return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1637         
1638     def _symbolic_(self, SR):
1639         """
1640         If an embedding into CC is specified, then a representation of this
1641         element can be made in the symbolic ring (assuming roots of the
1642         minimal polynomial can be found symbolically).
1643         
1644         EXAMPLES::
1645         
1646             sage: K.<a> = QuadraticField(2)
1647             sage: SR(a) # indirect doctest
1648             sqrt(2)
1649             sage: SR(3*a-5) # indirect doctest
1650             3*sqrt(2) - 5
1651             sage: K.<a> = QuadraticField(2, embedding=-1.4)
1652             sage: SR(a) # indirect doctest
1653             -sqrt(2)
1654             sage: K.<a> = NumberField(x^2 - 2)
1655             sage: SR(a) # indirect doctest
1656             Traceback (most recent call last):
1657             ...
1658             TypeError: An embedding into RR or CC must be specified.
1659         
1660         Now a more complicated example::
1661         
1662             sage: K.<a> = NumberField(x^3 + x - 1, embedding=0.68)
1663             sage: b = SR(a); b # indirect doctest
1664             1/3*(3*(1/18*sqrt(3)*sqrt(31) + 1/2)^(2/3) - 1)/(1/18*sqrt(3)*sqrt(31) + 1/2)^(1/3)
1665 
1666             sage: (b^3 + b - 1).simplify_radical()
1667             0
1668         
1669         Make sure we got the right one::
1670         
1671             sage: CC(a)
1672             0.682327803828019
1673             sage: CC(b)
1674             0.682327803828019
1675         
1676         Special case for cyclotomic fields::
1677         
1678             sage: K.<zeta> = CyclotomicField(19)
1679             sage: SR(zeta) # indirect doctest
1680             e^(2/19*I*pi)
1681             sage: CC(zeta)
1682             0.945817241700635 + 0.324699469204683*I
1683             sage: CC(SR(zeta))
1684             0.945817241700635 + 0.324699469204683*I
1685 
1686             sage: SR(zeta^5 + 2)
1687             e^(10/19*I*pi) + 2
1688         
1689         For degree greater than 5, sometimes Galois theory prevents a
1690         closed-form solution.  In this case, a numerical approximation
1691         is used::
1692         
1693             sage: K.<a> = NumberField(x^5-x+1, embedding=-1)
1694             sage: SR(a)
1695             -1.1673040153
1696         
1697         ::
1698         
1699             sage: K.<a> = NumberField(x^6-x^3-1, embedding=1)
1700             sage: SR(a)
1701             1/2*(sqrt(5) + 1)^(1/3)*2^(2/3)
1702         """
1703         if self.__symbolic is None:
1704         
1705             K = self._parent.fraction_field()
1706 
1707             gen = K.gen()
1708             if not self is gen:
1709                 try:
1710                     # share the hard work...
1711                     gen_image = gen._symbolic_(SR)
1712                     self.__symbolic = self.polynomial()(gen_image)
1713                     return self.__symbolic
1714                 except TypeError:
1715                     pass # we may still be able to do this particular element...
1716             
1717             embedding = K.specified_complex_embedding()
1718             if embedding is None:
1719                 raise TypeError, "An embedding into RR or CC must be specified."
1720             
1721             if isinstance(K, number_field.NumberField_cyclotomic):
1722                 # solution by radicals may be difficult, but we have a closed form
1723                 from sage.all import exp, I, pi, ComplexField, RR
1724                 CC = ComplexField(53)
1725                 two_pi_i = 2 * pi * I
1726                 k = ( K._n()*CC(K.gen()).log() / CC(two_pi_i) ).real().round() # n ln z / (2 pi i)
1727                 gen_image = exp(k*two_pi_i/K._n())
1728                 if self is gen:
1729                     self.__symbolic = gen_image
1730                 else:
1731                     self.__symbolic = self.polynomial()(gen_image)
1732             else:
1733                 # try to solve the minpoly and choose the closest root
1734                 poly = self.minpoly()
1735                 roots = []
1736                 var = SR(poly.variable_name())
1737                 for soln in SR(poly).solve(var, to_poly_solve=True):
1738                     if soln.lhs() == var:
1739                         roots.append(soln.rhs())
1740                 if len(roots) != poly.degree():
1741                     raise TypeError, "Unable to solve by radicals."
1742                 from number_field_morphisms import matching_root
1743                 from sage.rings.complex_field import ComplexField
1744                 gen_image = matching_root(roots, self, ambient_field=ComplexField(53), margin=2)
1745                 if gen_image is not None:
1746                     self.__symbolic = gen_image
1747                 else:
1748                     # should be rare, e.g. if there is insufficient precision
1749                     raise TypeError, "Unable to determine which root in SR is this element."
1750                     
1751         return self.__symbolic
1752             
1753     def galois_conjugates(self, K):
1754         r"""
1755         Return all Gal(Qbar/Q)-conjugates of this number field element in
1756         the field K.
1757         
1758         EXAMPLES:
1759 
1760         In the first example the conjugates are obvious::
1761         
1762             sage: K.<a> = NumberField(x^2 - 2)
1763             sage: a.galois_conjugates(K)
1764             [a, -a]
1765             sage: K(3).galois_conjugates(K)
1766             [3]
1767         
1768         In this example the field is not Galois, so we have to pass to an
1769         extension to obtain the Galois conjugates.
1770         
1771         ::
1772         
1773             sage: K.<a> = NumberField(x^3 - 2)
1774             sage: c = a.galois_conjugates(K); c
1775             [a]
1776             sage: K.<a> = NumberField(x^3 - 2)
1777             sage: c = a.galois_conjugates(K.galois_closure('a1')); c
1778             [1/84*a1^4 + 13/42*a1, -1/252*a1^4 - 55/126*a1, -1/126*a1^4 + 8/63*a1]
1779             sage: c[0]^3
1780             2
1781             sage: parent(c[0])
1782             Number Field in a1 with defining polynomial x^6 + 40*x^3 + 1372
1783             sage: parent(c[0]).is_galois()
1784             True
1785         
1786         There is only one Galois conjugate of `\sqrt[3]{2}` in
1787         `\QQ(\sqrt[3]{2})`.
1788         
1789         ::
1790         
1791             sage: a.galois_conjugates(K)
1792             [a]
1793         
1794         Galois conjugates of `\sqrt[3]{2}` in the field
1795         `\QQ(\zeta_3,\sqrt[3]{2})`::
1796         
1797             sage: L.<a> = CyclotomicField(3).extension(x^3 - 2)
1798             sage: a.galois_conjugates(L)
1799             [a, (-zeta3 - 1)*a, zeta3*a]
1800         """
1801         f = self.absolute_minpoly()
1802         g = K['x'](f)
1803         return [a for a,_ in g.roots()]
1804 
1805     def conjugate(self):
1806         """
1807         Return the complex conjugate of the number field element.
1808         Currently, this is implemented for cyclotomic fields and quadratic
1809         extensions of Q. It seems likely that there are other number fields
1810         for which the idea of a conjugate would be easy to compute.
1811         
1812         EXAMPLES::
1813         
1814             sage: k.<I> = QuadraticField(-1)
1815             sage: I.conjugate()
1816             -I
1817             sage: (I/(1+I)).conjugate()
1818             -1/2*I + 1/2
1819             sage: z6=CyclotomicField(6).gen(0)
1820             sage: (2*z6).conjugate()
1821             -2*zeta6 + 2
1822             sage: K.<j,b> = QQ[sqrt(-1), sqrt(2)]
1823             sage: j.conjugate()
1824             Traceback (most recent call last):
1825             ...
1826             NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
1827         
1828         ::
1829         
1830             sage: K.<b> = NumberField(x^3 - 2)
1831             sage: b.conjugate()
1832             Traceback (most recent call last):
1833             ...
1834             NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
1835         """
1836         coeffs = self.number_field().absolute_polynomial().list()
1837         if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
1838             # polynomial looks like x^2+d
1839             # i.e. we live in a quadratic extension of QQ
1840             if coeffs[0] > 0:
1841                 gen = self.number_field().gen()
1842                 return self.polynomial()(-gen)
1843             else:
1844                 return self
1845         elif isinstance(self.number_field(), number_field.NumberField_cyclotomic):
1846             # We are in a cyclotomic field
1847             # Replace the generator zeta_n with (zeta_n)^(n-1)
1848             gen = self.number_field().gen()
1849             return self.polynomial()(gen ** (gen.multiplicative_order()-1))
1850         else:
1851             raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
1852 
1853     def polynomial(self, var='x'):
1854         """
1855         Return the underlying polynomial corresponding to this number field
1856         element.
1857         
1858         The resulting polynomial is currently *not* cached.
1859         
1860         EXAMPLES::
1861         
1862             sage: K.<a> = NumberField(x^5 - x - 1)
1863             sage: f = (-2/3 + 1/3*a)^4; f
1864             1/81*a^4 - 8/81*a^3 + 8/27*a^2 - 32/81*a + 16/81
1865             sage: g = f.polynomial(); g
1866             1/81*x^4 - 8/81*x^3 + 8/27*x^2 - 32/81*x + 16/81
1867             sage: parent(g)
1868             Univariate Polynomial Ring in x over Rational Field
1869         
1870         Note that the result of this function is not cached (should this be
1871         changed?)::
1872         
1873             sage: g is f.polynomial() 
1874             False
1875         """
1876         return QQ[var](self._coefficients())
1877 
1878     def __hash__(self):
1879         """
1880         Return hash of this number field element, which is just the
1881         hash of the underlying polynomial.
1882         
1883         EXAMPLE::
1884         
1885             sage: K.<b> = NumberField(x^3 - 2)
1886             sage: hash(b^2 + 1) == hash((b^2 + 1).polynomial()) # indirect doctest
1887             True
1888         """
1889         return hash(self.polynomial())
1890 
1891     def _coefficients(self):
1892         """
1893         Return the coefficients of the underlying polynomial corresponding
1894         to this number field element.
1895         
1896         OUTPUT:
1897 
1898         - a list whose length corresponding to the degree of this
1899           element written in terms of a generator.
1900         
1901         EXAMPLES:
1902         
1903             sage: K.<b> = NumberField(x^3 - 2)
1904             sage: (b^2 + 1)._coefficients()
1905             [1, 0, 1]
1906         """
1907         coeffs = []
1908         cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1909         cdef Integer numCoeff
1910         cdef int i
1911         for i from 0 <= i <= ZZX_deg(self.__numerator):
1912             numCoeff = PY_NEW(Integer)
1913             ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
1914             coeffs.append( numCoeff / den )
1915         return coeffs
1916         
1917     cdef void _ntl_coeff_as_mpz(self, mpz_t* z, long i):
1918         if i > ZZX_deg(self.__numerator):
1919             mpz_set_ui(z[0], 0)
1920         else:
1921             ZZX_getitem_as_mpz(z, &self.__numerator, i)
1922         
1923     cdef void _ntl_denom_as_mpz(self, mpz_t* z):
1924         cdef Integer denom = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1925         mpz_set(z[0], denom.value)
1926 
1927     def denominator(self):
1928         """
1929         Return the denominator of this element, which is by definition the
1930         denominator of the corresponding polynomial representation. I.e.,
1931         elements of number fields are represented as a polynomial (in
1932         reduced form) modulo the modulus of the number field, and the
1933         denominator is the denominator of this polynomial.
1934         
1935         EXAMPLES::
1936         
1937             sage: K.<z> = CyclotomicField(3)
1938             sage: a = 1/3 + (1/5)*z
1939             sage: print a.denominator()
1940             15
1941         """
1942         return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1943 
1944     def _set_multiplicative_order(self, n):
1945         """
1946         Set the multiplicative order of this number field element.
1947         
1948         .. warning::
1949 
1950            Use with caution - only for internal use! End users should
1951            never call this unless they have a very good reason to do
1952            so.
1953         
1954         EXAMPLES::
1955         
1956             sage: K.<a> = NumberField(x^2 + x + 1)
1957             sage: a._set_multiplicative_order(3)
1958             sage: a.multiplicative_order()
1959             3
1960         
1961         You can be evil with this so be careful. That's why the function
1962         name begins with an underscore.
1963         
1964         ::
1965         
1966             sage: a._set_multiplicative_order(389)
1967             sage: a.multiplicative_order()
1968             389
1969         """
1970         self.__multiplicative_order = n
1971 
1972     def multiplicative_order(self):
1973         """
1974         Return the multiplicative order of this number field element.
1975         
1976         EXAMPLES::
1977         
1978             sage: K.<z> = CyclotomicField(5)
1979             sage: z.multiplicative_order()
1980             5
1981             sage: (-z).multiplicative_order()
1982             10
1983             sage: (1+z).multiplicative_order()
1984             +Infinity
1985 
1986             sage: x = polygen(QQ)
1987             sage: K.<a>=NumberField(x^40 - x^20 + 4)
1988             sage: u = 1/4*a^30 + 1/4*a^10 + 1/2
1989             sage: u.multiplicative_order()
1990             6
1991             sage: a.multiplicative_order()
1992             +Infinity
1993 
1994         An example in a relative extension::
1995     
1996             sage: K.<a, b> = NumberField([x^2 + x + 1, x^2 - 3])
1997             sage: z = (a - 1)*b/3
1998             sage: z.multiplicative_order()
1999             12
2000             sage: z^12==1 and z^6!=1 and z^4!=1
2001             True
2002 
2003         """
2004         if self.__multiplicative_order is not None:
2005             return self.__multiplicative_order
2006 
2007         one = self.number_field().one_element()
2008         infinity = sage.rings.infinity.infinity
2009 
2010         if self == one:
2011             self.__multiplicative_order = ZZ(1)
2012             return self.__multiplicative_order
2013         if self == -one:
2014             self.__multiplicative_order = ZZ(2)
2015             return self.__multiplicative_order
2016             
2017         if isinstance(self.number_field(), number_field.NumberField_cyclotomic):
2018             t = self.number_field()._multiplicative_order_table()
2019             f = self.polynomial()
2020             if t.has_key(f):
2021                 self.__multiplicative_order = t[f]
2022                 return self.__multiplicative_order
2023             else:
2024                 self.__multiplicative_order = sage.rings.infinity.infinity
2025                 return self.__multiplicative_order
2026 
2027         if self.is_rational_c() or not self.is_integral() or not self.norm() ==1:
2028             self.__multiplicative_order = infinity
2029             return self.__multiplicative_order
2030 
2031         # Now we have a unit of norm 1, and check if it is a root of unity
2032 
2033         n = self.number_field().zeta_order()
2034         if not self**n ==1:
2035             self.__multiplicative_order = infinity
2036             return self.__multiplicative_order
2037         from sage.groups.generic import order_from_multiple
2038         self.__multiplicative_order = order_from_multiple(self,n,operation='*')
2039         return self.__multiplicative_order
2040 
2041     def additive_order(self):
2042         r"""
2043         Return the additive order of this element (i.e. infinity if
2044         self != 0, 1 if self == 0)
2045         
2046         EXAMPLES::
2047         
2048             sage: K.<u> = NumberField(x^4 - 3*x^2 + 3)
2049             sage: u.additive_order()
2050             +Infinity
2051             sage: K(0).additive_order()
2052             1
2053             sage: K.ring_of_integers().characteristic() # implicit doctest
2054             0
2055         """
2056         if self == 0: return 1
2057         else: return sage.rings.infinity.infinity
2058 
2059     cdef bint is_rational_c(self):
2060         return ZZX_deg(self.__numerator) == 0
2061                 
2062     def trace(self, K=None):
2063         """
2064         Return the absolute or relative trace of this number field
2065         element.
2066         
2067         If K is given then K must be a subfield of the parent L of self, in
2068         which case the trace is the relative trace from L to K. In all
2069         other cases, the trace is the absolute trace down to QQ.
2070         
2071         EXAMPLES::
2072         
2073             sage: K.<a> = NumberField(x^3 -132/7*x^2 + x + 1); K
2074             Number Field in a with defining polynomial x^3 - 132/7*x^2 + x + 1
2075             sage: a.trace()
2076             132/7
2077             sage: (a+1).trace() == a.trace() + 3
2078             True
2079         
2080         If we are in an order, the trace is an integer::
2081         
2082             sage: K.<zeta> = CyclotomicField(17)
2083             sage: R = K.ring_of_integers()
2084             sage: R(zeta).trace().parent()
2085             Integer Ring
2086         
2087         TESTS::
2088         
2089             sage: F.<z> = CyclotomicField(5) ; t = 3*z**3 + 4*z**2 + 2
2090             sage: t.trace(F)
2091             3*z^3 + 4*z^2 + 2
2092         """
2093         if K is None:
2094             trace = self._pari_('x').trace()
2095             return QQ(trace) if self._parent.is_field() else ZZ(trace)
2096         return self.matrix(K).trace()
2097 
2098     def norm(self, K=None):
2099         """
2100         Return the absolute or relative norm of this number field element.
2101         
2102         If K is given then K must be a subfield of the parent L of self, in
2103         which case the norm is the relative norm from L to K. In all other
2104         cases, the norm is the absolute norm down to QQ.
2105         
2106         EXAMPLES::
2107         
2108             sage: K.<a> = NumberField(x^3 + x^2 + x - 132/7); K
2109             Number Field in a with defining polynomial x^3 + x^2 + x - 132/7
2110             sage: a.norm()
2111             132/7
2112             sage: factor(a.norm())
2113             2^2 * 3 * 7^-1 * 11
2114             sage: K(0).norm()
2115             0
2116         
2117         Some complicated relatives norms in a tower of number fields.
2118         
2119         ::
2120         
2121             sage: K.<a,b,c> = NumberField([x^2 + 1, x^2 + 3, x^2 + 5])
2122             sage: L = K.base_field(); M = L.base_field()
2123             sage: a.norm()
2124             1
2125             sage: a.norm(L)
2126             1
2127             sage: a.norm(M)
2128             1
2129             sage: a
2130             a
2131             sage: (a+b+c).norm()
2132             121
2133             sage: (a+b+c).norm(L)
2134             2*c*b - 7
2135             sage: (a+b+c).norm(M)
2136             -11
2137         
2138         We illustrate that norm is compatible with towers::
2139         
2140             sage: z = (a+b+c).norm(L); z.norm(M)
2141             -11
2142         
2143         If we are in an order, the norm is an integer::
2144         
2145             sage: K.<a> = NumberField(x^3-2)
2146             sage: a.norm().parent()
2147             Rational Field
2148             sage: R = K.ring_of_integers()
2149             sage: R(a).norm().parent()
2150             Integer Ring
2151         
2152         TESTS::
2153         
2154             sage: F.<z> = CyclotomicField(5)
2155             sage: t = 3*z**3 + 4*z**2 + 2
2156             sage: t.norm(F)
2157             3*z^3 + 4*z^2 + 2
2158         """
2159         if K is None:
2160             norm = self._pari_('x').norm()
2161             return QQ(norm) if self._parent.is_field() else ZZ(norm)
2162         return self.matrix(K).determinant()
2163 
2164     def vector(self):
2165         """
2166         Return vector representation of self in terms of the basis for the
2167         ambient number field.
2168         
2169         EXAMPLES::
2170         
2171             sage: K.<a> = NumberField(x^2 + 1)
2172             sage: (2/3*a - 5/6).vector()
2173             (-5/6, 2/3)
2174             sage: (-5/6, 2/3)
2175             (-5/6, 2/3)
2176             sage: O = K.order(2*a)
2177             sage: (O.1).vector()
2178             (0, 2)
2179             sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
2180             sage: (a + b).vector()
2181             (b, 1)
2182             sage: O = K.order([a,b])
2183             sage: (O.1).vector()
2184             (-b, 1)
2185             sage: (O.2).vector()
2186             (1, -b)
2187         """
2188         return self.number_field().relative_vector_space()[2](self)
2189 
2190     def charpoly(self, var='x'):
2191         r"""
2192         Return the characteristic polynomial of this number field element.
2193         
2194         EXAMPLE::
2195         
2196             sage: K.<a> = NumberField(x^3 + 7)
2197             sage: a.charpoly()
2198             x^3 + 7
2199             sage: K(1).charpoly()
2200             x^3 - 3*x^2 + 3*x - 1
2201         """
2202         raise NotImplementedError, "Subclasses of NumberFieldElement must override charpoly()"
2203 
2204     def minpoly(self, var='x'):
2205         """
2206         Return the minimal polynomial of this number field element.
2207         
2208         EXAMPLES::
2209         
2210             sage: K.<a> = NumberField(x^2+3)
2211             sage: a.minpoly('x')
2212             x^2 + 3
2213             sage: R.<X> = K['X']
2214             sage: L.<b> = K.extension(X^2-(22 + a))
2215             sage: b.minpoly('t')
2216             t^2 - a - 22
2217             sage: b.absolute_minpoly('t')
2218             t^4 - 44*t^2 + 487
2219             sage: b^2 - (22+a)
2220             0
2221         """
2222         return self.charpoly(var).radical() # square free part of charpoly
2223 
2224     def is_integral(self):
2225         r"""
2226         Determine if a number is in the ring of integers of this number
2227         field.
2228         
2229         EXAMPLES::
2230         
2231             sage: K.<a> = NumberField(x^2 + 23)
2232             sage: a.is_integral()
2233             True
2234             sage: t = (1+a)/2
2235             sage: t.is_integral()
2236             True
2237             sage: t.minpoly()
2238             x^2 - x + 6
2239             sage: t = a/2
2240             sage: t.is_integral()
2241             False
2242             sage: t.minpoly()
2243             x^2 + 23/4
2244         
2245         An example in a relative extension::
2246         
2247             sage: K.<a,b> = NumberField([x^2+1, x^2+3])
2248             sage: (a+b).is_integral()
2249             True
2250             sage: ((a-b)/2).is_integral()
2251             False
2252         """
2253         return all([a in ZZ for a in self.absolute_minpoly()])
2254 
2255     def matrix(self, base=None):
2256         r"""
2257         If base is None, return the matrix of right multiplication by the
2258         element on the power basis `1, x, x^2, \ldots, x^{d-1}` for
2259         the number field. Thus the *rows* of this matrix give the images of
2260         each of the `x^i`.
2261         
2262         If base is not None, then base must be either a field that embeds
2263         in the parent of self or a morphism to the parent of self, in which
2264         case this function returns the matrix of multiplication by self on
2265         the power basis, where we view the parent field as a field over
2266         base.
2267         
2268         INPUT:
2269         
2270         
2271         -  ``base`` - field or morphism
2272         
2273         
2274         EXAMPLES:
2275 
2276         Regular number field::
2277         
2278             sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
2279             sage: M = a.matrix(); M
2280             [0 1 0]
2281             [0 0 1]
2282             [5 0 0]
2283             sage: M.base_ring() is QQ
2284             True
2285         
2286         Relative number field::
2287         
2288             sage: L.<b> = K.extension(K['x'].0^2 - 2)
2289             sage: M = b.matrix(); M
2290             [0 1]
2291             [2 0]
2292             sage: M.base_ring() is K
2293             True
2294         
2295         Absolute number field::
2296         
2297             sage: M = L.absolute_field('c').gen().matrix(); M
2298             [  0   1   0   0   0   0]
2299             [  0   0   1   0   0   0]
2300             [  0   0   0   1   0   0]
2301             [  0   0   0   0   1   0]
2302             [  0   0   0   0   0   1]
2303             [-17 -60 -12 -10   6   0]
2304             sage: M.base_ring() is QQ
2305             True
2306         
2307         More complicated relative number field::
2308         
2309             sage: L.<b> = K.extension(K['x'].0^2 - a); L
2310             Number Field in b with defining polynomial x^2 - a over its base field
2311             sage: M = b.matrix(); M
2312             [0 1]
2313             [a 0]
2314             sage: M.base_ring() is K
2315             True
2316         
2317         An example where we explicitly give the subfield or the embedding::
2318         
2319             sage: K.<a> = NumberField(x^4 + 1); L.<a2> = NumberField(x^2 + 1)
2320             sage: a.matrix(L)
2321             [ 0  1]
2322             [a2  0]
2323         
2324         Notice that if we compute all embeddings and choose a different
2325         one, then the matrix is changed as it should be::
2326         
2327             sage: v = L.embeddings(K)
2328             sage: a.matrix(v[1])
2329             [  0   1]
2330             [-a2   0]
2331         
2332         The norm is also changed::
2333         
2334             sage: a.norm(v[1])
2335             a2
2336             sage: a.norm(v[0])
2337             -a2
2338         
2339         TESTS::
2340         
2341             sage: F.<z> = CyclotomicField(5) ; t = 3*z**3 + 4*z**2 + 2
2342             sage: t.matrix(F)
2343             [3*z^3 + 4*z^2 + 2]
2344         """
2345         if base is not None:
2346             if number_field.is_NumberField(base):
2347                 return self._matrix_over_base(base)
2348             else:
2349                 return self._matrix_over_base_morphism(base)
2350         # Multiply each power of field generator on
2351         # the left by this element; make matrix
2352         # whose rows are the coefficients of the result,
2353         # and transpose.
2354         if self.__matrix is None:
2355             K = self.number_field()
2356             v = []
2357             x = K.gen()
2358             a = K(1)
2359             d = K.relative_degree()
2360             for n in range(d):
2361                 v += (a*self).list()
2362                 a *= x
2363             k = K.base_ring()
2364             import sage.matrix.matrix_space
2365             M = sage.matrix.matrix_space.MatrixSpace(k, d)
2366             self.__matrix = M(v)
2367         return self.__matrix
2368 
2369     def valuation(self, P):
2370         """
2371         Returns the valuation of self at a given prime ideal P.
2372         
2373         INPUT:
2374         
2375         
2376         -  ``P`` - a prime ideal of the parent of self
2377         
2378         
2379         EXAMPLES::
2380         
2381             sage: R.<x> = QQ[]
2382             sage: K.<a> = NumberField(x^4+3*x^2-17)
2383             sage: P = K.ideal(61).factor()[0][0]
2384             sage: b = a^2 + 30
2385             sage: b.valuation(P)
2386             1
2387             sage: type(b.valuation(P))
2388             <type 'sage.rings.integer.Integer'>
2389 
2390         The function can be applied to elements in relative number fields::
2391 
2392             sage: L.<b> = K.extension(x^2 - 3)
2393             sage: [L(6).valuation(P) for P in L.primes_above(2)]
2394             [4]
2395             sage: [L(6).valuation(P) for P in L.primes_above(3)]
2396             [2, 2]
2397         """
2398         from number_field_ideal import is_NumberFieldIdeal
2399         from sage.rings.infinity import infinity
2400         if not is_NumberFieldIdeal(P):
2401             if is_NumberFieldElement(P):
2402                 P = self.number_field().fractional_ideal(P)
2403             else:
2404                 raise TypeError, "P must be an ideal"
2405         if not P.is_prime():
2406             # We always check this because it caches the pari prime representation of this ideal.
2407             raise ValueError, "P must be prime"
2408         if self == 0:
2409             return infinity
2410         return Integer_sage(self.number_field()._pari_().elementval(self._pari_(), P._pari_prime))
2411 
2412     def local_height(self, P, prec=None, weighted=False):
2413         r"""
2414         Returns the local height of self at a given prime ideal `P`.
2415         
2416         INPUT:
2417         
2418         
2419         -  ``P`` - a prime ideal of the parent of self
2420         
2421         - ``prec`` (int) -- desired floating point precision (defult:
2422           default RealField precision).
2423 
2424         - ``weighted`` (bool, default False) -- if True, apply local
2425           degree weighting.
2426 
2427         OUTPUT:
2428 
2429         (real) The local height of this number field element at the
2430         place `P`.  If ``weighted`` is True, this is multiplied by the
2431         local degree (as required for global heights).
2432         
2433         EXAMPLES::
2434         
2435             sage: R.<x> = QQ[]
2436             sage: K.<a> = NumberField(x^4+3*x^2-17)
2437             sage: P = K.ideal(61).factor()[0][0]
2438             sage: b = 1/(a^2 + 30)
2439             sage: b.local_height(P)
2440             4.11087386417331
2441             sage: b.local_height(P, weighted=True)
2442             8.22174772834662
2443             sage: b.local_height(P, 200)
2444             4.1108738641733112487513891034256147463156817430812610629374
2445             sage: (b^2).local_height(P)
2446             8.22174772834662
2447             sage: (b^-1).local_height(P)
2448             0.000000000000000
2449 
2450         A relative example::
2451 
2452             sage: PK.<y> = K[]
2453             sage: L.<c> = NumberField(y^2 + a)
2454             sage: L(1/4).local_height(L.ideal(2, c-a+1))
2455             1.38629436111989
2456         """
2457         if self.valuation(P) >= 0: ## includes the case self=0
2458             from sage.rings.real_mpfr import RealField
2459             if prec is None:
2460                 return RealField().zero_element()
2461             else:
2462                 return RealField(prec).zero_element()
2463         ht = self.abs_non_arch(P,prec).log()
2464         if not weighted:
2465             return ht
2466         nP = P.residue_class_degree()*P.absolute_ramification_index()
2467         return nP*ht
2468 
2469     def local_height_arch(self, i, prec=None, weighted=False):
2470         r"""
2471         Returns the local height of self at the `i`'th infinite place.
2472         
2473         INPUT:
2474         
2475         
2476         - ``i`` (int) - an integer in ``range(r+s)`` where `(r,s)` is the
2477            signature of the parent field (so `n=r+2s` is the degree).
2478         
2479         - ``prec`` (int) -- desired floating point precision (default:
2480           default RealField precision).
2481 
2482         - ``weighted`` (bool, default False) -- if True, apply local
2483           degree weighting, i.e. double the value for complex places.
2484 
2485         OUTPUT:
2486 
2487         (real) The archimedean local height of this number field
2488         element at the `i`'th infinite place.  If ``weighted`` is
2489         True, this is multiplied by the local degree (as required for
2490         global heights), i.e. 1 for real places and 2 for complex
2491         places.
2492         
2493         EXAMPLES::
2494         
2495             sage: R.<x> = QQ[]
2496             sage: K.<a> = NumberField(x^4+3*x^2-17)
2497             sage: [p.codomain() for p in K.places()]
2498             [Real Field with 106 bits of precision,
2499             Real Field with 106 bits of precision,
2500             Complex Field with 53 bits of precision]
2501             sage: [a.local_height_arch(i) for i in range(3)]
2502             [0.5301924545717755083366563897519,
2503             0.5301924545717755083366563897519,
2504             0.886414217456333]
2505             sage: [a.local_height_arch(i, weighted=True) for i in range(3)]
2506             [0.5301924545717755083366563897519,
2507             0.5301924545717755083366563897519,
2508             1.77282843491267]
2509     
2510         A relative example::
2511 
2512             sage: L.<b, c> = NumberFieldTower([x^2 - 5, x^3 + x + 3])
2513             sage: [(b + c).local_height_arch(i) for i in range(4)]
2514             [1.238223390757884911842206617439,
2515             0.02240347229957875780769746914391,
2516             0.780028961749618,
2517             1.16048938497298]
2518         """
2519         K = self.number_field()
2520         emb = K.places(prec=prec)[i]
2521         a = emb(self).abs()
2522         Kv = emb.codomain()
2523         if a <= Kv.one_element():
2524             return Kv.zero_element()
2525         ht = a.log()
2526         from sage.rings.real_mpfr import is_RealField
2527         if weighted and not is_RealField(Kv):
2528             ht*=2
2529         return ht
2530 
2531     def global_height_non_arch(self, prec=None):
2532         """
2533         Returns the total non-archimedean component of the height of self.
2534         
2535         INPUT:
2536         
2537         - ``prec`` (int) -- desired floating point precision (default:
2538           default RealField precision).
2539 
2540         OUTPUT:
2541 
2542         (real) The total non-archimedean component of the height of
2543         this number field element; that is, the sum of the local
2544         heights at all finite places, weighted by the local degrees.
2545 
2546         ALGORITHM:
2547 
2548         An alternative formula is `\log(d)` where `d` is the norm of
2549         the denominator ideal; this is used to avoid factorization.
2550         
2551         EXAMPLES::
2552         
2553             sage: R.<x> = QQ[]
2554             sage: K.<a> = NumberField(x^4+3*x^2-17)
2555             sage: b = a/6
2556             sage: b.global_height_non_arch()
2557             7.16703787691222
2558             
2559         Check that this is equal to the sum of the non-archimedean
2560         local heights::
2561 
2562             sage: [b.local_height(P) for P in b.support()]
2563             [0.000000000000000, 0.693147180559945, 1.09861228866811, 1.09861228866811]
2564             sage: [b.local_height(P, weighted=True) for P in b.support()]
2565             [0.000000000000000, 2.77258872223978, 2.19722457733622, 2.19722457733622]
2566             sage: sum([b.local_height(P,weighted=True) for P in b.support()])
2567             7.16703787691222
2568     
2569         A relative example::
2570 
2571             sage: PK.<y> = K[]
2572             sage: L.<c> = NumberField(y^2 + a)
2573             sage: (c/10).global_height_non_arch()
2574             18.4206807439524
2575         """
2576         from sage.rings.real_mpfr import RealField
2577         if prec is None:
2578             R = RealField()
2579         else:
2580             R = RealField(prec)
2581         if self.is_zero():
2582             return R.zero_element()
2583         return R(self.denominator_ideal().absolute_norm()).log()
2584 
2585     def global_height_arch(self, prec=None):
2586         """
2587         Returns the total archimedean component of the height of self.
2588         
2589         INPUT:
2590         
2591         - ``prec`` (int) -- desired floating point precision (defult:
2592           default RealField precision).
2593 
2594         OUTPUT:
2595 
2596         (real) The total archimedean component of the height of
2597         this number field element; that is, the sum of the local
2598         heights at all infinite places.
2599         
2600         EXAMPLES::
2601         
2602             sage: R.<x> = QQ[]
2603             sage: K.<a> = NumberField(x^4+3*x^2-17)
2604             sage: b = a/2
2605             sage: b.global_height_arch()
2606             0.38653407379277...
2607         """
2608         r,s = self.number_field().signature()
2609         hts = [self.local_height_arch(i, prec, weighted=True) for i in range(r+s)]
2610         return sum(hts, hts[0].parent().zero_element())
2611 
2612     def global_height(self, prec=None):
2613         """
2614         Returns the absolute logarithmic height of this number field element.
2615         
2616         INPUT:
2617         
2618         - ``prec`` (int) -- desired floating point precision (defult:
2619           default RealField precision).
2620 
2621         OUTPUT:
2622 
2623         (real) The absolute logarithmic height of this number field
2624         element; that is, the sum of the local heights at all finite
2625         and infinite places, with the contributions from the infinite
2626         places scaled by the degree to make the result independent of
2627         the parent field.
2628         
2629         EXAMPLES::
2630         
2631             sage: R.<x> = QQ[]
2632             sage: K.<a> = NumberField(x^4+3*x^2-17)
2633             sage: b = a/2
2634             sage: b.global_height()
2635             2.869222240687...
2636             sage: b.global_height(prec=200)
2637             2.8692222406879748488543678846959454765968722137813736080066
2638 
2639         The global height of an algebraic number is absolute, i.e. it
2640         does not depend on th parent field::
2641 
2642             sage: QQ(6).global_height()
2643             1.79175946922805
2644             sage: K(6).global_height()
2645             1.79175946922805
2646 
2647             sage: L.<b> = NumberField((a^2).minpoly())
2648             sage: L.degree()
2649             2
2650             sage: b.global_height() # element of L (degree 2 field)
2651             1.41660667202811
2652             sage: (a^2).global_height() # element of K (degree 4 field)
2653             1.41660667202811
2654         """
2655         return self.global_height_non_arch(prec)+self.global_height_arch(prec)/self.number_field().absolute_degree()
2656 
2657     def numerator_ideal(self):
2658         """
2659         Return the numerator ideal of this number field element.
2660 
2661         .. note::
2662 
2663            A ValueError will be raised if this function is called on
2664            0.
2665 
2666         .. seealso::
2667 
2668            :meth:`~denominator_ideal`
2669         
2670         OUTPUT:
2671 
2672         (integral ideal) The numerator ideal `N` of this element,
2673         where for a non-zero number field element `a`, the principal
2674         ideal generated by `a` has the form `N/D` where `N` and `D`
2675         are coprime integral ideals.  An error is raised if the
2676         element is zero.
2677         
2678         EXAMPLES::
2679         
2680             sage: K.<a> = NumberField(x^2+5)
2681             sage: b = (1+a)/2
2682             sage: b.norm()
2683             3/2
2684             sage: N = b.numerator_ideal(); N
2685             Fractional ideal (3, a + 1)
2686             sage: N.norm()
2687             3
2688             sage: (1/b).numerator_ideal()
2689             Fractional ideal (2, a + 1)
2690         
2691         TESTS:
2692 
2693         Undefined for 0::
2694         
2695             sage: K(0).numerator_ideal()
2696             Traceback (most recent call last):
2697             ...
2698             ValueError: numerator ideal of 0 is not defined.
2699         """
2700         if self.is_zero():
2701             raise ValueError, "numerator ideal of 0 is not defined."
2702         return self.number_field().ideal(self).numerator()
2703 
2704     def denominator_ideal(self):
2705         """
2706         Return the denominator ideal of this number field element.
2707 
2708         .. note::
2709 
2710            A ValueError will be raised if this function is called on
2711            0.
2712 
2713         .. seealso::
2714 
2715            :meth:`~numerator_ideal`
2716         
2717         OUTPUT:
2718 
2719         (integral ideal) The denominator ideal `D` of this element,
2720         where for a non-zero number field element `a`, the principal
2721         ideal generated by `a` has the form `N/D` where `N` and `D`
2722         are coprime integral ideals.  An error is raised if the
2723         element is zero.
2724         
2725         EXAMPLES::
2726         
2727             sage: K.<a> = NumberField(x^2+5)
2728             sage: b = (1+a)/2
2729             sage: b.norm()
2730             3/2
2731             sage: D = b.denominator_ideal(); D
2732             Fractional ideal (2, a + 1)
2733             sage: D.norm()
2734             2
2735             sage: (1/b).denominator_ideal()
2736             Fractional ideal (3, a + 1)
2737         
2738         TESTS:
2739 
2740         Undefined for 0::
2741         
2742             sage: K(0).denominator_ideal()
2743             Traceback (most recent call last):
2744             ...
2745             ValueError: denominator ideal of 0 is not defined.
2746         """
2747         if self.is_zero():
2748             raise ValueError, "denominator ideal of 0 is not defined."
2749         return self.number_field().ideal(self).denominator()
2750 
2751     def support(self):
2752         """
2753         Return the support of this number field element.
2754         
2755         OUTPUT: A sorted list of the primes ideals at which this number
2756         field element has nonzero valuation. An error is raised if the
2757         element is zero.
2758         
2759         EXAMPLES::
2760         
2761             sage: x = ZZ['x'].gen()
2762             sage: F.<t> = NumberField(x^3 - 2)
2763         
2764         ::
2765         
2766             sage: P5s = F(5).support()
2767             sage: P5s 
2768             [Fractional ideal (t^2 + 1), Fractional ideal (t^2 - 2*t - 1)]
2769             sage: all(5 in P5 for P5 in P5s)
2770             True
2771             sage: all(P5.is_prime() for P5 in P5s)
2772             True
2773             sage: [ P5.norm() for P5 in P5s ]
2774             [5, 25]
2775         
2776         TESTS:
2777 
2778         It doesn't make sense to factor the ideal (0)::
2779         
2780             sage: F(0).support()
2781             Traceback (most recent call last):
2782             ...
2783             ArithmeticError: Support of 0 is not defined.
2784         """
2785         if self.is_zero():
2786             raise ArithmeticError, "Support of 0 is not defined."
2787         return self.number_field().primes_above(self)
2788 
2789     def _matrix_over_base(self, L):
2790         """
2791         Return the matrix of self over the base field L.
2792         
2793         EXAMPLES::
2794         
2795             sage: K.<a> = NumberField(ZZ['x'].0^3-2, 'a')
2796             sage: L.<b> = K.extension(ZZ['x'].0^2+3, 'b')
2797             sage: L(a)._matrix_over_base(K) == L(a).matrix()
2798             True
2799         """
2800         K = self.number_field()
2801         E = L.embeddings(K)
2802         if len(E) == 0:
2803             raise ValueError, "no way to embed L into parent's base ring K"
2804         phi = E[0]
2805         return self._matrix_over_base_morphism(phi)
2806 
2807     def _matrix_over_base_morphism(self, phi):
2808         """
2809         Return the matrix of self over a specified base, where phi gives a
2810         map from the specified base to self.parent().
2811         
2812         EXAMPLES::
2813         
2814             sage: F.<alpha> = NumberField(ZZ['x'].0^5-2)
2815             sage: h = Hom(QQ,F)([1])
2816             sage: alpha._matrix_over_base_morphism(h) == alpha.matrix()
2817             True
2818             sage: alpha._matrix_over_base_morphism(h) == alpha.matrix(QQ)
2819             True
2820         """
2821         L = phi.domain()
2822 
2823         ## the code below doesn't work if the morphism is
2824         ## over QQ, since QQ.primitive_element() doesn't
2825         ## make sense
2826         if L is QQ:
2827             K = phi.codomain()
2828             if K != self.number_field():
2829                 raise ValueError, "codomain of phi must be parent of self"
2830             ## the variable name is irrelevant below, because the
2831             ## matrix is over QQ
2832             F = K.absolute_field('alpha')
2833             from_f, to_F = F.structure()
2834             return to_F(self).matrix()
2835         
2836         alpha = L.primitive_element()
2837         beta = phi(alpha)
2838         K = phi.codomain()
2839         if K != self.number_field():
2840             raise ValueError, "codomain of phi must be parent of self"
2841 
2842         # Construct a relative extension over L (= QQ(beta))
2843         M = K.relativize(beta, ('a','b'))
2844                      # variable name a is OK, since this is temporary
2845 
2846         # Carry self over to M.
2847         from_M, to_M = M.structure()
2848         try:
2849             z = to_M(self)
2850         except Exception:
2851             return to_M, self, K, beta
2852 
2853         # Compute the relative matrix of self, but in M
2854         R = z.matrix()
2855 
2856         # Map back to L.
2857         psi = M.base_field().hom([alpha])
2858         return R.apply_morphism(psi)
2859         
2860 
2861     def list(self):
2862         """
2863         Return the list of coefficients of self written in terms of a power
2864         basis.
2865         
2866         EXAMPLE::
2867         
2868             sage: K.<a> = NumberField(x^3 - x + 2); ((a + 1)/(a + 2)).list()
2869             [1/4, 1/2, -1/4]
2870             sage: K.<a, b> = NumberField([x^3 - x + 2, x^2 + 23]); ((a + b)/(a + 2)).list()
2871             [3/4*b - 1/2, -1/2*b + 1, 1/4*b - 1/2]
2872         """
2873         raise NotImplementedError
2874         
2875     def inverse_mod(self, I):
2876         """
2877         Returns the inverse of self mod the integral ideal I.
2878 
2879         INPUT:
2880 
2881         -  ``I`` - may be an ideal of self.parent(), or an element or list
2882            of elements of self.parent() generating a nonzero ideal. A ValueError
2883            is raised if I is non-integral or zero. A ZeroDivisionError is 
2884            raised if I + (x) != (1).
2885 
2886         NOTE: It's not implemented yet for non-integral elements.
2887 
2888         EXAMPLES::
2889 
2890             sage: k.<a> = NumberField(x^2 + 23)
2891             sage: N = k.ideal(3)
2892             sage: d = 3*a + 1
2893             sage: d.inverse_mod(N)
2894             1
2895 
2896         ::
2897 
2898             sage: k.<a> = NumberField(x^3 + 11)
2899             sage: d = a + 13
2900             sage: d.inverse_mod(a^2)*d - 1 in k.ideal(a^2)
2901             True
2902             sage: d.inverse_mod((5, a + 1))*d - 1 in k.ideal(5, a + 1)
2903             True
2904             sage: K.<b> = k.extension(x^2 + 3)
2905             sage: b.inverse_mod([37, a - b])
2906             7
2907             sage: 7*b - 1 in K.ideal(37, a - b)
2908             True
2909             sage: b.inverse_mod([37, a - b]).parent() == K
2910             True
2911         """
2912         R = self.number_field().ring_of_integers()
2913         try:
2914             return _inverse_mod_generic(R(self), I)
2915         except TypeError: # raised by failure of R(self)
2916             raise NotImplementedError, "inverse_mod is not implemented for non-integral elements"                
2917 
2918 
2919     def residue_symbol(self, P, m, check=True):
2920         r"""
2921         The m-th power residue symbol for an element self and proper ideal P.
2922 
2923         .. math:: \left(\frac{\alpha}{\mathbf{P}}\right) \equiv \alpha^{\frac{N(\mathbf{P})-1}{m}} \operatorname{mod} \mathbf{P}
2924         
2925         .. note:: accepts m=1, in which case returns 1
2926 
2927         .. note:: can also be called for an ideal from sage.rings.number_field_ideal.residue_symbol
2928         
2929         INPUT:
2930             
2931         - ``P`` - proper ideal of the number field (or an extension)
2932                 
2933         - ``m`` - positive integer
2934         
2935         OUTPUT:
2936             
2937         - an m-th root of unity in the number field
2938         
2939         EXAMPLES::
2940             
2941             Quadratic Residue (7 is not a square modulo 11)
2942             sage: K.<a> = NumberField(x-1)
2943             sage: K(7).residue_symbol(K.ideal(11),2)
2944             -1
2945             
2946             Cubic Residue
2947             sage: K.<w> = NumberField(x^2 - x + 1)
2948             sage: (w^2+3).residue_symbol(K.ideal(17),3)
2949             -w
2950             
2951         """
2952         return P.residue_symbol(self,m,check)
2953 
2954 
2955 
2956 cdef class NumberFieldElement_absolute(NumberFieldElement):
2957 
2958     def _pari_(self, var='x'):
2959         """
2960         Return PARI C-library object corresponding to self.
2961         
2962         EXAMPLES::
2963         
2964             sage: k.<j> = QuadraticField(-1)
2965             sage: j._pari_('j')
2966             Mod(j, j^2 + 1)
2967             sage: pari(j)
2968             Mod(x, x^2 + 1)
2969         
2970         ::
2971         
2972             sage: y = QQ['y'].gen()
2973             sage: k.<j> = NumberField(y^3 - 2)
2974             sage: pari(j)
2975             Mod(x, x^3 - 2)
2976         
2977         By default the variable name is 'x', since in PARI many variable
2978         names are reserved::
2979         
2980             sage: theta = polygen(QQ, 'theta')
2981             sage: M.<theta> = NumberField(theta^2 + 1)
2982             sage: pari(theta)
2983             Mod(x, x^2 + 1)
2984         
2985         If you try do coerce a generator called I to PARI, hell may break
2986         loose::
2987         
2988             sage: k.<I> = QuadraticField(-1)
2989             sage: I._pari_('I')
2990             Traceback (most recent call last):
2991             ...
2992             PariError: incorrect type (11)
2993         
2994         Instead, request the variable be named different for the coercion::
2995         
2996             sage: pari(I)
2997             Mod(x, x^2 + 1)
2998             sage: I._pari_('i')
2999             Mod(i, i^2 + 1)
3000             sage: I._pari_('II')
3001             Mod(II, II^2 + 1)
3002         """
3003         try:
3004             return self.__pari[var]
3005         except KeyError:
3006             pass
3007         except TypeError:
3008             self.__pari = {}
3009         if var is None:
3010             var = self.number_field().variable_name()
3011 
3012         f = self.polynomial()._pari_().subst('x', var)
3013         g = self.number_field().pari_polynomial().subst('x', var)
3014         h = f.Mod(g)
3015         self.__pari[var] = h
3016         return h
3017 
3018     def _magma_init_(self, magma):
3019         """
3020         Return Magma version of this number field element.
3021         
3022         INPUT:
3023         
3024         
3025         -  ``magma`` - a Magma interpreter
3026         
3027         
3028         OUTPUT: MagmaElement that has parent the Magma object corresponding
3029         to the parent number field.
3030         
3031         EXAMPLES::
3032         
3033             sage: K.<a> = NumberField(x^3 + 2)
3034             sage: a._magma_init_(magma)            # optional - magma
3035             '(_sage_[...]![0, 1, 0])'            
3036             sage: magma((2/3)*a^2 - 17/3)          # optional - magma
3037             1/3*(2*a^2 - 17)
3038         
3039         An element of a cyclotomic field.
3040         
3041         ::
3042         
3043             sage: K = CyclotomicField(9)
3044             sage: K.gen()
3045             zeta9
3046             sage: K.gen()._magma_init_(magma)     # optional - magma
3047             '(_sage_[...]![0, 1, 0, 0, 0, 0])'
3048             sage: magma(K.gen())                  # optional - magma
3049             zeta9
3050         """
3051         K = magma(self.parent())
3052         return '(%s!%s)'%(K.name(), self.list())
3053         
3054     def absolute_charpoly(self, var='x', algorithm=None):
3055         r"""
3056         Return the characteristic polynomial of this element over `\QQ`.
3057 
3058         For the meaning of the optional argument ``algorithm``, see :meth:`charpoly`.
3059 
3060         EXAMPLES::
3061         
3062             sage: x = ZZ['x'].0
3063             sage: K.<a> = NumberField(x^4 + 2, 'a')
3064             sage: a.absolute_charpoly()
3065             x^4 + 2
3066             sage: a.absolute_charpoly('y')
3067             y^4 + 2
3068             sage: (-a^2).absolute_charpoly()
3069             x^4 + 4*x^2 + 4
3070             sage: (-a^2).absolute_minpoly()
3071             x^2 + 2
3072 
3073             sage: a.absolute_charpoly(algorithm='pari') == a.absolute_charpoly(algorithm='sage')
3074             True
3075         """
3076         # this hack is necessary because quadratic fields override
3077         # charpoly(), and they don't take the argument 'algorithm'
3078         if algorithm is None:
3079             return self.charpoly(var)
3080         return self.charpoly(var, algorithm)
3081 
3082     def absolute_minpoly(self, var='x', algorithm=None):
3083         r"""
3084         Return the minimal polynomial of this element over
3085         `\QQ`.
3086         
3087         For the meaning of the optional argument algorithm, see :meth:`charpoly`.
3088 
3089         EXAMPLES::
3090         
3091             sage: x = ZZ['x'].0
3092             sage: f = x^10 - 5*x^9 + 15*x^8 - 68*x^7 + 81*x^6 - 221*x^5 + 141*x^4 - 242*x^3 - 13*x^2 - 33*x - 135
3093             sage: K.<a> = NumberField(f, 'a')
3094             sage: a.absolute_charpoly()
3095             x^10 - 5*x^9 + 15*x^8 - 68*x^7 + 81*x^6 - 221*x^5 + 141*x^4 - 242*x^3 - 13*x^2 - 33*x - 135
3096             sage: a.absolute_charpoly('y')
3097             y^10 - 5*y^9 + 15*y^8 - 68*y^7 + 81*y^6 - 221*y^5 + 141*y^4 - 242*y^3 - 13*y^2 - 33*y - 135
3098             sage: b = -79/9995*a^9 + 52/9995*a^8 + 271/9995*a^7 + 1663/9995*a^6 + 13204/9995*a^5 + 5573/9995*a^4 + 8435/1999*a^3 - 3116/9995*a^2 + 7734/1999*a + 1620/1999
3099             sage: b.absolute_charpoly()
3100             x^10 + 10*x^9 + 25*x^8 - 80*x^7 - 438*x^6 + 80*x^5 + 2950*x^4 + 1520*x^3 - 10439*x^2 - 5130*x + 18225
3101             sage: b.absolute_minpoly()
3102             x^5 + 5*x^4 - 40*x^2 - 19*x + 135
3103 
3104             sage: b.absolute_minpoly(algorithm='pari') == b.absolute_minpoly(algorithm='sage')
3105             True
3106         """
3107         # this hack is necessary because quadratic fields override
3108         # minpoly(), and they don't take the argument 'algorithm'
3109         if algorithm is None:
3110             return self.minpoly(var)
3111         return self.minpoly(var, algorithm)
3112 
3113     def charpoly(self, var='x', algorithm=None):
3114         r"""
3115         The characteristic polynomial of this element, over
3116         `\QQ` if self is an element of a field, and over
3117         `\ZZ` is self is an element of an order.
3118         
3119         This is the same as ``self.absolute_charpoly`` since
3120         this is an element of an absolute extension.
3121         
3122         The optional argument algorithm controls how the
3123         characteristic polynomial is computed: 'pari' uses Pari,
3124         'sage' uses charpoly for Sage matrices.  The default value
3125         None means that 'pari' is used for small degrees (up to the
3126         value of the constant TUNE_CHARPOLY_NF, currently at 25),
3127         otherwise 'sage' is used.  The constant TUNE_CHARPOLY_NF
3128         should give reasonable performance on all architectures;
3129         however, if you feel the need to customize it to your own
3130         machine, see trac ticket 5213 for a tuning script.
3131 
3132         EXAMPLES:
3133         
3134         We compute the characteristic polynomial of the cube root of `2`.
3135         
3136         ::
3137         
3138             sage: R.<x> = QQ[]
3139             sage: K.<a> = NumberField(x^3-2)
3140             sage: a.charpoly('x')
3141             x^3 - 2
3142             sage: a.charpoly('y').parent()
3143             Univariate Polynomial Ring in y over Rational Field
3144         
3145         TESTS::
3146         
3147             sage: R = K.ring_of_integers()
3148             sage: R(a).charpoly()
3149             x^3 - 2
3150             sage: R(a).charpoly().parent()
3151             Univariate Polynomial Ring in x over Integer Ring
3152 
3153             sage: R(a).charpoly(algorithm='pari') == R(a).charpoly(algorithm='sage')
3154             True
3155         """
3156         if algorithm is None:
3157             if self._parent.degree() <= TUNE_CHARPOLY_NF:
3158                 algorithm = 'pari'
3159             else:
3160                 algorithm = 'sage'
3161         R = self._parent.base_ring()[var]
3162         if algorithm == 'pari':
3163             return R(self._pari_('x').charpoly())
3164         if algorithm == 'sage':
3165             return R(self.matrix().charpoly())
3166 
3167     def minpoly(self, var='x', algorithm=None):
3168         """
3169         Return the minimal polynomial of this number field element.
3170 
3171         For the meaning of the optional argument algorithm, see charpoly().
3172 
3173         EXAMPLES:
3174         
3175         We compute the characteristic polynomial of cube root of `2`.
3176 
3177         ::
3178         
3179             sage: R.<x> = QQ[]
3180             sage: K.<a> = NumberField(x^3-2)
3181             sage: a.minpoly('x')
3182             x^3 - 2
3183             sage: a.minpoly('y').parent()
3184             Univariate Polynomial Ring in y over Rational Field
3185             
3186         TESTS::
3187         
3188             sage: R = K.ring_of_integers()
3189             sage: R(a).minpoly()
3190             x^3 - 2
3191             sage: R(a).minpoly().parent()
3192             Univariate Polynomial Ring in x over Integer Ring
3193 
3194             sage: R(a).minpoly(algorithm='pari') == R(a).minpoly(algorithm='sage')
3195             True
3196 
3197         """
3198         return self.charpoly(var, algorithm).radical() # square free part of charpoly
3199         
3200     def list(self):
3201         """
3202         Return the list of coefficients of self written in terms of a power
3203         basis.
3204         
3205         EXAMPLE::
3206         
3207             sage: K.<z> = CyclotomicField(3)
3208             sage: (2+3/5*z).list()
3209             [2, 3/5]
3210             sage: (5*z).list()
3211             [0, 5]
3212             sage: K(3).list()
3213             [3, 0]
3214         """
3215         n = self.number_field().degree()
3216         v = self._coefficients()
3217         z = sage.rings.rational.Rational(0)
3218         return v + [z]*(n - len(v))
3219         
3220     def lift(self, var='x'):
3221         """
3222         Return an element of QQ[x], where this number field element
3223         lives in QQ[x]/(f(x)).
3224         
3225         EXAMPLES::
3226         
3227             sage: K.<a> = QuadraticField(-3)
3228             sage: a.lift()
3229             x
3230         
3231         """
3232         R = self.number_field().base_field()[var]
3233         return R(self.list())
3234 
3235     def is_real_positive(self, min_prec=53):
3236         r"""
3237         Using the ``n`` method of approximation, return ``True`` if
3238         ``self`` is a real positive number and ``False`` otherwise. 
3239         This method is completely dependent of the embedding used by 
3240         the ``n`` method.
3241 
3242         The algorithm first checks that ``self`` is not a strictly
3243         complex number. Then if ``self`` is not zero, by approximation
3244         more and more precise, the method answers True if the 
3245         number is positive. Using `RealInterval`, the result is
3246         guaranteed to be correct. 
3247 
3248         For CyclotomicField, the embedding is the natural one
3249         sending `zetan` on `cos(2*pi/n)`.
3250 
3251         EXAMPLES::
3252 
3253             sage: K.<a> = CyclotomicField(3)
3254             sage: (a+a^2).is_real_positive()
3255             False
3256             sage: (-a-a^2).is_real_positive()
3257             True
3258             sage: K.<a> = CyclotomicField(1000)
3259             sage: (a+a^(-1)).is_real_positive()
3260             True
3261             sage: K.<a> = CyclotomicField(1009)
3262             sage: d = a^252
3263             sage: (d+d.conjugate()).is_real_positive()
3264             True
3265             sage: d = a^253
3266             sage: (d+d.conjugate()).is_real_positive()
3267             False
3268             sage: K.<a> = QuadraticField(3)
3269             sage: a.is_real_positive()
3270             True
3271             sage: K.<a> = QuadraticField(-3)
3272             sage: a.is_real_positive()
3273             False
3274             sage: (a-a).is_real_positive()
3275             False
3276         """
3277         if self != self.conjugate() or self.is_zero():
3278             return False
3279         else:
3280             approx = RealInterval(self.n(min_prec).real())
3281             if approx.lower() > 0:
3282                 return True
3283             else:
3284                 if approx.upper() < 0:
3285                     return False
3286                 else:
3287                     return self.is_real_positive(min_prec+20)
3288 
3289 cdef class NumberFieldElement_relative(NumberFieldElement):
3290     r"""
3291     The current relative number field element implementation
3292     does everything in terms of absolute polynomials.
3293 
3294     All conversions from relative polynomials, lists, vectors, etc
3295     should happen in the parent.
3296     """
3297     def __init__(self, parent, f):
3298         r"""
3299         EXAMPLE::
3300         
3301             sage: L.<a, b> = NumberField([x^2 + 1, x^2 + 2])
3302             sage: type(a) # indirect doctest
3303             <type 'sage.rings.number_field.number_field_element.NumberFieldElement_relative'>
3304         """
3305         NumberFieldElement.__init__(self, parent, f)
3306 
3307     def __getitem__(self, n):
3308         """
3309         Return the n-th coefficient of this relative number field element, written
3310         as a polynomial in the generator.
3311         
3312         Note that `n` must be between 0 and `d-1`, where
3313         `d` is the relative degree of the number field.
3314         
3315         EXAMPLES::
3316         
3317             sage: K.<a, b> = NumberField([x^3 - 5, x^2 + 3])
3318             sage: c = (a + b)^3; c
3319             3*b*a^2 - 9*a - 3*b + 5
3320             sage: c[0]
3321             -3*b + 5
3322         
3323         We illustrate bounds checking::
3324         
3325             sage: c[-1]
3326             Traceback (most recent call last):
3327             ...
3328             IndexError: index must be between 0 and the relative degree minus 1.
3329             sage: c[4]
3330             Traceback (most recent call last):
3331             ...
3332             IndexError: index must be between 0 and the relative degree minus 1.
3333         
3334         The list method implicitly calls ``__getitem__``::
3335         
3336             sage: list(c)
3337             [-3*b + 5, -9, 3*b]
3338             sage: K(list(c)) == c
3339             True
3340         """
3341         if n < 0 or n >= self.parent().relative_degree():
3342             raise IndexError, "index must be between 0 and the relative degree minus 1."
3343         return self.vector()[n]
3344 
3345     def list(self):
3346         """
3347         Return the list of coefficients of self written in terms of a power
3348         basis.
3349         
3350         EXAMPLES::
3351         
3352             sage: K.<a,b> = NumberField([x^3+2, x^2+1])
3353             sage: a.list()
3354             [0, 1, 0]
3355             sage: v = (K.base_field().0 + a)^2 ; v
3356             a^2 + 2*b*a - 1
3357             sage: v.list()
3358             [-1, 2*b, 1]
3359         """
3360         return self.vector().list()
3361         
3362     def lift(self, var='x'):
3363         """
3364         Return an element of K[x], where this number field element
3365         lives in the relative number field K[x]/(f(x)).
3366         
3367         EXAMPLES::
3368         
3369             sage: K.<a> = QuadraticField(-3)
3370             sage: x = polygen(K)
3371             sage: L.<b> = K.extension(x^7 + 5)
3372             sage: u = L(1/2*a + 1/2 + b + (a-9)*b^5)
3373             sage: u.lift()
3374             (a - 9)*x^5 + x + 1/2*a + 1/2
3375         
3376         """
3377         K = self.number_field()
3378         # Compute representation of self in terms of relative vector space.
3379         R = K.base_field()[var]
3380         return R(self.list())
3381 
3382     def _pari_(self, var='x'):
3383         """
3384         Return PARI C-library object corresponding to self.
3385         
3386         EXAMPLES:
3387 
3388         By default the variable name is 'x', since in PARI many
3389         variable names are reserved.
3390         
3391         ::
3392         
3393             sage: y = QQ['y'].gen()
3394             sage: k.<j> = NumberField([y^2 - 7, y^3 - 2])
3395             sage: pari(j)
3396             Mod(42/5515*x^5 - 9/11030*x^4 - 196/1103*x^3 + 273/5515*x^2 + 10281/5515*x + 4459/11030, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
3397             sage: j^2
3398             7
3399             sage: pari(j)^2
3400             Mod(7, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
3401             sage: (j^2)._pari_('y')
3402             Mod(7, y^6 - 21*y^4 + 4*y^3 + 147*y^2 + 84*y - 339)
3403 
3404             sage: K.<a> = NumberField(x^2 + 2, 'a')
3405             sage: K(1)._pari_()
3406             Mod(1, x^2 + 2)
3407             sage: K(1)._pari_('t')
3408             Mod(1, t^2 + 2)
3409             
3410             sage: K.gen()._pari_()
3411             Mod(x, x^2 + 2)
3412             sage: K.gen()._pari_('t')
3413             Mod(t, t^2 + 2)
3414 
3415             At this time all elements, even relative elements, are
3416             represented as absolute polynomials:
3417 
3418             sage: K.<a> = NumberField(x^2 + 2, 'a')
3419             sage: L.<b> = NumberField(K['x'].0^2 + a, 'b')
3420             sage: L(1)._pari_()
3421             Mod(1, x^4 + 2)
3422             sage: L(1)._pari_('t')
3423             Mod(1, t^4 + 2)
3424             sage: L.gen()._pari_()
3425             Mod(x, x^4 + 2)
3426             sage: L.gen()._pari_('t')
3427             Mod(t, t^4 + 2)
3428 
3429             sage: M.<c> = NumberField(L['x'].0^3 + b, 'c')
3430             sage: M(1)._pari_()
3431             Mod(1, x^12 + 2)
3432             sage: M(1)._pari_('t')
3433             Mod(1, t^12 + 2)
3434             sage: M.gen()._pari_()
3435             Mod(x, x^12 + 2)
3436             sage: M.gen()._pari_('t')
3437             Mod(t, t^12 + 2)
3438         """
3439         try:
3440             return self.__pari[var]
3441         except KeyError:
3442             pass
3443         except TypeError:
3444             self.__pari = {}
3445         g = self.parent().pari_polynomial(var)
3446         f = self.polynomial()._pari_()
3447         f = f.subst('x', var)
3448         h = f.Mod(g)
3449         self.__pari[var] = h
3450         return h
3451 
3452     def _repr_(self):
3453         r"""
3454         EXAMPLE::
3455         
3456             sage: L.<a, b> = NumberField([x^3 - x + 1, x^2 + 23])
3457             sage: repr(a^4*b) # indirect doctest
3458             'b*a^2 - b*a'
3459         """
3460         K = self.number_field()
3461         # Compute representation of self in terms of relative vector space.
3462         R = K.base_field()[K.variable_name()]
3463         return repr(R(self.list()))
3464 
3465     def _latex_(self):
3466         r"""
3467         Returns the latex representation for this element.
3468         
3469         EXAMPLES::
3470         
3471             sage: C.<zeta> = CyclotomicField(12)
3472             sage: PC.<x> = PolynomialRing(C)
3473             sage: K.<alpha> = NumberField(x^2 - 7)
3474             sage: latex((alpha + zeta)^4) # indirect doctest
3475             \left(4 \zeta_{12}^{3} + 28 \zeta_{12}\right) \alpha + 43 \zeta_{12}^{2} + 48
3476             sage: PK.<y> = PolynomialRing(K)
3477             sage: L.<beta> = NumberField(y^3 + y + alpha)
3478             sage: latex((beta + zeta)^3) # indirect doctest
3479             3 \zeta_{12} \beta^{2} + \left(3 \zeta_{12}^{2} - 1\right) \beta - \alpha + \zeta_{12}^{3}
3480         """
3481         K = self.number_field()
3482         R = K.base_field()[K.variable_name()]
3483         return R(self.list())._latex_()
3484 
3485     def charpoly(self, var='x'):
3486         r"""
3487         The characteristic polynomial of this element over its base field.
3488         
3489         EXAMPLES::
3490         
3491             sage: x = ZZ['x'].0
3492             sage: K.<a, b> = QQ.extension([x^2 + 2, x^5 + 400*x^4 + 11*x^2 + 2])
3493             sage: a.charpoly()
3494             x^2 + 2
3495             sage: b.charpoly()
3496             x^2 - 2*b*x + b^2
3497             sage: b.minpoly()
3498             x - b
3499 
3500             sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
3501             sage: y = K['y'].0
3502             sage: L.<c> = K.extension(y^2 + a*y + b)
3503             sage: c.charpoly()
3504             x^2 + a*x + b
3505             sage: c.minpoly()
3506             x^2 + a*x + b
3507             sage: L(a).charpoly()
3508             x^2 - 2*a*x - 2
3509             sage: L(a).minpoly()
3510             x - a
3511             sage: L(b).charpoly()
3512             x^2 - 2*b*x - 1000*b - 1
3513             sage: L(b).minpoly()
3514             x - b
3515         """
3516         R = self._parent.base_ring()[var]
3517         return R(self.matrix().charpoly())
3518 
3519     def absolute_charpoly(self, var='x', algorithm=None):
3520         r"""
3521         The characteristic polynomial of this element over
3522         `\QQ`.
3523         
3524         We construct a relative extension and find the characteristic
3525         polynomial over `\QQ`.
3526 
3527         The optional argument algorithm controls how the
3528         characteristic polynomial is computed: 'pari' uses Pari,
3529         'sage' uses charpoly for Sage matrices.  The default value
3530         None means that 'pari' is used for small degrees (up to the
3531         value of the constant TUNE_CHARPOLY_NF, currently at 25),
3532         otherwise 'sage' is used.  The constant TUNE_CHARPOLY_NF
3533         should give reasonable performance on all architectures;
3534         however, if you feel the need to customize it to your own
3535         machine, see trac ticket 5213 for a tuning script.
3536 
3537         EXAMPLES::
3538         
3539             sage: R.<x> = QQ[]
3540             sage: K.<a> = NumberField(x^3-2)
3541             sage: S.<X> = K[] 
3542             sage: L.<b> = NumberField(X^3 + 17); L
3543             Number Field in b with defining polynomial X^3 + 17 over its base field
3544             sage: b.absolute_charpoly()
3545             x^9 + 51*x^6 + 867*x^3 + 4913
3546             sage: b.charpoly()(b)
3547             0
3548             sage: a = L.0; a
3549             b
3550             sage: a.absolute_charpoly('x')
3551             x^9 + 51*x^6 + 867*x^3 + 4913
3552             sage: a.absolute_charpoly('y')
3553             y^9 + 51*y^6 + 867*y^3 + 4913
3554 
3555             sage: a.absolute_charpoly(algorithm='pari') == a.absolute_charpoly(algorithm='sage')
3556             True
3557         """
3558         if algorithm is None:
3559             # this might not be the optimal condition; maybe it should
3560             # be .degree() instead of .absolute_degree()
3561             # there are too many bugs in relative number fields to
3562             # figure this out now
3563             if self._parent.absolute_degree() <= TUNE_CHARPOLY_NF:
3564                 algorithm = 'pari'
3565             else:
3566                 algorithm = 'sage'
3567         g = self.polynomial()  # in QQ[x] 
3568         R = QQ[var]
3569         if algorithm == 'pari':
3570             f = self.number_field().pari_polynomial()  # # field is QQ[x]/(f) 
3571             return R((g._pari_().Mod(f)).charpoly()).change_variable_name(var)         
3572         if algorithm == 'sage':
3573             return R(self.matrix(QQ).charpoly())
3574 
3575     def absolute_minpoly(self, var='x', algorithm=None):
3576         r"""
3577         Return the minimal polynomial over `\QQ` of this element.
3578 
3579         For the meaning of the optional argument ``algorithm``, see :meth:`absolute_charpoly`.
3580         
3581         EXAMPLES::
3582         
3583             sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
3584             sage: y = K['y'].0
3585             sage: L.<c> = K.extension(y^2 + a*y + b)
3586             sage: c.absolute_charpoly()
3587             x^8 - 1996*x^6 + 996006*x^4 + 1997996*x^2 + 1
3588             sage: c.absolute_minpoly()
3589             x^8 - 1996*x^6 + 996006*x^4 + 1997996*x^2 + 1
3590             sage: L(a).absolute_charpoly()
3591             x^8 + 8*x^6 + 24*x^4 + 32*x^2 + 16
3592             sage: L(a).absolute_minpoly()
3593             x^2 + 2
3594             sage: L(b).absolute_charpoly()
3595             x^8 + 4000*x^7 + 6000004*x^6 + 4000012000*x^5 + 1000012000006*x^4 + 4000012000*x^3 + 6000004*x^2 + 4000*x + 1
3596             sage: L(b).absolute_minpoly()
3597             x^2 + 1000*x + 1
3598         """
3599         return self.absolute_charpoly(var, algorithm).radical()
3600 
3601     def valuation(self, P):
3602         """
3603         Returns the valuation of self at a given prime ideal P.
3604         
3605         INPUT:
3606         
3607         
3608         -  ``P`` - a prime ideal of relative number field which is the parent of self
3609         
3610         
3611         EXAMPLES::
3612         
3613             sage: K.<a, b, c> = NumberField([x^2 - 2, x^2 - 3, x^2 - 5])
3614             sage: P = K.prime_factors(5)[0]
3615             sage: (2*a + b - c).valuation(P)
3616             1
3617         """
3618         P_abs = P.absolute_ideal()
3619         abs = P_abs.number_field()
3620         to_abs = abs.structure()[1]
3621         return to_abs(self).valuation(P_abs)
3622 
3623 
3624 cdef class OrderElement_absolute(NumberFieldElement_absolute):
3625     """
3626     Element of an order in an absolute number field.
3627     
3628     EXAMPLES::
3629     
3630         sage: K.<a> = NumberField(x^2 + 1)
3631         sage: O2 = K.order(2*a)
3632         sage: w = O2.1; w
3633         2*a
3634         sage: parent(w)
3635         Order in Number Field in a with defining polynomial x^2 + 1
3636 
3637         sage: w.absolute_charpoly()
3638         x^2 + 4
3639         sage: w.absolute_charpoly().parent()
3640         Univariate Polynomial Ring in x over Integer Ring
3641         sage: w.absolute_minpoly()
3642         x^2 + 4
3643         sage: w.absolute_minpoly().parent()
3644         Univariate Polynomial Ring in x over Integer Ring
3645     """
3646     def __init__(self, order, f):
3647         r"""
3648         EXAMPLE::
3649         
3650             sage: K.<a> = NumberField(x^3 + 2)
3651             sage: O2 = K.order(2*a)
3652             sage: type(O2.1) # indirect doctest
3653             <type 'sage.rings.number_field.number_field_element.OrderElement_absolute'>
3654         """
3655         K = order.number_field()
3656         NumberFieldElement_absolute.__init__(self, K, f)
3657         self._number_field = K
3658         (<Element>self)._parent = order
3659 
3660     cdef _new(self):
3661         """
3662         Quickly creates a new initialized NumberFieldElement with the same
3663         parent as self.
3664         
3665         EXAMPLES:
3666 
3667         This is called implicitly in multiplication::
3668         
3669             sage: O = EquationOrder(x^3 + 18, 'a')
3670             sage: O.1 * O.1 * O.1
3671             -18
3672         """
3673         cdef OrderElement_absolute x
3674         x = <OrderElement_absolute>PY_NEW_SAME_TYPE(self)
3675         x._parent = self._parent
3676         x._number_field = self._parent.number_field()
3677         x.__fld_numerator = self.__fld_numerator
3678         x.__fld_denominator = self.__fld_denominator
3679         return x
3680 
3681     cdef number_field(self):
3682         r"""
3683         Return the number field of self. Only accessible from Cython.
3684         
3685         EXAMPLE::
3686             
3687             sage: K = NumberField(x^3 - 17, 'a')
3688             sage: OK = K.ring_of_integers()
3689             sage: a = OK(K.gen())
3690             sage: a._number_field() is K # indirect doctest
3691             True
3692         """
3693         return self._number_field
3694 
3695     cpdef RingElement _div_(self, RingElement other):
3696         r"""
3697         Implement division, checking that the result has the right parent.
3698         It's not so crucial what the parent actually is, but it is crucial
3699         that the returned value really is an element of its supposed
3700         parent! This fixes trac #4190.
3701         
3702         EXAMPLES::
3703         
3704             sage: K = NumberField(x^3 - 17, 'a')
3705             sage: OK = K.ring_of_integers()
3706             sage: a = OK(K.gen())
3707             sage: (17/a) in OK # indirect doctest
3708             True
3709             sage: (17/a).parent() is K # indirect doctest
3710             True
3711             sage: (17/(2*a)).parent() is K # indirect doctest
3712             True
3713             sage: (17/(2*a)) in OK # indirect doctest
3714             False
3715         """     
3716         cdef NumberFieldElement_absolute x 
3717         x = NumberFieldElement_absolute._div_(self, other)
3718         return self._parent.number_field()(x)
3719 
3720     def inverse_mod(self, I):
3721         r""" 
3722         Return an inverse of self modulo the given ideal.
3723         
3724         INPUT:
3725         
3726         
3727         -  ``I`` - may be an ideal of self.parent(), or an
3728            element or list of elements of self.parent() generating a nonzero
3729            ideal. A ValueError is raised if I is non-integral or is zero. 
3730            A ZeroDivisionError is raised if I + (x) != (1).
3731         
3732         
3733         EXAMPLES::
3734         
3735             sage: OE = NumberField(x^3 - x + 2, 'w').ring_of_integers()
3736             sage: w = OE.ring_generators()[0]
3737             sage: w.inverse_mod(13*OE)
3738             6*w^2 - 6
3739             sage: w * (w.inverse_mod(13)) - 1 in 13*OE
3740             True
3741             sage: w.inverse_mod(13).parent() == OE
3742             True
3743             sage: w.inverse_mod(2*OE)
3744             Traceback (most recent call last):
3745             ...
3746             ZeroDivisionError: w is not invertible modulo Fractional ideal (2)
3747         """
3748         R = self.parent()
3749         return R(_inverse_mod_generic(self, I))
3750 
3751     def __invert__(self):
3752         r"""
3753         Implement inversion, checking that the return value has the right
3754         parent. See trac #4190.
3755 
3756         EXAMPLE::
3757         
3758             sage: K = NumberField(x^3 -x + 2, 'a')
3759             sage: OK = K.ring_of_integers()
3760             sage: a = OK(K.gen())
3761             sage: (~a).parent() is K
3762             True
3763             sage: (~a) in OK
3764             False
3765             sage: a**(-1) in OK
3766             False
3767         """
3768         return self._parent.number_field()(NumberFieldElement_absolute.__invert__(self))
3769 
3770 cdef class OrderElement_relative(NumberFieldElement_relative):
3771     """
3772     Element of an order in a relative number field.
3773     
3774     EXAMPLES::
3775     
3776         sage: O = EquationOrder([x^2 + x + 1, x^3 - 2],'a,b')
3777         sage: c = O.1; c
3778         (-2*b^2 - 2)*a - 2*b^2 - b
3779         sage: type(c)
3780         <type 'sage.rings.number_field.number_field_element.OrderElement_relative'>
3781     """
3782     def __init__(self, order, f):
3783         r"""
3784         EXAMPLE::
3785         
3786             sage: O = EquationOrder([x^2 + x + 1, x^3 - 2],'a,b')
3787             sage: type(O.1) # indirect doctest
3788             <type 'sage.rings.number_field.number_field_element.OrderElement_relative'>
3789         """
3790         K = order.number_field()
3791         NumberFieldElement_relative.__init__(self, K, f)
3792         (<Element>self)._parent = order
3793         self._number_field = K
3794         
3795     cdef number_field(self):
3796         return self._number_field
3797 
3798     cdef _new(self):
3799         """
3800         Quickly creates a new initialized NumberFieldElement with the same
3801         parent as self.
3802         
3803         EXAMPLES:
3804 
3805         This is called implicitly in multiplication::
3806         
3807             sage: O = EquationOrder([x^2 + 18, x^3 + 2], 'a,b')
3808             sage: c = O.1 * O.2; c
3809             (-23321*b^2 - 9504*b + 10830)*a + 10152*b^2 - 104562*b - 110158
3810             sage: parent(c) == O
3811             True
3812         """
3813         cdef OrderElement_relative x
3814         x = <OrderElement_relative>PY_NEW_SAME_TYPE(self)
3815         x._parent = self._parent
3816         x._number_field = self._parent.number_field()
3817         x.__fld_numerator = self.__fld_numerator
3818         x.__fld_denominator = self.__fld_denominator
3819         return x
3820 
3821     cpdef RingElement _div_(self, RingElement other):
3822         r"""
3823         Implement division, checking that the result has the right parent.
3824         It's not so crucial what the parent actually is, but it is crucial
3825         that the returned value really is an element of its supposed
3826         parent. This fixes trac #4190.
3827         
3828         EXAMPLES::
3829         
3830             sage: K1.<a> = NumberField(x^3 - 17)
3831             sage: R.<y> = K1[]
3832             sage: K2 = K1.extension(y^2 - a, 'b')
3833             sage: OK2 = K2.order(K2.gen()) # (not maximal)
3834             sage: b = OK2.gens()[1]; b
3835             b
3836             sage: (17/b).parent() is K2 # indirect doctest
3837             True
3838             sage: (17/b) in OK2 # indirect doctest
3839             True
3840             sage: (17/b^7) in OK2 # indirect doctest
3841             False
3842         """     
3843         cdef NumberFieldElement_relative x 
3844         x = NumberFieldElement_relative._div_(self, other)
3845         return self._parent.number_field()(x)
3846 
3847     def __invert__(self):
3848         r"""
3849         Implement division, checking that the result has the right parent.
3850         See trac #4190.
3851         
3852         EXAMPLES::
3853         
3854             sage: K1.<a> = NumberField(x^3 - 17)
3855             sage: R.<y> = K1[]
3856             sage: K2 = K1.extension(y^2 - a, 'b')
3857             sage: OK2 = K2.order(K2.gen()) # (not maximal)
3858             sage: b = OK2.gens()[1]; b
3859             b
3860             sage: b.parent() is OK2
3861             True
3862             sage: (~b).parent() is K2
3863             True
3864             sage: (~b) in OK2 # indirect doctest
3865             False
3866             sage: b**(-1) in OK2 # indirect doctest
3867             False
3868         """
3869         return self._parent.number_field()(NumberFieldElement_relative.__invert__(self))
3870 
3871     def inverse_mod(self, I):
3872         r""" 
3873         Return an inverse of self modulo the given ideal.
3874         
3875         INPUT:
3876 
3877 
3878         -  ``I`` - may be an ideal of self.parent(), or an
3879            element or list of elements of self.parent() generating a nonzero
3880            ideal. A ValueError is raised if I is non-integral or is zero. 
3881            A ZeroDivisionError is raised if I + (x) != (1).
3882 
3883                 
3884         EXAMPLES::
3885         
3886             sage: E.<a,b> = NumberField([x^2 - x + 2, x^2 + 1])
3887             sage: OE = E.ring_of_integers()
3888             sage: t = OE(b - a).inverse_mod(17*b)
3889             sage: t*(b - a) - 1 in E.ideal(17*b)
3890             True
3891             sage: t.parent() == OE
3892             True
3893         """
3894         R = self.parent()
3895         return R(_inverse_mod_generic(self, I))
3896 
3897     def charpoly(self, var='x'):
3898         r"""
3899         The characteristic polynomial of this order element over its base ring.
3900 
3901         This special implementation works around bug \#4738.  At this
3902         time the base ring of relative order elements is ZZ; it should
3903         be the ring of integers of the base field.
3904 
3905         EXAMPLES::
3906         
3907             sage: x = ZZ['x'].0
3908             sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3909             sage: OK = K.maximal_order(); OK.basis()
3910             [1, 1/2*a - 1/2*b, -1/2*b*a + 1/2, a]
3911             sage: charpoly(OK.1)
3912             x^2 + b*x + 1
3913             sage: charpoly(OK.1).parent()
3914             Univariate Polynomial Ring in x over Maximal Order in Number Field in b with defining polynomial x^2 - 3
3915             sage: [ charpoly(t) for t in OK.basis() ]
3916             [x^2 - 2*x + 1, x^2 + b*x + 1, x^2 - x + 1, x^2 + 1]
3917         """
3918         R = self.parent().number_field().base_field().ring_of_integers()[var]
3919         return R(self.matrix().charpoly(var))
3920 
3921     def minpoly(self, var='x'):
3922         r"""
3923         The minimal polynomial of this order element over its base ring.
3924 
3925         This special implementation works around bug \#4738.  At this
3926         time the base ring of relative order elements is ZZ; it should
3927         be the ring of integers of the base field.
3928 
3929         EXAMPLES::
3930         
3931             sage: x = ZZ['x'].0
3932             sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3933             sage: OK = K.maximal_order(); OK.basis()
3934             [1, 1/2*a - 1/2*b, -1/2*b*a + 1/2, a]
3935             sage: minpoly(OK.1)
3936             x^2 + b*x + 1
3937             sage: charpoly(OK.1).parent()
3938             Univariate Polynomial Ring in x over Maximal Order in Number Field in b with defining polynomial x^2 - 3
3939             sage: _, u, _, v = OK.basis()
3940             sage: t = 2*u - v; t
3941             -b
3942             sage: t.charpoly()
3943             x^2 + 2*b*x + 3
3944             sage: t.minpoly()
3945             x + b
3946 
3947             sage: t.absolute_charpoly()
3948             x^4 - 6*x^2 + 9
3949             sage: t.absolute_minpoly()
3950             x^2 - 3
3951         """
3952         K = self.parent().number_field()
3953         R = K.base_field().ring_of_integers()[var]
3954         return R(K(self).minpoly(var))
3955 
3956     def absolute_charpoly(self, var='x'):
3957         r"""
3958         The absolute characteristic polynomial of this order element over ZZ.
3959 
3960         EXAMPLES::
3961         
3962             sage: x = ZZ['x'].0
3963             sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3964             sage: OK = K.maximal_order()
3965             sage: _, u, _, v = OK.basis()
3966             sage: t = 2*u - v; t
3967             -b
3968             sage: t.absolute_charpoly()
3969             x^4 - 6*x^2 + 9
3970             sage: t.absolute_minpoly()
3971             x^2 - 3
3972             sage: t.absolute_charpoly().parent()
3973             Univariate Polynomial Ring in x over Integer Ring
3974         """
3975         K = self.parent().number_field()
3976         R = ZZ[var]
3977         return R(K(self).absolute_charpoly(var))
3978 
3979     def absolute_minpoly(self, var='x'):
3980         r"""
3981         The absolute minimal polynomial of this order element over ZZ.
3982 
3983         EXAMPLES::
3984         
3985             sage: x = ZZ['x'].0
3986             sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3987             sage: OK = K.maximal_order()
3988             sage: _, u, _, v = OK.basis()
3989             sage: t = 2*u - v; t
3990             -b
3991             sage: t.absolute_charpoly()
3992             x^4 - 6*x^2 + 9
3993             sage: t.absolute_minpoly()
3994             x^2 - 3
3995             sage: t.absolute_minpoly().parent()
3996             Univariate Polynomial Ring in x over Integer Ring
3997         """
3998         K = self.parent().number_field()
3999         R = ZZ[var]
4000         return R(K(self).absolute_minpoly(var))
4001 
4002 
4003 
4004 class CoordinateFunction:
4005     r"""
4006     This class provides a callable object which expresses 
4007     elements in terms of powers of a fixed field generator `\alpha`.
4008     
4009     EXAMPLE::
4010     
4011         sage: K.<a> = NumberField(x^2 + x + 3)
4012         sage: f = (a + 1).coordinates_in_terms_of_powers(); f
4013         Coordinate function that writes elements in terms of the powers of a + 1
4014         sage: f.__class__
4015         <class sage.rings.number_field.number_field_element.CoordinateFunction at ...>
4016         sage: f(a)
4017         [-1, 1]
4018         sage: f == loads(dumps(f))
4019         True
4020     """
4021     def __init__(self, NumberFieldElement alpha, W, to_V):
4022         r"""
4023         EXAMPLE::
4024         
4025             sage: K.<a> = NumberField(x^2 + x + 3)
4026             sage: f = (a + 1).coordinates_in_terms_of_powers(); f # indirect doctest
4027             Coordinate function that writes elements in terms of the powers of a + 1
4028         """
4029         self.__alpha = alpha
4030         self.__W = W
4031         self.__to_V = to_V
4032         self.__K = alpha.number_field()
4033 
4034     def __repr__(self):
4035         r"""
4036         EXAMPLE::
4037         
4038             sage: K.<a> = NumberField(x^2 + x + 3)
4039             sage: f = (a + 1).coordinates_in_terms_of_powers(); repr(f) # indirect doctest
4040             'Coordinate function that writes elements in terms of the powers of a + 1'
4041         """
4042         return "Coordinate function that writes elements in terms of the powers of %s"%self.__alpha
4043 
4044     def alpha(self):
4045         r"""
4046         EXAMPLE::
4047         
4048             sage: K.<a> = NumberField(x^3 + 2)
4049             sage: (a + 2).coordinates_in_terms_of_powers().alpha()
4050             a + 2
4051         """
4052         return self.__alpha
4053 
4054     def __call__(self, x):
4055         r"""
4056         EXAMPLE::
4057         
4058             sage: K.<a> = NumberField(x^3 + 2)
4059             sage: f = (a + 2).coordinates_in_terms_of_powers()
4060             sage: f(1/a)
4061             [-2, 2, -1/2]
4062             sage: f(ZZ(2))
4063             [2, 0, 0]
4064             sage: L.<b> = K.extension(x^2 + 7)
4065             sage: g = (a + b).coordinates_in_terms_of_powers()
4066             sage: g(a/b)
4067             [-3379/5461, -371/10922, -4125/38227, -15/5461, -14/5461, -9/76454]
4068             sage: g(a)
4069             [4459/10922, -4838/5461, -273/5461, -980/5461, -9/10922, -42/5461]
4070             sage: f(b)
4071             Traceback (most recent call last):
4072             ...
4073             TypeError: Cannot coerce element into this number field
4074         """
4075         return self.__W.coordinates(self.__to_V(self.__K(x)))
4076     
4077     def __cmp__(self, other):
4078         r"""
4079         EXAMPLE::
4080         
4081             sage: K.<a> = NumberField(x^4 + 1)
4082             sage: f = (a + 1).coordinates_in_terms_of_powers()
4083             sage: f == loads(dumps(f))
4084             True
4085             sage: f == (a + 2).coordinates_in_terms_of_powers()
4086             False
4087             sage: f == NumberField(x^2 + 3,'b').gen().coordinates_in_terms_of_powers()
4088             False
4089         """
4090         return cmp(self.__class__, other.__class__) or cmp(self.__K, other.__K) or cmp(self.__alpha, other.__alpha)
4091 
4092 
4093 
4094 #################
4095 
4096 cdef void _ntl_poly(f, ZZX_c *num, ZZ_c *den):
4097     cdef long i
4098     cdef ZZ_c coeff
4099     cdef ntl_ZZX _num
4100     cdef ntl_ZZ _den
4101 
4102     __den = f.denominator()
4103     (<Integer>ZZ(__den))._to_ZZ(den)
4104 
4105     __num = f * __den
4106     for i from 0 <= i <= __num.degree():
4107         (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
4108         ZZX_SetCoeff( num[0], i, coeff )
4109 
4110     

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
  • [get | view] (2010-12-09 19:01:33, 1.4 KB) [[attachment:Code]]
  • [get | view] (2010-12-07 22:19:28, 232.8 KB) [[attachment:Stange-SageDays-2010.pdf]]
  • [get | view] (2010-12-09 19:02:39, 1.4 KB) [[attachment:code.sws]]
  • [get | view] (2010-12-10 18:11:31, 134.2 KB) [[attachment:number_field_element.pyx]]
  • [get | view] (2010-12-10 18:11:05, 97.1 KB) [[attachment:number_field_ideal.py]]
  • [get | view] (2010-12-10 19:12:52, 4.1 KB) [[attachment:residue_symbol_test.sws]]
  • [get | view] (2010-12-10 18:22:04, 6.1 KB) [[attachment:test_failed.txt]]
 All files | Selected Files: delete move to page copy to page

You are not allowed to attach a file to this page.