Coverage for /usr/lib/python3/dist-packages/sympy/polys/numberfields/basis.py: 15%
82 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1"""Computing integral bases for number fields. """
3from sympy.polys.polytools import Poly
4from sympy.polys.domains.algebraicfield import AlgebraicField
5from sympy.polys.domains.integerring import ZZ
6from sympy.polys.domains.rationalfield import QQ
7from sympy.utilities.decorator import public
8from .modules import ModuleEndomorphism, ModuleHomomorphism, PowerBasis
9from .utilities import extract_fundamental_discriminant
12def _apply_Dedekind_criterion(T, p):
13 r"""
14 Apply the "Dedekind criterion" to test whether the order needs to be
15 enlarged relative to a given prime *p*.
16 """
17 x = T.gen
18 T_bar = Poly(T, modulus=p)
19 lc, fl = T_bar.factor_list()
20 assert lc == 1
21 g_bar = Poly(1, x, modulus=p)
22 for ti_bar, _ in fl:
23 g_bar *= ti_bar
24 h_bar = T_bar // g_bar
25 g = Poly(g_bar, domain=ZZ)
26 h = Poly(h_bar, domain=ZZ)
27 f = (g * h - T) // p
28 f_bar = Poly(f, modulus=p)
29 Z_bar = f_bar
30 for b in [g_bar, h_bar]:
31 Z_bar = Z_bar.gcd(b)
32 U_bar = T_bar // Z_bar
33 m = Z_bar.degree()
34 return U_bar, m
37def nilradical_mod_p(H, p, q=None):
38 r"""
39 Compute the nilradical mod *p* for a given order *H*, and prime *p*.
41 Explanation
42 ===========
44 This is the ideal $I$ in $H/pH$ consisting of all elements some positive
45 power of which is zero in this quotient ring, i.e. is a multiple of *p*.
47 Parameters
48 ==========
50 H : :py:class:`~.Submodule`
51 The given order.
52 p : int
53 The rational prime.
54 q : int, optional
55 If known, the smallest power of *p* that is $>=$ the dimension of *H*.
56 If not provided, we compute it here.
58 Returns
59 =======
61 :py:class:`~.Module` representing the nilradical mod *p* in *H*.
63 References
64 ==========
66 .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory*.
67 (See Lemma 6.1.6.)
69 """
70 n = H.n
71 if q is None:
72 q = p
73 while q < n:
74 q *= p
75 phi = ModuleEndomorphism(H, lambda x: x**q)
76 return phi.kernel(modulus=p)
79def _second_enlargement(H, p, q):
80 r"""
81 Perform the second enlargement in the Round Two algorithm.
82 """
83 Ip = nilradical_mod_p(H, p, q=q)
84 B = H.parent.submodule_from_matrix(H.matrix * Ip.matrix, denom=H.denom)
85 C = B + p*H
86 E = C.endomorphism_ring()
87 phi = ModuleHomomorphism(H, E, lambda x: E.inner_endomorphism(x))
88 gamma = phi.kernel(modulus=p)
89 G = H.parent.submodule_from_matrix(H.matrix * gamma.matrix, denom=H.denom * p)
90 H1 = G + H
91 return H1, Ip
94@public
95def round_two(T, radicals=None):
96 r"""
97 Zassenhaus's "Round 2" algorithm.
99 Explanation
100 ===========
102 Carry out Zassenhaus's "Round 2" algorithm on an irreducible polynomial
103 *T* over :ref:`ZZ` or :ref:`QQ`. This computes an integral basis and the
104 discriminant for the field $K = \mathbb{Q}[x]/(T(x))$.
106 Alternatively, you may pass an :py:class:`~.AlgebraicField` instance, in
107 place of the polynomial *T*, in which case the algorithm is applied to the
108 minimal polynomial for the field's primitive element.
110 Ordinarily this function need not be called directly, as one can instead
111 access the :py:meth:`~.AlgebraicField.maximal_order`,
112 :py:meth:`~.AlgebraicField.integral_basis`, and
113 :py:meth:`~.AlgebraicField.discriminant` methods of an
114 :py:class:`~.AlgebraicField`.
116 Examples
117 ========
119 Working through an AlgebraicField:
121 >>> from sympy import Poly, QQ
122 >>> from sympy.abc import x
123 >>> T = Poly(x ** 3 + x ** 2 - 2 * x + 8)
124 >>> K = QQ.alg_field_from_poly(T, "theta")
125 >>> print(K.maximal_order())
126 Submodule[[2, 0, 0], [0, 2, 0], [0, 1, 1]]/2
127 >>> print(K.discriminant())
128 -503
129 >>> print(K.integral_basis(fmt='sympy'))
130 [1, theta, theta/2 + theta**2/2]
132 Calling directly:
134 >>> from sympy import Poly
135 >>> from sympy.abc import x
136 >>> from sympy.polys.numberfields.basis import round_two
137 >>> T = Poly(x ** 3 + x ** 2 - 2 * x + 8)
138 >>> print(round_two(T))
139 (Submodule[[2, 0, 0], [0, 2, 0], [0, 1, 1]]/2, -503)
141 The nilradicals mod $p$ that are sometimes computed during the Round Two
142 algorithm may be useful in further calculations. Pass a dictionary under
143 `radicals` to receive these:
145 >>> T = Poly(x**3 + 3*x**2 + 5)
146 >>> rad = {}
147 >>> ZK, dK = round_two(T, radicals=rad)
148 >>> print(rad)
149 {3: Submodule[[-1, 1, 0], [-1, 0, 1]]}
151 Parameters
152 ==========
154 T : :py:class:`~.Poly`, :py:class:`~.AlgebraicField`
155 Either (1) the irreducible polynomial over :ref:`ZZ` or :ref:`QQ`
156 defining the number field, or (2) an :py:class:`~.AlgebraicField`
157 representing the number field itself.
159 radicals : dict, optional
160 This is a way for any $p$-radicals (if computed) to be returned by
161 reference. If desired, pass an empty dictionary. If the algorithm
162 reaches the point where it computes the nilradical mod $p$ of the ring
163 of integers $Z_K$, then an $\mathbb{F}_p$-basis for this ideal will be
164 stored in this dictionary under the key ``p``. This can be useful for
165 other algorithms, such as prime decomposition.
167 Returns
168 =======
170 Pair ``(ZK, dK)``, where:
172 ``ZK`` is a :py:class:`~sympy.polys.numberfields.modules.Submodule`
173 representing the maximal order.
175 ``dK`` is the discriminant of the field $K = \mathbb{Q}[x]/(T(x))$.
177 See Also
178 ========
180 .AlgebraicField.maximal_order
181 .AlgebraicField.integral_basis
182 .AlgebraicField.discriminant
184 References
185 ==========
187 .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory.*
189 """
190 K = None
191 if isinstance(T, AlgebraicField):
192 K, T = T, T.ext.minpoly_of_element()
193 if ( not T.is_univariate
194 or not T.is_irreducible
195 or T.domain not in [ZZ, QQ]):
196 raise ValueError('Round 2 requires an irreducible univariate polynomial over ZZ or QQ.')
197 T, _ = T.make_monic_over_integers_by_scaling_roots()
198 n = T.degree()
199 D = T.discriminant()
200 D_modulus = ZZ.from_sympy(abs(D))
201 # D must be 0 or 1 mod 4 (see Cohen Sec 4.4), which ensures we can write
202 # it in the form D = D_0 * F**2, where D_0 is 1 or a fundamental discriminant.
203 _, F = extract_fundamental_discriminant(D)
204 Ztheta = PowerBasis(K or T)
205 H = Ztheta.whole_submodule()
206 nilrad = None
207 while F:
208 # Next prime:
209 p, e = F.popitem()
210 U_bar, m = _apply_Dedekind_criterion(T, p)
211 if m == 0:
212 continue
213 # For a given prime p, the first enlargement of the order spanned by
214 # the current basis can be done in a simple way:
215 U = Ztheta.element_from_poly(Poly(U_bar, domain=ZZ))
216 # TODO:
217 # Theory says only first m columns of the U//p*H term below are needed.
218 # Could be slightly more efficient to use only those. Maybe `Submodule`
219 # class should support a slice operator?
220 H = H.add(U // p * H, hnf_modulus=D_modulus)
221 if e <= m:
222 continue
223 # A second, and possibly more, enlargements for p will be needed.
224 # These enlargements require a more involved procedure.
225 q = p
226 while q < n:
227 q *= p
228 H1, nilrad = _second_enlargement(H, p, q)
229 while H1 != H:
230 H = H1
231 H1, nilrad = _second_enlargement(H, p, q)
232 # Note: We do not store all nilradicals mod p, only the very last. This is
233 # because, unless computed against the entire integral basis, it might not
234 # be accurate. (In other words, if H was not already equal to ZK when we
235 # passed it to `_second_enlargement`, then we can't trust the nilradical
236 # so computed.) Example: if T(x) = x ** 3 + 15 * x ** 2 - 9 * x + 13, then
237 # F is divisible by 2, 3, and 7, and the nilradical mod 2 as computed above
238 # will not be accurate for the full, maximal order ZK.
239 if nilrad is not None and isinstance(radicals, dict):
240 radicals[p] = nilrad
241 ZK = H
242 # Pre-set expensive boolean properties which we already know to be true:
243 ZK._starts_with_unity = True
244 ZK._is_sq_maxrank_HNF = True
245 dK = (D * ZK.matrix.det() ** 2) // ZK.denom ** (2 * n)
246 return ZK, dK