# A little intro to the Jacobi symbol: Part 1

Posted by Jason Polak on 21. July 2018 · Write a comment · Categories: number-theory · Tags: ,

If $m$ and $n$ are relatively prime integers, the Jacobi symbol $(m/n)$ is defined as the sign of the permutation $x\mapsto mx$ on the set $\Z/n$. Let's give a simple example: $(7/5)$. The permutation on $\{1,2,3,4\}$ is given by $(1 2 4 3) = (1 2)(2 4)(4 3)$ which has an odd number of transpositions. Therefore, $(7/5) = -1$.

Note that as in this example, it is sufficient to compute the sign of the permutation on $\Z/n – \{0\}$, since multiplication always leaves zero fixed.

But what if we wanted to compute something like $(3/412871)$? These numbers aren't so big, so a computer could do it directly. However, there is a better way to do the computation of the Jacobi symbol $(m/n)$ if one of $m$ or $n$ is much larger than the other one. This method is good for computers too when one of the numbers is so large, that a direct computation even by a fast computer would be hopeless.
More »

# Polynomial over finite field: permutation polynomial?

Posted by Jason Polak on 18. February 2018 · 2 comments · Categories: computer-science · Tags: , ,

Let's assume you have a polynomial over a finite field $\F_q$, defined in Sage. How can you tell whether it's a permutation polynomial? That is, when is the corresponding function $\F_q\to\F_q$ bijective?

This is how you might have a polynomial over $\F_q$ defined in Sage:

Here, the variable $x$ refers the element $x$ in the isomorphism $\F_q \cong \F_p[x]/\alpha(x)$ and $t$ is the variable in the polynomial ring $\F_q[t]$. Is $f$ a permutation polynomial? That of course depends on what $q$ is.
More »

# Working with group rings in Sage

Posted by Jason Polak on 16. January 2018 · Write a comment · Categories: commutative-algebra, ring-theory · Tags:

Let $\Z[\Z/n]$ denote the integral group ring of the cyclic group $\Z/n$. How would you create $\Z[\Z/n]$ in Sage so that you could easily multiply elements?

First, if you've already assigned a group to the variable 'A', then

will give you the corresponding group ring and store it in the variable 'R'. The first argument of 'GroupAlgebra(-,-)' is the group and the second is the coefficient ring. Sage uses 'ZZ' to denote the integers, 'QQ' to denote the rationals, etc.

So how do you specify the cyclic group $A$? The first posibility is to use the construction:

where you'd replace 'n' by the actual number that you want there. This is useful if you want to work with other permutation groups, because the elements of 'A' are stored as permutations:

The output to this snippet is:

More »