source: sage/rings/finite_field_element.py @ 3309:978bc4ff9c23

Revision 3309:978bc4ff9c23, 18.0 KB checked in by David Roe <roed@…>, 6 years ago (diff)

merge
Line 
1"""
2Elements of Finite Fields
3
4EXAMPLES:
5    sage: K = FiniteField(2)
6    sage: V = VectorSpace(K,3)
7    sage: w = V([0,1,2])
8    sage: K(1)*w
9    (0, 1, 0)
10"""
11
12
13import operator
14
15import sage.structure.element as element
16import arith
17import integer_ring
18from integer import Integer
19import rational
20from sage.libs.all import pari, pari_gen
21from sage.structure.element import FiniteFieldElement
22import field_element
23import integer_mod
24import ring
25
26def is_FiniteFieldElement(x):
27    """
28    Returns if x is a finite field element.
29
30    EXAMPLE:
31        sage: is_FiniteFieldElement(1)
32            False
33        sage: is_FiniteFieldElement(IntegerRing())
34            False
35        sage: is_FiniteFieldElement(GF(5)(2))
36            True
37       
38    """
39    return isinstance(x, element.Element) and ring.is_FiniteField(x.parent())
40
41class FiniteField_ext_pariElement(FiniteFieldElement):
42    """
43    An element of a finite field.
44
45    Create elements by first defining the finite field F, then use
46    the notation F(n), for n an integer. or let a = F.gen() and
47    write the element in terms of a.
48
49    EXAMPLES:
50        sage: from sage.rings.finite_field import FiniteField_ext_pari
51        sage: K = FiniteField_ext_pari(10007^10, 'a')
52        sage: a = K.gen(); a
53        a
54        sage: loads(a.dumps()) == a
55        True
56        sage: K = GF(10007)
57        sage: a = K(938); a
58        938
59        sage: loads(a.dumps()) == a
60        True
61    """
62    def __init__(self, parent, value):
63        """
64        Create element of a finite field.
65
66        EXAMPLES:
67            sage: from sage.rings.finite_field import FiniteField_ext_pari
68            sage: k = FiniteField_ext_pari(9,'a')
69            sage: a = k(11); a
70            2
71            sage: a.parent()
72            Finite Field in a of size 3^2
73        """
74        field_element.FieldElement.__init__(self, parent)
75        self.__parent = parent
76        if isinstance(value, str):
77            raise TypeError, "value must not be a string"
78        try:
79            if isinstance(value, pari_gen):
80                if value.type()[-3:] == "MOD" :
81                    self.__value = value
82                else:
83                    try:
84                        self.__value = value.Mod(parent._pari_modulus())*parent._pari_one()
85                    except RuntimeError:
86                        raise TypeError, "no possible coercion implemented"
87                return
88            elif isinstance(value, FiniteField_ext_pariElement):
89                if parent != value.parent():
90                    raise TypeError, "no coercion implemented"
91                else:
92                    self.__value = value.__value
93                    return
94            try:
95                self.__value = pari(value).Mod(parent._pari_modulus())*parent._pari_one()
96            except RuntimeError:
97                raise TypeError, "no coercion implemented"
98
99        except (AttributeError, TypeError):
100            raise TypeError, "unable to coerce"
101
102    def __hash__(self):
103        return hash(self.polynomial())
104
105    def polynomial(self):
106        """
107        Elements of a finite field are represented as a polynomial
108        modulo a modulus.  This functions returns the representing
109        polynomial as an element of the polynomial ring over the prime
110        finite field, with the same variable as the finite field.
111       
112        EXAMPLES:
113        The default variable is a:
114            sage: from sage.rings.finite_field import FiniteField_ext_pari
115            sage: k = FiniteField_ext_pari(3**2,'a')
116            sage: k.gen().polynomial()
117            a
118           
119        The variable can be any string.
120            sage: k = FiniteField(3**4, "alpha")
121            sage: a = k.gen()
122            sage: a.polynomial()
123            alpha
124            sage: (a**2 + 1).polynomial()
125            alpha^2 + 1
126            sage: (a**2 + 1).polynomial().parent()
127            Univariate Polynomial Ring in alpha over Finite Field of size 3
128        """
129        return self.parent().polynomial_ring()(self.__value.lift())
130
131    def is_square(self):
132        """
133        Returns True if and only if this element is a perfect square.
134
135        EXAMPLES:
136            sage: from sage.rings.finite_field import FiniteField_ext_pari
137            sage: k = FiniteField_ext_pari(3**2, 'a')
138            sage: a = k.gen()
139            sage: a.is_square()
140            False
141            sage: (a**2).is_square()
142            True
143            sage: k = FiniteField_ext_pari(2**2,'a')
144            sage: a = k.gen()
145            sage: (a**2).is_square()
146            True
147            sage: k = FiniteField_ext_pari(17**5,'a'); a = k.gen()
148            sage: (a**2).is_square()
149            True
150            sage: a.is_square()
151            False
152
153            sage: k(0).is_square()
154            True
155        """
156        K = self.parent()
157        if K.characteristic() == 2:
158            return True
159        n = K.order() - 1
160        a = self**(n // 2)
161        return a == 1 or a == 0
162
163    def square_root(self):
164        """
165        Return a square root of this finite field element in its
166        finite field, if there is one.  Otherwise, raise a ValueError.
167
168        EXAMPLES:
169          sage: from sage.rings.finite_field import FiniteField_ext_pari
170          sage: F = FiniteField_ext_pari(7^2, 'a')
171          sage: F(2).square_root()
172          4
173          sage: F(3).square_root()
174          5*a + 1
175          sage: F(3).square_root()**2
176          3
177          sage: F(4).square_root()
178          5
179          sage: K = FiniteField_ext_pari(7^3, 'alpha')
180          sage: K(3).square_root()
181          Traceback (most recent call last):
182          ...
183          ValueError: must be a perfect square.
184
185        """
186        R = self.parent()['x']
187        f = R([-self, 0, 1])
188        g = f.factor()
189        if len(g) == 2 or g[0][1] == 2:
190            return -g[0][0][0]
191        raise ValueError, "must be a perfect square."
192
193    def sqrt(self):
194        """
195        See self.square_root().
196        """
197        return self.square_root()
198       
199       
200    def rational_reconstruction(self):
201        """
202        If the parent field is a prime field, uses rational reconstruction to
203        try to find a lift of this element to the rational numbers.
204
205        EXAMPLES:
206            sage: from sage.rings.finite_field import FiniteField_ext_pari
207            sage: k = GF(97)
208            sage: a = k(RationalField()('2/3'))
209            sage: a
210            33
211            sage: a.rational_reconstruction()
212            2/3
213        """
214        if self.parent().degree() != 1:
215            raise ArithmeticError, "finite field must be prime"
216        t = arith.rational_reconstruction(int(self), self.parent().characteristic())
217        if t == None or t[1] == 0:
218            raise ZeroDivisionError, "unable to compute rational reconstruction"
219        return rational.Rational((t[0],t[1]))
220
221    def multiplicative_order(self):
222        r"""
223        Returns the \emph{multiplicative} order of this element, which
224        must be nonzero.
225
226        EXAMPLES:
227            sage: from sage.rings.finite_field import FiniteField_ext_pari
228            sage: a = FiniteField_ext_pari(5**3, 'a').0
229            sage: a.multiplicative_order()
230            124
231            sage: a**124
232            1
233        """
234        try:
235            return self.__multiplicative_order
236        except AttributeError:
237            if self.is_zero():
238                return ArithmeticError, "Multiplicative order of 0 not defined."
239            n = self.parent().order() - 1
240            order = 1
241            for p, e in arith.factor(n):
242                # Determine the power of p that divides the order.
243                a = self**(n//(p**e))
244                while a != 1:
245                    order *= p
246                    a = a**p
247            self.__multiplicative_order = order
248            return order
249   
250    def copy(self):
251        """
252        Return a copy of this element.
253
254        EXAMPLES:
255            sage: from sage.rings.finite_field import FiniteField_ext_pari
256            sage: k = FiniteField_ext_pari(3**3,'a')
257            sage: a = k(5)
258            sage: a
259            2
260            sage: a.copy()
261            2
262            sage: b = a.copy()
263            sage: a == b
264            True
265            sage: a is b
266            False
267            sage: a is a
268            True
269        """
270        return FiniteField_ext_pariElement(self.__parent, self.__value)
271
272    def _pari_(self, var=None):
273        """
274        Return PARI object corresponding to this finite field element.
275
276        EXAMPLES:
277            sage: from sage.rings.finite_field import FiniteField_ext_pari
278            sage: k = FiniteField_ext_pari(3**3, 'a')
279            sage: a = k.gen()
280            sage: b = a**2 + 2*a + 1
281            sage: b._pari_()
282            Mod(Mod(1, 3)*a^2 + Mod(2, 3)*a + Mod(1, 3), Mod(1, 3)*a^3 + Mod(2, 3)*a + Mod(1, 3))
283
284        Looking at the PARI representation of a finite field element, it's no wonder people
285        find PARI difficult to work with directly.  Compare our representation:
286       
287            sage: b
288            a^2 + 2*a + 1
289            sage: b.parent()
290            Finite Field in a of size 3^3
291        """
292        if var is None:
293            var = self.parent().variable_name()
294        if var == 'a':
295            return self.__value
296        else:
297            return self.__value.subst('a', var)
298       
299    def _pari_init_(self):
300        return str(self.__value)
301
302    def _gap_init_(self):
303        """
304        Supports returning corresponding GAP object.  This can be slow
305        since non-prime GAP finite field elements are represented as
306        powers of a generator for the multiplicative group, so the
307        discrete log problem must be solved.
308
309        \note{The order of the parent field must be $\leq 65536$.}
310       
311       
312        EXAMPLES:
313            sage: from sage.rings.finite_field import FiniteField_ext_pari
314            sage: F = FiniteField_ext_pari(8,'a')
315            sage: a = F.multiplicative_generator()
316            sage: gap(a)
317            Z(2^3)
318            sage: b = F.multiplicative_generator()
319            sage: a = b^3
320            sage: gap(a)
321            Z(2^3)^3
322            sage: gap(a^3)
323            Z(2^3)^2
324
325        You can specify the instance of the Gap interpreter that is used:
326       
327            sage: F = FiniteField_ext_pari(next_prime(200)^2, 'a')
328            sage: a = F.multiplicative_generator ()
329            sage: a._gap_ (gap) 
330            Z(211^2)
331            sage: (a^20)._gap_(gap)
332            Z(211^2)^20
333
334        Gap only supports relatively small finite fields.
335            sage: F = FiniteField_ext_pari(next_prime(1000)^2, 'a')
336            sage: a = F.multiplicative_generator ()
337            sage: gap._coerce_(a)
338            Traceback (most recent call last):
339            ...
340            TypeError: order must be at most 65536
341        """
342        F = self.parent()
343        if F.order() > 65536:
344            raise TypeError, "order must be at most 65536"
345       
346        if self == 0:
347            return '0*Z(%s)'%F.order()
348        assert F.degree() > 1
349        g = F.multiplicative_generator()
350        n = self.log(g)
351        return 'Z(%s)^%s'%(F.order(), n)
352
353    def charpoly(self, var):
354        """
355        Returns the characteristic polynomial of this element.
356
357        EXAMPLES:
358            sage: from sage.rings.finite_field import FiniteField_ext_pari
359            sage: k = FiniteField_ext_pari(3^3,'a'); a = k.gen()
360            sage: a.charpoly('x')
361            x^3 + 2*x + 1
362            sage: k.modulus()
363            x^3 + 2*x + 1
364            sage: b = a**2 + 1
365            sage: b.charpoly('x')
366            x^3 + x^2 + 2*x + 1
367        """
368        R = self.parent().prime_subfield()[var]
369        return R(self.__value.charpoly('x').lift())
370
371    def trace(self):
372        """
373        Returns the trace of this element.
374
375        EXAMPLES:
376            sage: from sage.rings.finite_field import FiniteField_ext_pari
377            sage: a = FiniteField_ext_pari(3**3, 'a').gen()
378            sage: b = a^2 + 2
379            sage: b.charpoly('x')
380            x^3 + x^2 + 2
381            sage: b.trace()
382            2
383            sage: b.norm()
384            1
385        """
386        return self.parent().prime_subfield()(self.__value.trace().lift())
387
388    def norm(self):
389        """
390        Returns the norm of this element, which is the constant term
391        of the characteristic polynomial, i.e., the determinant of left
392        multiplication.
393
394        EXAMPLES:
395            sage: from sage.rings.finite_field import FiniteField_ext_pari
396            sage: a = FiniteField_ext_pari(3**3, 'a').gen()
397            sage: b = a^2 + 2
398            sage: b.charpoly('x')
399            x^3 + x^2 + 2
400            sage: b.trace()
401            2
402            sage: b.norm()
403            1
404        """
405        f = self.charpoly('x')
406        n = f[0]
407        if f.degree() % 2 != 0:
408            return -n
409        else:
410            return n
411
412    def log(self, base):
413        """
414        Return $x$ such that $b^x = a$, where $x$ is $a$ and $b$
415        is the base.
416       
417        INPUT:
418            self -- finite field element
419            b -- finite field element that generates the multiplicative group.
420
421        OUTPUT:
422            Integer $x$ such that $a^x = b$, if it exists.
423            Raises a ValueError exception if no such $x$ exists.
424
425        EXAMPLES:
426            sage: from sage.rings.finite_field import FiniteField_ext_pari
427            sage: F = GF(17)
428            sage: F(3^11).log(F(3))
429            11
430            sage: F = GF(113)
431            sage: F(3^19).log(F(3))
432            19
433            sage: F = GF(next_prime(10000))
434            sage: F(23^997).log(F(23))
435            997
436
437            sage: F = FiniteField_ext_pari(2^10, 'a')
438            sage: g = F.gen()
439            sage: b = g; a = g^37
440            sage: a.log(b)
441            37
442            sage: b^37; a
443            a^8 + a^7 + a^4 + a + 1
444            a^8 + a^7 + a^4 + a + 1
445
446        AUTHOR: David Joyner and William Stein (2005-11)
447        """
448        q = (self.parent()).order() - 1
449        b = self.parent()(base)
450        # TODO: This function is TERRIBLE!  PARI?
451        return arith.discrete_log_generic(self, b, q)
452
453    def order(self):
454        """
455        Return the additive order of this finite field element.
456        """
457        if self.is_zero():
458            return Integer(1)
459        return self.parent().characteristic()
460       
461    def _repr_(self):
462        return ("%s"%(self.__value.lift().lift())).replace('a',self.parent().variable_name())
463
464    def _latex_(self):
465        """
466        EXAMPLES:
467            sage: from sage.rings.finite_field import FiniteField_ext_pari
468            sage: print latex(Set(FiniteField_ext_pari(9,'z')))
469            \left\{0, 1, 2, 2z + 1, z + 2, 2z, 2z + 2, z, z + 1\right\}
470        """
471        return self.polynomial()._latex_()
472   
473    def __compat(self, other):
474        if self.parent() != other.parent():
475            raise TypeError, "Parents of finite field elements must be equal."
476       
477    def _add_(self, right):
478        return FiniteField_ext_pariElement(self.__parent, self.__value + right.__value)
479   
480    def _sub_(self, right):
481        return FiniteField_ext_pariElement(self.__parent, self.__value - right.__value)
482   
483    def _mul_(self, right):
484        return FiniteField_ext_pariElement(self.__parent, self.__value * right.__value)
485
486    def _div_(self, right):
487        if right.__value == 0:
488            raise ZeroDivisionError
489        return FiniteField_ext_pariElement(self.__parent, self.__value / right.__value)
490
491    def __int__(self):
492        try:
493            return int(self.__value.lift().lift())
494        except ValueError:
495            raise TypeError, "cannot coerce to int"
496
497    def _integer_(self):
498        return self.lift()
499
500    def __long__(self):
501        try:
502            return long(self.__value.lift().lift())
503        except ValueError:
504            raise TypeError, "cannot coerce to long"
505
506    def __float__(self):
507        try:
508            return float(self.__value.lift().lift())
509        except ValueError:
510            raise TypeError, "cannot coerce to float"
511
512    # commented out because PARI (used for .__value) prints
513    # out crazy warnings when the exponent is LARGE -- this
514    # is even a problem in gp!!!
515    # (Commenting out causes this to use a generic algorithm)
516    #def __pow__(self, _right):
517    #    right = int(_right)
518    #    if right != _right:
519    #         raise ValueError
520    #    return FiniteField_ext_pariElement(self.__parent, self.__value**right)
521
522    def __neg__(self):
523        return FiniteField_ext_pariElement(self.__parent, -self.__value)
524   
525    def __pos__(self):
526        return self
527   
528    def __abs__(self):
529        raise ArithmeticError, "absolute value not defined"
530   
531    def __invert__(self):
532        """
533        EXAMPLES:
534            sage: from sage.rings.finite_field import FiniteField_ext_pari
535            sage: a = FiniteField_ext_pari(9, 'a').gen()
536            sage: ~a
537            a + 2
538            sage: (a+1)*a
539            2*a + 1
540        """
541
542        if self.__value == 0:
543            raise ZeroDivisionError, "Cannot invert 0"
544        return FiniteField_ext_pariElement(self.__parent, ~self.__value)
545   
546    def lift(self):
547        """
548        If this element lies in a prime finite field, return a lift of this
549        element to an integer.
550
551        EXAMPLES:
552            sage: from sage.rings.finite_field import FiniteField_ext_pari
553            sage: k = GF(next_prime(10**10))
554            sage: a = k(17)/k(19)
555            sage: b = a.lift(); b
556            7894736858
557            sage: b.parent()
558            Integer Ring
559        """
560        return integer_ring.IntegerRing()(self.__value.lift().lift())
561   
562   
563    def __cmp__(self, other):
564        """
565        Compare an element of a finite field with other.  If other is
566        not an element of a finite field, an attempt is made to coerce
567        it so it is one.
568
569        EXAMPLES:
570            sage: from sage.rings.finite_field import FiniteField_ext_pari
571            sage: a = FiniteField_ext_pari(3**3, 'a').gen()
572            sage: a == 1
573            False
574            sage: a**0 == 1
575            True
576            sage: a == a
577            True
578            sage: a < a**2
579            True
580            sage: a > a**2
581            False
582        """
583        return cmp(self.__value, other.__value)
584
585   
Note: See TracBrowser for help on using the repository browser.