3
votes
1answer
42 views

Square-free factorization of polynomials over finite fields

For any $f\in\mathbb{F}_q[X]$, I want to derive an algorithm which computes a factorization $$f=\prod_{i=1}^kf_i^i\tag{1}$$ with square-free polynomials $f_i$. My Ideas: If $f'=0$, we're done ...
1
vote
1answer
46 views

Chinese remainder theorem for polynomial evaluation

Let $R$ be a euclidean domain, $m_0,\ldots ,m_{k-1}\in R$ be pairwise coprime and $m:=m_0\cdots m_{k-1}$. The Chinese remainder theorem states: $$\varphi:R\to R/(m_0)\times\cdots \times ...
1
vote
1answer
45 views

If $A\ne 0$ is a square matrix over a commutative ring with $\det A=0$, then its null space contains an element whose components are minors of $A$

Let $R$ denote a commutative ring and $A\ne 0$ a $n\times n$ matrix over $R$ with $\det A=0$. Then there exists a $x\in\ker A\setminus\left\{0\right\}$ such that all components of $x$ are minors of ...
5
votes
2answers
49 views

Analogue of Fermat's primality test for polynomials and irreducibility

We've got Fermat's primality test to test if a number is probable prime. Is there an analogous test for polynomials in $\mathbb{F}_{p^n}[X]$ and irreducibility?
1
vote
1answer
49 views

Number of monic irreducible polynomials over a finite field

Let $\mathbb{K}=\mathbb{F}_q$ and $\nu_n$ denote the number of monic irreducible polynomials over $\mathbb{K}$. It holds $$\nu_n=\frac{1}{n}\sum_{d\mid n}\mu\left(\frac{n}{d}\right)q^d$$ What I need ...
1
vote
1answer
42 views

How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and ...
1
vote
3answers
47 views

If there is an $a\in\mathbb{Z}$ with $a^{n-1}\equiv 1\mod n$ but $a^{\frac{n-1}p}\not\equiv 1$ for all primes $p\mid n-1$, then $n$ is a prime

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ ...
0
votes
1answer
23 views

Relationship between the Carmichael function and Euler's totient function

Let $\lambda$ denote the Carmichael function and $\varphi$ Euler's totient function. Furthermore, let $p$ denote any prime number and $k\in\mathbb{N}$. The wikipedia article about $\lambda$ states: ...
0
votes
1answer
54 views

What “meta-dimension” do algebraic numbers have?

actually what I am asking for is "how many ways do there exist to create a real number out of a sequence of coefficients?" there is the solution of polynomials through radicals, some polynomials can ...
3
votes
1answer
314 views

Proving $n^{97}\equiv n\text{ mod }4501770$

How do we show $$n^{97}\equiv n\text{ mod }4501770$$ for all integer $n$? First of all, I thought I could use Fermat's little theorem or Euler's theorem, but I'm not sure if they are applicable here.
0
votes
1answer
67 views

Computing univariate resultant via modified Euclidean algorithm

In an answer to the question Resultant of Two Univariate Polynomials, a PDF of course slides was linked which describes a modification of Euclid's algorithm for computing univariate polynomial ...
1
vote
1answer
113 views

Knuth-Bendix completion algorithm: word problem

Can someone explain me how to set up an algorithm to find the 12 normal forms of the group $A_4$ by making use of the Knuth-Bendix completion algorithm? So we have that $RRR=1, SSS=1$ and $RSRS=1$. ...
1
vote
1answer
70 views

Resultant of Two Univariate Polynomials

I am trying to implement an algorithm for computing Res(f(x),g(x),x) where f(x) and g(x) uni variate polynomials with integer coefficients. Could any one list the various algorithms for computing ...
0
votes
0answers
43 views

Evaluating polynomials at elements of algebras in Magma

I've defined a $2$ dimensional algebra, $A$ in Magma as follows: R:=FieldOfFractions(PolynomialRing(GF(2),10)); A:=Algebra< R,2|[1,0,0,1,0,1,1,1]>; The sequence of $1$'s and $0$'s just ...
2
votes
1answer
109 views

How to extract the indeterminates from a set of polynomial?

I am a biologist and I am facing a huge problem. I would like to extract the indeterminates of a set of polynomials, for example, I have: $f_{1} = \{\\x_{3}^{2} + x_{1}*x_{2} + x_{1} + x_{1}*x_{3},\\ ...
2
votes
1answer
119 views

Using Janet Basis to solve a nonlinear polynomial system

I am trying to solve a nonlinear polynomial equation system using Janet basis, when they have finite many solutions. For example the solution of the system: $$xy^2-y^3-3x^2=0,x^2+y^2+xy=0.$$ There ...
4
votes
1answer
188 views

Computing Conjugacy Classes of Subgroups in GAP

GAP has the command ConjugacyClassesSubgroups which gives a list of the conjugacy classes of a finite group $G$. Is there a way I can specify further what types of subgroups GAP reports? For ...
4
votes
2answers
513 views

Computing Subgroup Lattices

Let $G$ be a finite group, and let $L(G)$ be the lattice of subgroups, partially ordered by inclusion. For example, below is $L(D_8)$. $\quad\qquad\quad\qquad\quad\quad\qquad$ I have two questions: ...
2
votes
0answers
58 views

Minimal set of algebraically independent numbers

Suppose we have a set of polynomials $f_1, f_2, \ldots, f_n \in \mathbb{Q}[x]$. Consider the set $$S := \{\alpha \in \mathbb{C} \; | \; f_i(\alpha) = 0 \text{ for some } i \}$$ of complex roots of ...
4
votes
1answer
226 views

MAGMA question: SemidirectProduct using a homomorphism $f:G \rightarrow GL_n(\mathbb{F}_p)$.

Suppose I have a homomorphism $f:G\rightarrow GL_n(\mathbb{F}_p)$ and I wish to form the semidirect product $E\rtimes_f G$ with $E$ being the elementary abelian group of order $p^n$. The Semidirect ...
2
votes
3answers
97 views

Prove that $\log f(n)$ is $O(\log n)$.

If $f(n)$ is any polynomial in n with positive coefficients, how could I prove that $\log f(n)$ is $O(\log n)$? I've been having trouble how to do this for a while now.
5
votes
1answer
175 views

Algorithms for symbolic definite integration?

What are the algorithms for symbolic definite integration? Apart from computing the antiderivative first. What are the basic ideas behind such algorithms? As far as I got it, the main idea behind ...
1
vote
2answers
110 views

Representing Elementary Functions in a CAS

I've looked through several books about computer algebra. They are surprisingly scarce about how to actually represent elementary functions. Basically, as far as I understood elementary functions are ...
2
votes
1answer
182 views

Introduction to Elementary Functions

I'm looking for an introductory text on algebraic treatment of elementary functions. Really short and easy-going. Video lectures are even better. I want to learn basic ideas (i.e. definitions) behind ...
2
votes
0answers
155 views

What is a good software package for ( assisted ) theorem proving and documenting?

Background: An issue in my math study is that I haven't found a good way of storing the theorems ( mostly abstract algebra ) I studied and want to (re-)use in proofs. At the moment I use a personal ...
4
votes
1answer
313 views

Computing with ideals: over $K$ or over $\mathbb{Q}\subseteq K$? does it matter?

I'm beginning to learn to use SINGULAR, the computer algebra system (CAS) for commutative algebra. NOTATION: If $K$ is a field of characteristic $0$, then $\mathbb{Q}\subseteq K$; otherwise ...
1
vote
0answers
60 views

Computing relations on the columns of a matrix

Given an $m\times n$ (with $n>m)$ matrix $M$ over a polynomial ring $R=k[x_1,...,x_n]$, suppose that every column of $M$ is an $R$-linear combination of $m$ specified columns. I would like to ...
2
votes
3answers
156 views

Simplifying expressions

I have a polynomial ring $R=k[x,y,z...]$ and a given ideal $I$ (defined by given generators) and several polynomials $f_1,f_2,...$ in the ring. I also have several other elements of $R$ given as ...
3
votes
1answer
102 views

Find $k^{th}$ root of $M \in GL(n,F_2)$

Given $M \in GL(n,F_2)$ which is known to have a $k^{th}$ root. How can I find a root algorithmically? Can I find all roots? Other than being invertible and having a $k^{th}$ root I know nothing of ...