Coverage for /usr/lib/python3/dist-packages/sympy/polys/domains/finitefield.py: 50%

1"""Implementation of :class:`FiniteField` class. """ 

2 

3 

4from sympy.polys.domains.field import Field 

5 

6from sympy.polys.domains.modularinteger import ModularIntegerFactory 

7from sympy.polys.domains.simpledomain import SimpleDomain 

8from sympy.polys.polyerrors import CoercionFailed 

9from sympy.utilities import public 

10from sympy.polys.domains.groundtypes import SymPyInteger 

11 

12@public 

13class FiniteField(Field, SimpleDomain): 

14 r"""Finite field of prime order :ref:`GF(p)` 

15 

16 A :ref:`GF(p)` domain represents a `finite field`_ `\mathbb{F}_p` of prime 

17 order as :py:class:`~.Domain` in the domain system (see 

18 :ref:`polys-domainsintro`). 

19 

20 A :py:class:`~.Poly` created from an expression with integer 

21 coefficients will have the domain :ref:`ZZ`. However, if the ``modulus=p`` 

22 option is given then the domain will be a finite field instead. 

23 

24 >>> from sympy import Poly, Symbol 

25 >>> x = Symbol('x') 

26 >>> p = Poly(x**2 + 1) 

27 >>> p 

28 Poly(x**2 + 1, x, domain='ZZ') 

29 >>> p.domain 

30 ZZ 

31 >>> p2 = Poly(x**2 + 1, modulus=2) 

32 >>> p2 

33 Poly(x**2 + 1, x, modulus=2) 

34 >>> p2.domain 

35 GF(2) 

36 

37 It is possible to factorise a polynomial over :ref:`GF(p)` using the 

38 modulus argument to :py:func:`~.factor` or by specifying the domain 

39 explicitly. The domain can also be given as a string. 

40 

41 >>> from sympy import factor, GF 

42 >>> factor(x**2 + 1) 

43 x**2 + 1 

44 >>> factor(x**2 + 1, modulus=2) 

45 (x + 1)**2 

46 >>> factor(x**2 + 1, domain=GF(2)) 

47 (x + 1)**2 

48 >>> factor(x**2 + 1, domain='GF(2)') 

49 (x + 1)**2 

50 

51 It is also possible to use :ref:`GF(p)` with the :py:func:`~.cancel` 

52 and :py:func:`~.gcd` functions. 

53 

54 >>> from sympy import cancel, gcd 

55 >>> cancel((x**2 + 1)/(x + 1)) 

56 (x**2 + 1)/(x + 1) 

57 >>> cancel((x**2 + 1)/(x + 1), domain=GF(2)) 

58 x + 1 

59 >>> gcd(x**2 + 1, x + 1) 

60 1 

61 >>> gcd(x**2 + 1, x + 1, domain=GF(2)) 

62 x + 1 

63 

64 When using the domain directly :ref:`GF(p)` can be used as a constructor 

65 to create instances which then support the operations ``+,-,*,**,/`` 

66 

67 >>> from sympy import GF 

68 >>> K = GF(5) 

69 >>> K 

70 GF(5) 

71 >>> x = K(3) 

72 >>> y = K(2) 

73 >>> x 

74 3 mod 5 

75 >>> y 

76 2 mod 5 

77 >>> x * y 

78 1 mod 5 

79 >>> x / y 

80 4 mod 5 

81 

82 Notes 

83 ===== 

84 

85 It is also possible to create a :ref:`GF(p)` domain of **non-prime** 

86 order but the resulting ring is **not** a field: it is just the ring of 

87 the integers modulo ``n``. 

88 

89 >>> K = GF(9) 

90 >>> z = K(3) 

91 >>> z 

92 3 mod 9 

93 >>> z**2 

94 0 mod 9 

95 

96 It would be good to have a proper implementation of prime power fields 

97 (``GF(p**n)``) but these are not yet implemented in SymPY. 

98 

99 .. _finite field: https://en.wikipedia.org/wiki/Finite_field 

100 """ 

101 

102 rep = 'FF' 

103 alias = 'FF' 

104 

105 is_FiniteField = is_FF = True 

106 is_Numerical = True 

107 

108 has_assoc_Ring = False 

109 has_assoc_Field = True 

110 

111 dom = None 

112 mod = None 

113 

114 def __init__(self, mod, symmetric=True): 

115 from sympy.polys.domains import ZZ 

116 dom = ZZ 

117 

118 if mod <= 0: 

119 raise ValueError('modulus must be a positive integer, got %s' % mod) 

120 

121 self.dtype = ModularIntegerFactory(mod, dom, symmetric, self) 

122 self.zero = self.dtype(0) 

123 self.one = self.dtype(1) 

124 self.dom = dom 

125 self.mod = mod 

126 

127 def __str__(self): 

128 return 'GF(%s)' % self.mod 

129 

130 def __hash__(self): 

131 return hash((self.__class__.__name__, self.dtype, self.mod, self.dom)) 

132 

133 def __eq__(self, other): 

134 """Returns ``True`` if two domains are equivalent. """ 

135 return isinstance(other, FiniteField) and \ 

136 self.mod == other.mod and self.dom == other.dom 

137 

138 def characteristic(self): 

139 """Return the characteristic of this domain. """ 

140 return self.mod 

141 

142 def get_field(self): 

143 """Returns a field associated with ``self``. """ 

144 return self 

145 

146 def to_sympy(self, a): 

147 """Convert ``a`` to a SymPy object. """ 

148 return SymPyInteger(int(a)) 

149 

150 def from_sympy(self, a): 

151 """Convert SymPy's Integer to SymPy's ``Integer``. """ 

152 if a.is_Integer: 

153 return self.dtype(self.dom.dtype(int(a))) 

154 elif a.is_Float and int(a) == a: 

155 return self.dtype(self.dom.dtype(int(a))) 

156 else: 

157 raise CoercionFailed("expected an integer, got %s" % a) 

158 

159 def from_FF(K1, a, K0=None): 

160 """Convert ``ModularInteger(int)`` to ``dtype``. """ 

161 return K1.dtype(K1.dom.from_ZZ(a.val, K0.dom)) 

162 

163 def from_FF_python(K1, a, K0=None): 

164 """Convert ``ModularInteger(int)`` to ``dtype``. """ 

165 return K1.dtype(K1.dom.from_ZZ_python(a.val, K0.dom)) 

166 

167 def from_ZZ(K1, a, K0=None): 

168 """Convert Python's ``int`` to ``dtype``. """ 

169 return K1.dtype(K1.dom.from_ZZ_python(a, K0)) 

170 

171 def from_ZZ_python(K1, a, K0=None): 

172 """Convert Python's ``int`` to ``dtype``. """ 

173 return K1.dtype(K1.dom.from_ZZ_python(a, K0)) 

174 

175 def from_QQ(K1, a, K0=None): 

176 """Convert Python's ``Fraction`` to ``dtype``. """ 

177 if a.denominator == 1: 

178 return K1.from_ZZ_python(a.numerator) 

179 

180 def from_QQ_python(K1, a, K0=None): 

181 """Convert Python's ``Fraction`` to ``dtype``. """ 

182 if a.denominator == 1: 

183 return K1.from_ZZ_python(a.numerator) 

184 

185 def from_FF_gmpy(K1, a, K0=None): 

186 """Convert ``ModularInteger(mpz)`` to ``dtype``. """ 

187 return K1.dtype(K1.dom.from_ZZ_gmpy(a.val, K0.dom)) 

188 

189 def from_ZZ_gmpy(K1, a, K0=None): 

190 """Convert GMPY's ``mpz`` to ``dtype``. """ 

191 return K1.dtype(K1.dom.from_ZZ_gmpy(a, K0)) 

192 

193 def from_QQ_gmpy(K1, a, K0=None): 

194 """Convert GMPY's ``mpq`` to ``dtype``. """ 

195 if a.denominator == 1: 

196 return K1.from_ZZ_gmpy(a.numerator) 

197 

198 def from_RealField(K1, a, K0): 

199 """Convert mpmath's ``mpf`` to ``dtype``. """ 

200 p, q = K0.to_rational(a) 

201 

202 if q == 1: 

203 return K1.dtype(K1.dom.dtype(p)) 

204 

205 

206FF = GF = FiniteField