Ask Your Question

orangejake's profile - activity

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:

  1. g should generate the unit group of R
  2. The order of the unit group of R should be 24960
  3. g's order should be 24960
  4. 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
    # 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:


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:

  1. {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.<u> = CyclotomicField(n-1), and then K.<a> = 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).

  2. {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:

  1. Checks if it's being called on my special case, where better algorithms exist. If so, run that.
  2. 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 (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 <stuff>. Namely, how can I reduce the polynomial R with respect to the ideal P?