Optimized Quadratic Number Field Elements

This file defines a Cython class NumberFieldElement_quadratic to speed up computations in quadratic extensions of \QQ.

AUTHORS:

  • Robert Bradshaw (2007-09): Initial version
  • David Harvey (2007-10): fix up a few bugs, polish around the edges
  • David Loeffler (2009-05): add more documentation and tests

TODO:

The _new() method should be overridden in this class to copy the D attribute
class sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic

A NumberFieldElement_quadratic object gives an efficient representation of an element of a quadratic extension of \QQ.

Elements are represented internally as triples (a, b, c) of integers, where {\rm gcd}(a, b, c) = 1 and c > 0, representing the element (a +
b \sqrt{D}) / c. Note that if the discriminant D is 1 \bmod 4, integral elements do not necessarily have c = 1.

TESTS:

sage: from sage.rings.number_field.number_field_element_quadratic import NumberFieldElement_quadratic

We set up some fields:

sage: K.<a> = NumberField(x^2+23)
sage: a.parts()
(0, 1)
sage: F.<b> = NumberField(x^2-x+7)
sage: b.parts()
(1/2, 3/2)

We construct elements of these fields in various ways - firstly, from polynomials:

sage: NumberFieldElement_quadratic(K, x-1)
a - 1
sage: NumberFieldElement_quadratic(F, x-1)
b - 1

From triples of Integers:

sage: NumberFieldElement_quadratic(K, (1,2,3))
2/3*a + 1/3
sage: NumberFieldElement_quadratic(F, (1,2,3))
4/9*b + 1/9
sage: NumberFieldElement_quadratic(F, (1,2,3)).parts()
(1/3, 2/3)

From pairs of Rationals:

sage: NumberFieldElement_quadratic(K, (1/2,1/3))
1/3*a + 1/2
sage: NumberFieldElement_quadratic(F, (1/2,1/3))
2/9*b + 7/18
sage: NumberFieldElement_quadratic(F, (1/2,1/3)).parts()
(1/2, 1/3)

Direct from Rationals:

sage: NumberFieldElement_quadratic(K, 2/3)
2/3
sage: NumberFieldElement_quadratic(F, 2/3)
2/3

This checks a bug when converting from lists:

sage: w = CyclotomicField(3)([1/2,1])
sage: w == w.__invert__().__invert__()
True
__abs__()

EXAMPLES:

sage: K.<a> = NumberField(x^2+1, embedding=CDF.gen())
sage: abs(a+1)
sqrt(2)
__copy__()

Returns a new copy of self.

TESTS:

sage: K.<a> = QuadraticField(-3)
sage: b = a + 3
sage: c = b.__copy__()
sage: b
a + 3
sage: c
a + 3
sage: b is c
False
sage: b == c
True
__eq__()
x.__eq__(y) <==> x==y
__ge__()
x.__ge__(y) <==> x>=y
__gt__()
x.__gt__(y) <==> x>y
__hash__()
x.__hash__() <==> hash(x)
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__invert__()
EXAMPLES:
sage: K.<a> = NumberField(x^2-5) sage: ~a 1/5*a sage: ~(a+1) 1/4*a - 1/4 sage: (a-1)*(a+1) 4 sage: b = ~(5*a-3); b 5/116*a + 3/116 sage: b*(5*a-3) 1 sage: b = ~((3*a-2)/7); b 21/41*a + 14/41 sage: (3*a-2)/7 * b 1
__le__()
x.__le__(y) <==> x<=y
__lt__()
x.__lt__(y) <==> x<y
__ne__()
x.__ne__(y) <==> x!=y
__neg__()

EXAMPLES:

sage: K.<a> = NumberField(x^2+163)
sage: -a
-a
sage: -(a+4)
-a - 4
sage: b = (a-3)/2
sage: -b
-1/2*a + 3/2
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
__nonzero__()
x.__nonzero__() <==> x != 0
__reduce__()

Used for pickling.

TEST:

sage: K.<a> = NumberField(x^2-13) sage: loads(dumps(a)) == a True sage: loads(dumps(a/3+5)) == a/3+5 True
_add_()
EXAMPLES:
sage: K.<a> = NumberField(x^2-5) sage: K.discriminant() 5 sage: a+a # indirect doctest 2*a sage: s = (a+2)/6; s 1/6*a + 1/3 sage: s+a 7/6*a + 1/3 sage: s+10 1/6*a + 31/3 sage: s+(2*a+5)/7 19/42*a + 22/21 sage: s+(1+a)/2 2/3*a + 5/6 sage: s+(1+a)/8 7/24*a + 11/24 sage: s+(a+5)/6 1/3*a + 7/6 sage: (a/3+2/3) + (2*a/3+1/3) a + 1
_coefficients()
EXAMPLES:
sage: K.<a> = NumberField(x^2+41) sage: a._coefficients() [0, 1] sage: K.<a> = NumberField(x^2+x+41) sage: a._coefficients() [0, 1] sage: b = 3*a+1/5 sage: b._coefficients() [1/5, 3]
_div_()
EXAMPLES:
sage: K.<a> = NumberField(x^2-5) sage: 2/a # indirect doctest 2/5*a sage: (a+2)/(a+1) 1/4*a + 3/4 sage: (a+1)*(a+2)/(a+1) a + 2 sage: (a+1/3)*(5*a+2/7)/(a+1/3) 5*a + 2/7
_integer_()
EXAMPLES:
sage: K.<a> = NumberField(x^2+163) sage: (a+1-a)._integer_() 1 sage: (a+1/2-a)._integer_() Traceback (most recent call last): ... TypeError: Unable to coerce 1/2 to an integer
_lift_cyclotomic_element()

Creates an element of the passed field from this field. This is specific to creating elements in a cyclotomic field from elements in another cyclotomic field, in the case that self.number_field()._n() divides new_parent()._n(). This function aims to make this common coercion extremely fast!

More general coercion (i.e. of zeta6 into CyclotomicField(3)) is implemented in the _coerce_from_other_cyclotomic_field method of a CyclotomicField.

EXAMPLES:

sage: C.<zeta4>=CyclotomicField(4)
sage: CyclotomicField(20)(zeta4+1)  # The function _lift_cyclotomic_element does the heavy lifting in the background
zeta20^5 + 1
sage: (zeta4+1)._lift_cyclotomic_element(CyclotomicField(40))  # There is rarely a purpose to call this function directly
zeta40^10 + 1

sage: cf3 = CyclotomicField(3) ; z3 = cf3.0
sage: cf6 = CyclotomicField(6) ; z6 = cf6.0
sage: z6._lift_cyclotomic_element(cf3)
...
TypeError: The zeta_order of the new field must be a multiple of the zeta_order of the original.
sage: cf3(z6)
zeta3 + 1
sage: z3._lift_cyclotomic_element(cf6)
zeta6 - 1

AUTHOR:

  • Joel B. Mohler (original version)
  • Craig Citro (reworked for quadratic elements)
_lmul_()
EXAMPLE:
sage: K.<a> = NumberField(x^2+43) sage: 5*(a-1/5) # indirect doctest 5*a - 1
_maxima_init_()

EXAMPLES:

sage: K.<a> = QuadraticField(-1)
sage: f = 1 + a
sage: f._maxima_init_()
'1+%i*1'
_mul_()
EXAMPLES:
sage: K.<a> = NumberField(x^2+23) sage: a*a # indirect doctest -23 sage: (a+1)*(a-1) -24 sage: (a+1)*(a+2) 3*a - 21 sage: (a+1)/2 * (a+2) 3/2*a - 21/2 sage: (a+1)/2 * (a+2)/3 1/2*a - 7/2 sage: (2*a+4) * (3*a)/2 6*a - 69
Verify Karatsuba
sage: K.<a> = NumberField(x^2-41) sage: (10^1000 * (a+1)) * K(2+3*a) == 10^1000 * ((a+1) * K(2+3*a)) True
_rational_()
EXAMPLES:
sage: K.<a> = NumberField(x^2+163) sage: (a+1/2-a)._rational_() 1/2 sage: (a+1/2)._rational_() Traceback (most recent call last): ... TypeError: Unable to coerce a + 1/2 to a rational
_rmul_()
EXAMPLE:
sage: K.<a> = NumberField(x^2+43) sage: (1+a)*3 # indirect doctest 3*a + 3
_sub_()
EXAMPLES:
sage: K.<a> = NumberField(x^2-13) sage: b = (a-3)/10; b # indirect doctest 1/10*a - 3/10 sage: b-1 1/10*a - 13/10 sage: b-a -9/10*a - 3/10 sage: b-1/2 1/10*a - 4/5 sage: b-a/15 1/30*a - 3/10
charpoly()

The characteristic polynomial of this element over \QQ.

EXAMPLES:

sage: K.<a> = NumberField(x^2-x+13)
sage: a.charpoly()
x^2 - x + 13
sage: b = 3-a/2
sage: f = b.charpoly(); f
x^2 - 11/2*x + 43/4
sage: f(b)
0
denominator()

Return the denominator of self. This is the LCM of the denominators of the coefficients of self, and thus it may well be > 1 even when the element is an algebraic integer.

EXAMPLES:

sage: K.<a> = NumberField(x^2+x+41)
sage: a.denominator()
1
sage: b = (2*a+1)/6
sage: b.denominator()
6
sage: K(1).denominator()
1
sage: K(1/2).denominator()
2
sage: K(0).denominator()
1

sage: K.<a> = NumberField(x^2 - 5)
sage: b = (a + 1)/2
sage: b.denominator()
2
sage: b.is_integral()
True
imag()

Returns the imaginary part of self.

EXAMPLES:

sage: K.<sqrt2> = QuadraticField(2)
sage: sqrt2.imag()
0
sage: parent(sqrt2.imag())
Rational Field

sage: K.<i> = QuadraticField(-1)
sage: i.imag()
1
sage: parent(i.imag())
Rational Field

sage: K.<a> = NumberField(x^2 + x + 1, embedding=CDF.0)
sage: a.imag()
1/2*sqrt3
sage: a.real()
-1/2
sage: SR(a)
1/2*I*sqrt(3) - 1/2
sage: bool(I*a.imag() + a.real() == a)
True

TESTS:

sage: K.<a> = QuadraticField(-9, embedding=-CDF.0)
sage: a.imag()
-3
sage: parent(a.imag())
Rational Field
is_integral()

Returns whether this element is an algebraic integer.

TESTS:

sage: K.<a> = QuadraticField(-1)
sage: a.is_integral()
True
sage: K(1).is_integral()
True
sage: K(1/2).is_integral()
False
sage: K(a/2).is_integral()
False
sage: K((a+1)/2).is_integral()
False
sage: K(a/3).is_integral()
False

sage: K.<a> = QuadraticField(-3)
sage: a.is_integral()
True
sage: K(1).is_integral()
True
sage: K(1/2).is_integral()
False
sage: K(a/2).is_integral()
False
sage: ((a+1)/2).is_integral()
True
minpoly()

The minimal polynomial of this element over \QQ.

EXAMPLES:

sage: K.<a> = NumberField(x^2+13)
sage: a.minpoly()
x^2 + 13
sage: (a+1/2-a).minpoly()
x - 1/2        
norm()

Return the norm of self. If the second argument is None, this is the norm down to \QQ. Otherwise, return the norm down to K (which had better be either \QQ or this number field).

EXAMPLES:

sage: K.<a> = NumberField(x^2-x+3)
sage: a.norm()
3
sage: a.matrix()
[ 0  1]
[-3  1]
sage: K.<a> = NumberField(x^2+5)
sage: (1+a).norm()
6

The norm is multiplicative:

sage: K.<a> = NumberField(x^2-3)
sage: a.norm()
-3
sage: K(3).norm()
9
sage: (3*a).norm()
-27

We test that the optional argument is handled sensibly:

sage: (3*a).norm(QQ)
-27
sage: (3*a).norm(K)
3*a
sage: (3*a).norm(CyclotomicField(3))
...
ValueError: no way to embed L into parent's base ring K
parts()

This function returns a pair of rationals a and b such that self =
a+b\sqrt{D}.

This is much closer to the internal storage format of the elements than the polynomial representation coefficients (the output of self.list()), unless the generator with which this number field was constructed was equal to \sqrt{D}. See the last example below.

EXAMPLES:

sage: K.<a> = NumberField(x^2-13)
sage: K.discriminant()
13
sage: a.parts()
(0, 1)
sage: (a/2-4).parts()
(-4, 1/2)
sage: K.<a> = NumberField(x^2-7)
sage: K.discriminant()
28
sage: a.parts()
(0, 1)
sage: K.<a> = NumberField(x^2-x+7)
sage: a.parts()
(1/2, 3/2)
sage: a._coefficients()
[0, 1]                    
real()

Returns the real part of self, which is either self (if self lives it a totally real field) or a rational number.

EXAMPLES:

sage: K.<sqrt2> = QuadraticField(2)
sage: sqrt2.real()
sqrt2
sage: K.<a> = QuadraticField(-3)
sage: a.real()
0
sage: (a + 1/2).real()
1/2
sage: K.<a> = NumberField(x^2 + x + 1)
sage: a.real()
-1/2
sage: parent(a.real())
Rational Field
sage: K.<i> = QuadraticField(-1)
sage: i.real()
0
trace()

EXAMPLES:

sage: K.<a> = NumberField(x^2+x+41)
sage: a.trace()
-1
sage: a.matrix()
[  0   1]
[-41  -1]

The trace is additive:

sage: K.<a> = NumberField(x^2+7)
sage: (a+1).trace()
2
sage: K(3).trace()
6
sage: (a+4).trace()
8
sage: (a/3+1).trace()
2
class sage.rings.number_field.number_field_element_quadratic.OrderElement_quadratic

Element of an order in a quadratic field.

EXAMPLES:

sage: K.<a> = NumberField(x^2 + 1)
sage: O2 = K.order(2*a)
sage: w = O2.1; w
2*a
sage: parent(w)
Order in Number Field in a with defining polynomial x^2 + 1
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__invert__()

Implement inversion, checking that the return value has the right parent. See trac #4190.

EXAMPLES:

sage: K = NumberField(x^2 -x + 2, 'a')
sage: OK = K.ring_of_integers()
sage: a = OK(K.gen())
sage: (~a).parent() is K
True
sage: (~a) in OK
False
sage: a**(-1) in OK
False
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
_div_()

Implement division, checking that the result has the right parent. It’s not so crucial what the parent actually is, but it is crucial that the returned value really is an element of its supposed parent! This fixes trac #4190.

EXAMPLES:

sage: K = NumberField(x^2 - 17, 'a')
sage: OK = K.ring_of_integers()
sage: a = OK(K.gen())
sage: (17/a).parent() is K # indirect doctest
True
sage: 17/a in OK
True
sage: (17/(2*a)).parent() is OK
False
sage: (17/(2*a)) in OK
False
sage: (17/(2*a)).parent() is K
True
_lmul_()
EXAMPLE:
sage: K.<a> = NumberField(x^2+43) sage: R = K.ring_of_integers() sage: aa = R.gen(0); aa 1/2*a + 1/2 sage: aa*3 # indirect doctest 3/2*a + 3/2
_rmul_()
EXAMPLE:
sage: K.<a> = NumberField(x^2-27) sage: R = K.ring_of_integers() sage: aa = R.gen(1); aa 1/3*a sage: 5 * aa # indirect doctest 5/3*a
charpoly()

The characteristic polynomial of this element, which is over \ZZ because this element is an algebraic integer.

EXAMPLES:

sage: K.<a> = NumberField(x^2 - 5)
sage: R = K.ring_of_integers()
sage: b = R((5+a)/2)
sage: f = b.charpoly('x'); f
x^2 - 5*x + 5
sage: f.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: f(b)
0
inverse_mod()

Return an inverse of self modulo the given ideal.

EXAMPLES:

sage: OE = QuadraticField(-7, 's').ring_of_integers()
sage: w = OE.ring_generators()[0]
sage: w.inverse_mod(13) + (7*w + 6) in 13*OE
True
sage: w.inverse_mod(2*OE)
...
ZeroDivisionError: 1/2*s + 1/2 is not invertible modulo Fractional ideal (2)
minpoly()

The minimal polynomial of this element over \ZZ.

EXAMPLES:

sage: K.<a> = NumberField(x^2 + 163)
sage: R = K.ring_of_integers()
sage: f = R(a).minpoly('x'); f
x^2 + 163
sage: f.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: R(5).minpoly()
x - 5
norm()

The norm of an element of the ring of integers is an Integer.

EXAMPLES:

sage: K.<a> = NumberField(x^2 + 3)
sage: O2 = K.order(2*a)
sage: w = O2.gen(1); w
2*a
sage: w.norm()
12
sage: parent(w.norm())
Integer Ring
trace()

The trace of an element of the ring of integers is an Integer.

EXAMPLES:

sage: K.<a> = NumberField(x^2 - 5)
sage: R = K.ring_of_integers()
sage: b = R((1+a)/2)
sage: b.trace()
1
sage: parent(b.trace())
Integer Ring
class sage.rings.number_field.number_field_element_quadratic.Q_to_quadratic_field_element

Morphism that coerces from rationals to elements of a quadratic number field K.

__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
_call_()

Evaluate at a rational x.

EXAMPLE:

sage: K.<a> = QuadraticField(3)
sage: phi = K.coerce_map_from(QQ)
sage: a = phi(2/3); a # indirect doctest
2/3
sage: a.parent() is K
True
_repr_type()

Return a short name for this morphism.

EXAMPLE:

sage: K.<a> = QuadraticField(3)
sage: phi = K.coerce_map_from(QQ)
sage: repr(phi) # indirect doctest
'Natural morphism:\n  From: Rational Field\n  To:   Number Field in a with defining polynomial x^2 - 3'
sage.rings.number_field.number_field_element_quadratic.__make_NumberFieldElement_quadratic0()

Used in unpickling elements of number fields.

TEST:

sage: K.<a> = NumberField(x^2-x+13)
sage: loads(dumps(a)) == a # indirect doctest
True
sage.rings.number_field.number_field_element_quadratic.__make_NumberFieldElement_quadratic1()

Used in unpickling elements of number fields.

TEST:

sage: K.<a> = NumberField(x^2-x+13)
sage: loads(dumps(a)) == a # indirect doctest
True

We test that #6462 is fixed:

sage: L = QuadraticField(-11,'a'); OL = L.maximal_order(); w = OL.0
sage: loads(dumps(w)) == w # indirect doctest
True

Previous topic

Number Field Elements

Next topic

Orders in Number Fields

This Page