CoCalc -- hom_finite_field

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/rings/finite_rings/hom_finite_field_givaro.pyx
⁸⁸²⁰ views
1
"""
2
Special implementation for givaro finite fields of:
3

4
- embeddings between finite fields
5

6
- frobenius endomorphisms
7

8
SEEALSO::
9

10
    :mod:`sage.rings.finite_rings.hom_finite_field`
11

12
AUTHOR:
13

14
- Xavier Caruso (2012-06-29)
15
"""
16

17
#############################################################################
18
#    Copyright (C) 2012 Xavier Caruso <[email protected]>
19
#
20
#  Distributed under the terms of the GNU General Public License (GPL)
21
#
22
#                  http://www.gnu.org/licenses/
23
#****************************************************************************
24

25
include "../../ext/stdsage.pxi"
26

27
from sage.rings.finite_rings.constructor import FiniteField
28

29
from hom_finite_field cimport SectionFiniteFieldHomomorphism_generic
30
from hom_finite_field cimport FiniteFieldHomomorphism_generic
31
from hom_finite_field cimport FrobeniusEndomorphism_finite_field
32

33
from hom_prime_finite_field cimport FiniteFieldHomomorphism_prime
34

35
from sage.categories.homset import Hom
36
from sage.structure.element cimport Element
37
from sage.rings.morphism cimport RingHomomorphism_im_gens
38

39
from sage.rings.finite_rings.finite_field_givaro import FiniteField_givaro
40
from element_givaro cimport FiniteField_givaroElement
41
#from element_givaro cimport make_FiniteField_givaroElement
42

43
from sage.structure.parent cimport Parent
44
from element_givaro cimport Cache_givaro
45

46

47
cdef class SectionFiniteFieldHomomorphism_givaro(SectionFiniteFieldHomomorphism_generic):
48
    def __init__(self, inverse):
49
        """
50
        TESTS::
51

52
            sage: from sage.rings.finite_rings.hom_finite_field_givaro import FiniteFieldHomomorphism_givaro
53
            sage: k.<t> = GF(3^2)
54
            sage: K.<T> = GF(3^4)
55
            sage: f = FiniteFieldHomomorphism_givaro(Hom(k, K))
56
            sage: g = f.section(); g
57
            Section of Ring morphism:
58
              From: Finite Field in t of size 3^2
59
              To:   Finite Field in T of size 3^4
60
              Defn: t |--> 2*T^3 + 2*T^2 + 1
61
        """
62
        if not isinstance(inverse, FiniteFieldHomomorphism_givaro):
63
            raise TypeError("The given map is not an instance of FiniteFieldHomomorphism_givaro")
64
        SectionFiniteFieldHomomorphism_generic.__init__(self, inverse)
65

66
        cdef long inverse_power = (<FiniteFieldHomomorphism_givaro>inverse)._power
67
        cdef long order = self.domain().cardinality() - 1
68
        self._order_codomain = self.codomain().cardinality() - 1
69

70
        # Compute a = gcd(inverse_power, order)
71
        # and solve inverse_power*x = a (mod order)
72
        cdef long a = inverse_power, b = order
73
        cdef unsigned long q
74
        cdef long x = 1, y = 0
75
        cdef long sb, sy
76
        while b != 0:
77
            q = a // b
78
            sb = b; b = a-q*b; a = sb
79
            sy = y; y = x-q*y; x = sy
80

81
        self._gcd = a
82
        if x < 0:
83
            x += order
84
        self._power = x % self._order_codomain
85

86
        self._codomain_cache = (<FiniteField_givaroElement>(self._codomain.gen()))._cache
87

88

89
    cpdef Element _call_(self, x):
90
        """
91
        TESTS::
92

93
            sage: from sage.rings.finite_rings.hom_finite_field_givaro import FiniteFieldHomomorphism_givaro
94
            sage: k.<t> = GF(3^2)
95
            sage: K.<T> = GF(3^4)
96
            sage: f = FiniteFieldHomomorphism_givaro(Hom(k, K))
97
            sage: g = f.section()
98
            sage: g(f(t+1))
99
            t + 1
100

101
            sage: g(T)
102
            Traceback (most recent call last):
103
            ...
104
            ValueError: T is not in the image of Ring morphism:
105
              From: Finite Field in t of size 3^2
106
              To:   Finite Field in T of size 3^4
107
              Defn: t |--> 2*T^3 + 2*T^2 + 1
108
        """
109
        if x.parent() != self.domain():
110
            raise TypeError("%s is not in %s" % (x, self.domain()))
111
        cdef FiniteField_givaroElement y = <FiniteField_givaroElement?>x
112
        if y._cache.objectptr.isZero(y.element):
113
            return make_FiniteField_givaroElement(self._codomain_cache, self._codomain_cache.objectptr.zero)
114
        if y._cache.objectptr.isOne(y.element):
115
            return make_FiniteField_givaroElement(self._codomain_cache, self._codomain_cache.objectptr.one)
116
        cdef int log = y.element
117
        cdef int q = log / self._gcd
118
        if log == q*self._gcd:
119
            q = (q*self._power) % self._order_codomain
120
            return make_FiniteField_givaroElement(self._codomain_cache, q)
121
        else:
122
            raise ValueError("%s is not in the image of %s" % (x, self._inverse))
123

124

125
cdef class FiniteFieldHomomorphism_givaro(FiniteFieldHomomorphism_generic):
126
    def __init__(self, parent, im_gens=None, check=False):
127
        """
128
        TESTS::
129

130
            sage: from sage.rings.finite_rings.hom_finite_field_givaro import FiniteFieldHomomorphism_givaro
131
            sage: k.<t> = GF(3^2)
132
            sage: K.<T> = GF(3^4)
133
            sage: f = FiniteFieldHomomorphism_givaro(Hom(k, K)); f
134
            Ring morphism:
135
              From: Finite Field in t of size 3^2
136
              To:   Finite Field in T of size 3^4
137
              Defn: t |--> 2*T^3 + 2*T^2 + 1
138

139
            sage: k.<t> = GF(3^10)
140
            sage: K.<T> = GF(3^20)
141
            sage: f = FiniteFieldHomomorphism_givaro(Hom(k, K)); f
142
            Traceback (most recent call last):
143
            ...
144
            TypeError: The codomain is not an instance of FiniteField_givaro
145
        """
146
        domain = parent.domain()
147
        codomain = parent.codomain()
148
        if not isinstance(domain, FiniteField_givaro):
149
            raise TypeError("The domain is not an instance of FiniteField_givaro")
150
        if not isinstance(codomain, FiniteField_givaro):
151
            raise TypeError("The codomain is not an instance of FiniteField_givaro")
152

153
        FiniteFieldHomomorphism_generic.__init__(self, parent, im_gens, check,
154
                                                 section_class=SectionFiniteFieldHomomorphism_givaro)
155

156
        cdef Cache_givaro domain_cache = (<FiniteField_givaroElement>(domain.gen()))._cache
157
        self._codomain_cache = (<FiniteField_givaroElement>(codomain.gen()))._cache
158

159
        cdef FiniteField_givaroElement g = make_FiniteField_givaroElement(domain_cache, 1)
160
        cdef FiniteField_givaroElement G = FiniteFieldHomomorphism_generic._call_(self, g)
161
        self._power = G.element
162

163
        self._order_domain = domain.cardinality() - 1
164
        self._order_codomain = codomain.cardinality() - 1
165

166

167
    cpdef Element _call_(self, x):
168
        """
169
        TESTS::
170

171
            sage: from sage.rings.finite_rings.hom_finite_field_givaro import FiniteFieldHomomorphism_givaro
172
            sage: k.<t> = GF(3^2)
173
            sage: K.<T> = GF(3^4)
174
            sage: f = FiniteFieldHomomorphism_givaro(Hom(k, K))
175
            sage: f(t)
176
            2*T^3 + 2*T^2 + 1
177
        """
178
        if x.parent() != self.domain():
179
            raise TypeError("%s is not in %s" % (x, self.domain()))
180
        cdef FiniteField_givaroElement y = <FiniteField_givaroElement?>x
181
        if y._cache.objectptr.isZero(y.element):
182
            return make_FiniteField_givaroElement(self._codomain_cache, self._codomain_cache.objectptr.zero)
183
        if y._cache.objectptr.isOne(y.element):
184
            return make_FiniteField_givaroElement(self._codomain_cache, self._codomain_cache.objectptr.one)
185
        cdef int log = y.element
186
        log = (log*self._power) % self._order_codomain
187
        return make_FiniteField_givaroElement(self._codomain_cache, log)
188

189

190

191
cdef class FrobeniusEndomorphism_givaro(FrobeniusEndomorphism_finite_field):
192
    def __init__(self, domain, power=1):
193
        """
194
        TESTS::
195

196
            sage: k.<t> = GF(5^3)
197
            sage: Frob = k.frobenius_endomorphism(); Frob
198
            Frobenius endomorphism t |--> t^5 on Finite Field in t of size 5^3
199
            sage: type(Frob)
200
            <type 'sage.rings.finite_rings.hom_finite_field_givaro.FrobeniusEndomorphism_givaro'>
201

202
            sage: k.<t> = GF(5^20)
203
            sage: Frob = k.frobenius_endomorphism(); Frob
204
            Frobenius endomorphism t |--> t^5 on Finite Field in t of size 5^20
205
            sage: type(Frob)
206
            <type 'sage.rings.finite_rings.hom_finite_field.FrobeniusEndomorphism_finite_field'>
207
        """
208
        if not isinstance(domain, FiniteField_givaro):
209
            raise TypeError("The domain is not an instance of FiniteField_givaro")
210
        FrobeniusEndomorphism_finite_field.__init__(self, domain, power)
211

212

213
    def fixed_field(self):
214
        """
215
        Return the fixed field of ``self``.
216

217
        OUTPUT:
218

219
        - a tuple `(K, e)`, where `K` is the subfield of the domain
220
          consisting of elements fixed by ``self`` and `e` is an
221
          embedding of `K` into the domain.
222

223
        .. NOTE::
224

225
            The name of the variable used for the subfield (if it
226
            is not a prime subfield) is suffixed by ``_fixed``.
227

228
        EXAMPLES::
229

230
            sage: k.<t> = GF(5^6)
231
            sage: f = k.frobenius_endomorphism(2)
232
            sage: kfixed, embed = f.fixed_field()
233
            sage: kfixed
234
            Finite Field in t_fixed of size 5^2
235
            sage: embed
236
            Ring morphism:
237
              From: Finite Field in t_fixed of size 5^2
238
              To:   Finite Field in t of size 5^6
239
              Defn: t_fixed |--> 4*t^5 + 2*t^4 + 4*t^2 + t
240

241
            sage: tfixed = kfixed.gen()
242
            sage: embed(tfixed)
243
            4*t^5 + 2*t^4 + 4*t^2 + t
244
        """
245
        if self._degree_fixed == 1:
246
            k = FiniteField(self.domain().characteristic())
247
            f = FiniteFieldHomomorphism_prime(Hom(k, self.domain()))
248
        else:
249
            k = FiniteField(self.domain().characteristic()**self._degree_fixed,
250
                            name=self.domain().variable_name() + "_fixed")
251
            f = FiniteFieldHomomorphism_givaro(Hom(k, self.domain()))
252
        return k, f
253

254

255
# copied from element_givaro.pyx
256
cdef inline FiniteField_givaroElement make_FiniteField_givaroElement(Cache_givaro cache, int x):
257
    cdef FiniteField_givaroElement y
258

259
    if cache._has_array:
260
        return <FiniteField_givaroElement>cache._array[x]
261
    else:
262
        y = PY_NEW(FiniteField_givaroElement)
263
        y._parent = <Parent> cache.parent
264
        y._cache = cache
265
        y.element = x
266
        return y
267

268
Product

Resources

Company
