2021-05-18 15:47:45 +0100 received badge ● Notable Question (source) 2020-05-06 08:08:16 +0100 answered a question Basic modular arithmetic correctness question The issue is that R's multiplicative group is not cyclic. I am trying to delete the question now that it is answered. 2020-05-06 07:51:24 +0100 asked a question Basic modular arithmetic correctness question I am on sagemath verion 8.1. Consider the following block of code: n = 75024 R = IntegerModRing(n) g = R.unit_gens()[0] # This is 65647 order = R.unit_group_order() # This is 24960 g**2 == 1  This last line will output True. My thoughts on the matter are: g should generate the unit group of R The order of the unit group of R should be 24960 g's order should be 24960 g's order must be 2 These clearly cannot all hold. I imagine I'm misunderstanding one of the functions I referred to, but from reading the documentation I cannot determine where my misunderstanding is. Can someone help set me straight? 2020-01-05 00:06:58 +0100 asked a question Computing the mod q kernel of a matrix for q composite As the title states, I'm interested in computing the $\bmod q$ kernel of a matrix for $q$ composite. This means that the matrix isn't a linear transformation between vector spaces, so linear algebraic techniques don't apply. From this answer, I have the following code (which is correct). The issue I currently have is that it is slow. The source of the inefficiency is fortunately obvious, so this question is mostly about suggestions to avoid it. def modq_kernel(matx, q): # Returns the mod_q (right) kernel of a given matrix, in the case # that q is not prime # Uses https://ask.sagemath.org/question/33890/how-to-find-kernel-of-a-matrix-in-mathbbzn/ # Iterates over whole kernel to find a matrix that generates it, likely slow source_dim = matx.ncols() target_dim = matx.nrows() domain = ZZ^source_dim / (q * ZZ^source_dim) codomain = ZZ^target_dim / (q * ZZ^target_dim) phi = domain.hom([codomain(matx.columns()[i]) for i in range(source_dim)]) full_kernel = matrix([domain(b) for b in phi.kernel()]).T pivot_cols = full_kernel.echelon_form().pivots() reduced_kernel = matrix(full_kernel.columns()[i] for i in pivot_cols).T return reduced_kernel  This code rewrites the matrix as a module homomorphism $\mathbb{Z}_q^n\to\mathbb{Z}_q^m$, enumerates all elements in the kernel of this homomorphism, and then uses an echelon form computation to identify generators of the kernel. As the size of the kernel is exponential in its dimension, this is (understandably) quite slow. It is also correct, as the following test case demonstrates: p = 2 k = 4 q = p**k - 1 zero_vec = matrix((k-1) * [0]).T matx = block_matrix([[identity_matrix(k-1), zero_vec]]) - p * block_matrix([[zero_vec, identity_matrix(k-1)]])  The origin of this matrix is unimportant. What matters is that I know that its mod-q kernel is: [8 1 2 4] [4 8 1 2] [2 4 8 1] [1 2 4 8]  which the aforementioned code correctly identifies. One can verify that matx * ker % q is an all-zero matrix (where ker is the above matrix), and everything is good. A natural way to try to improve the efficiency of the above code is to iterate not through phi.kernel(), but through phi.kernel().gens() instead. This should additionally let you remove the echelon form computations (while keeping the initial matrix small). If one makes this change (and returns full_kernel instead), the code now computes the kernel as: [8] [4] [2] [1]  This is contained in the kernel, but does not actually span the whole kernel (it's missing the other 3 vectors in the first kernel found). So while the code is much faster now, it is incorrect. I'm wondering if anyone knows how to efficiently compute the entire $\bmod q$ kernel of a map in $\mathbb{Z}_q^{n\times m}$. 2019-10-04 04:35:44 +0100 received badge ● Popular Question (source) 2017-11-29 07:53:37 +0100 commented answer Monkey-patching PARI calls Does monkey patching work for purely sage libraries? 2017-11-28 04:16:55 +0100 received badge ● Supporter (source) 2017-11-27 10:23:46 +0100 commented answer Monkey-patching PARI calls Could something like forebidden fruit let me avoid modifying source? That'd make it more difficult to distribute my code later. 2017-11-27 06:02:21 +0100 received badge ● Student (source) 2017-11-27 05:04:38 +0100 received badge ● Editor (source) 2017-11-27 01:09:54 +0100 received badge ● Scholar (source) 2017-11-27 00:37:25 +0100 asked a question Monkey-patching PARI calls I'm currently trying to implement some number field computations on a very particular number field (specifically, $K = \mathbb{Q}(\zeta_{n-1},n^{1/(n-1)})$). The code I've written so far has some bottlenecks that profiling via %prun has identified, namely: {method '_nf_rnfeq' of 'sage.libs.cypari2.gen.gen' objects}, which seems to compute the minimal polynomial of $K$ (currently I'm defining $K$ via F. = CyclotomicField(n-1), and then K. = F.extension(x^(n-1) - n), so $K$ is a relative extension. _nf_rnfeq seems to compute the absolute minimal polynomial of a given relative extension (via PARI). {method 'discriminant' of 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint' objects}, which appears to just be the polynomial discriminant computation. Assume I've done analysis by hand gives me a much faster computation of the absolute minimal polynomial for this particular number field. I'd then want a version of _nf_rnfeq that: Checks if it's being called on my special case, where better algorithms exist. If so, run that. Otherwise, run the traditional algorithm. Of course, I'd prefer to make this modification without modifying the source code, as that seems to be an especially ugly solution. One way to implement this is to change is by modifying the relevant method at run-time, via a technique known as "Monkey-Patching" (see https://stackoverflow.com/questions/47503061/replacing-specific-function-calls/47503146#47503146 (here)). The issue I'm having now is that attempting to monkey-patch the PARI call gives me the error: TypeError: can't set attributes of built-in/extension type 'sage.libs.cypari2.gen.gen' The code I'm using (in the first cell of my IPython notebook) is below: import sage.libs.cypari2.gen orig_nf_rnfeq = sage.libs.cypari2.gen.gen._nf_rnfeq def _nf_rnfeq(*args, **kwargs): print("Rnfeq works!") return orig_nf_rnfeq(*args, **kwargs) sage.libs.cypari2.gen.gen._nf_rnfeq = _nf_rnfeq  2017-11-19 23:23:01 +0100 commented answer Polynomial Mod Ideal This is exactly what I needed! A few questions: 1. Is there any particular reason that the field $F$ is constructed as an extension of a cyclotomic, instead of just specifying the two generators? 2. Similar to the above, is there any particular reason the norm of p1 is computed as the relative norm, and then the (what I'm assuming is) absolute norm? 2017-11-16 21:45:28 +0100 commented question Polynomial Mod Ideal The proof is: "The polynomial $R′$ has splitting field $L = \mathbb{Q}(\zeta_n−1, n^{1/(n−1)})$, in which $p_0$ does not ramify because $p_0$ does not divide $n(n−1)$. Thus $R$ is an Eisenstein polynomial with respect to any prime above $p_0$ in $L$; in particular, $R$ is irreducible over $L$. By the Chebotarev density theorem, there exist infinitely many prime ideals of $L$ of absolute degree 1 modulo which $R$ is irreducible; the norm of any such prime ideal is the prime we want." I'm not entirely sure what "absolute degree 1" means for a prime ideal, and if K.primes_of_degree_one_iter() is giving me something else (namely, fractional ideals), this could be the issue. Do you know how I could find prime ideals of $L$ of absolute degree 1? 2017-11-16 21:42:33 +0100 commented question Polynomial Mod Ideal I'm trying to implement Lemma 2.3 from Kedlaya's A construction of polynomials with squarefree discriminants (I don't believe I can post links, its identifier on Arxiv is 1103.5728). This lemma says "Let $p_0$ be a prime not dividing $n(n−1)$. Then there exist infinitely many primes $p_1$ modulo which the polynomial $R(x) = x^n − p_0^{n−1}x + p_0$ is irreducible and its derivative $R′(x) = nx^{n−1} − p_0^{n−1}$ splits into distinct linear factors. 2017-11-16 09:07:44 +0100 asked a question Polynomial Mod Ideal I have a polynomial $R\in\mathbb{Z}[x]$. I then define $R' = \frac{d}{dx}R$, and look at the splitting field of $R'$, $K$, an algebraic number field. Now, I want to find a prime ideal $\mathfrak{p}$ of $L$ of absolute degree 1 such that $R\mod\mathfrak{p}$ is irreducible. To do this, I've set up: p0, n = 5, 7 L = PolynomialRing(ZZ,'x') R = L(x^n-p0^(n-1)x+p0) Rprime = L(n*x^(n-1)-p0^(n-1)) K = NumberField(Rprime, 'z') for P in K.primes_of_degree_one_iter():  I'm now trying ti find the right thing to do for . Namely, how can I reduce the polynomial R with respect to the ideal P?