Trading GRH for algebra: algorithms for factoring polynomials and related structures

Introduction

The problem of finding a nontrivial factor of a given polynomial over a finite field is a fundamental computational problem. There are many problems whose known algorithms first require factoring polynomials. Thus, polynomial factoring is an intensely studied question and various randomized polynomial time algorithms are known – Berlekamp [Be67], Rabin [Rab80], Cantor and Zassenhaus [CZ81], von zur Gathen and Shoup [GS92], Kaltofen and Shoup [KS98] – but its deterministic complexity is a longstanding open problem. There are although several partial results known about the deterministic complexity of polynomial factoring based on the conjectured truth of the generalized Riemann Hypothesis (GRH). The surprising connection of GRH with polynomial factoring is based on the fact that if GRH is true and $r$ is a prime dividing $(|k|-1)$ then one can find primitive $r$-th nonresidues in the finite field $k$, which can then be used to factor ‘special’ polynomials, $x^{r}-a$ over $k$, in deterministic polynomial time (see [Ev89]).

Based on this are many deterministic factoring algorithms known, but all of them are super-polynomial time except on special instances.

The special instance when the degree $n$ of the input polynomial $f(x)$ has a “small” prime factor $r$ has been particularly interesting. Rónyai [Ró87] showed that under GRH one can find a nontrivial factor of $f(x)$ in deterministic polynomial time. Later it was shown by Evdokimov [Ev94] that Rónyai’s algorithm can be modified to get under GRH a deterministic algorithm that factors any input polynomial $f(x)\in k[x]$ of degree $n$ in sub-exponential time $poly(n^{\log n},\log|k|)$. This line of approach has since been investigated, in an attempt to remove GRH or improve the time complexity, leading to several algebraic-combinatorial conjectures and quite special case solutions [CH00, Gao01, IKS08].

Another instance studied is that of “special” finite fields. Bach, von zur Gathen and Lenstra [BGL01] showed under GRH that polynomials over finite fields of characteristic $p$ can be factored in deterministic polynomial time if $\phi_{k}(p)$ is “smooth” for some integer $k$, where $\phi_{k}(x)$ is the $k$-th cyclotomic polynomial. This result generalizes the previous works of Rónyai [Ró89a], Mignotte and Schnorr [MS88], von zur Gathen [G87], Camion [Cam83] and Moenck [Moe77].

Polynomial factoring has several applications both in the real world - coding theory and cryptography - and in fundamental computational algebra problems. The latter kind of applications are relevant to this work. Friedl and Rónyai [FR85] studied the computational problem of finding the simple components and a zero divisor of a given finite algebra over a finite field. They showed that all these problems depend on factoring polynomials over finite fields and hence have randomized polynomial time algorithms. Furthermore, they have under GRH deterministic subexponential time algorithms. In this work we give an unconditional version of this result. We show that if the given algebra is noncommutative then in fact we can find a zero divisor in deterministic subexponential time without needing GRH.

As we saw above there are several results on polynomial factoring that assume the truth of the GRH. Of course one would like to eliminate the need of GRH but that goal is still elusive. As a first step in that direction we give in this work GRH free versions of all the results mentioned above. In these versions the basic tool is that we either successfully find a nontrivial factor of a polynomial $f(x)$ over a finite field $k$ or we find a nontrivial automorphism of the algebra $k[x]/(f(x))$. Formally speaking the main result of the paper is:

Main Theorem: Let ${\cal A}$ be a commutative semisimple algebra of dimension $n$ over a finite field $k$ and let ${\cal A}$ be given in the input in terms of basis elements over $k$. Then there is a deterministic algorithm which in subexponential time $poly(n^{\log n},\log|k|)$ computes a decomposition of ${\cal A}$ into a direct sum ${\cal A}_{1}\oplus\ldots\oplus{\cal A}_{t}$ and finds an automorphism of order $\dim_{k}{\cal A}_{i}$ of the algebra ${\cal A}_{i}$, for each $1\leq i\leq t$.

This main theorem can be considered as a GRH-free version of Evdokimov’s factoring result [Ev94], but its proof leads us to significantly generalize standard notions and develop novel algebraic techniques that suggest a general paradigm for GRH elimination. We are going to use it as a tool for more important applications but first let us explain the importance of this result itself. It is the first deterministic subexponential time algorithm to find a nontrivial automorphism of a given commutative semisimple algebra over a finite field. Finding a nontrivial automorphism of a given arbitrary ring is in general as hard as integer factoring [KS05] but our result shows that it might be a lot easier for a commutative semisimple algebra over a finite field. Note that in the special case when ${\cal A}=k[x]/(f(x))$ with $f(x)$ splitting over $k$ as $\prod_{j=1}^{n}$ $(x-\alpha_{j})$, with $\alpha_{1},\ldots,\alpha_{n}$ all distinct, we have ${\cal A}\cong\oplus_{j=1}^{n}$ $k[x]/(x-\alpha_{j})$. The above algorithm either gives $t>1$ components of ${\cal A}$ – in which case it effectively yields a nontrivial factor of $f(x)$ – or $t=1$ and it gives an automorphism $\sigma$ of ${\cal A}$ of order $n$, thus yielding $n$ distinct “roots” of $f(x)$ – $x$, $\sigma(x),\ldots$, $\sigma^{n-1}(x)$ – all living in ${\cal A}\setminus k$. This latter case can be interpreted as finding roots over finite fields in terms of “radicals”, in analogy to classical Galois theory where one studies rational polynomials whose roots can be expressed by radicals, see Section 4 for details.

The key ideas in finding a nontrivial automorphism of a given commutative semisimple ${\cal B}$-algebra ${\cal A}$ over a finite field $k\subseteq{\cal B}$ are as follows. We consider a special ideal ${\cal A}^{\prime}$ (what we call the essential part in Section 5.2) of the tensor product ${\cal A}\otimes_{\cal B}{\cal A}$. The ideal ${\cal A}^{\prime}$ is just the kernel of a standard homomorphism of ${\cal A}\otimes_{\cal B}{\cal A}$ onto ${\cal A}$ and has rank (“dimension”) ${\rm rk}_{\cal B}{\cal A}({\rm rk}_{\cal B}{\cal A}-1)$ over ${\cal B}$. The algebra ${\cal A}$ gets naturally embedded in ${\cal A}^{\prime}$ by a map $\phi$, hence ${\cal A}^{\prime}$ is an extension algebra of $\phi({\cal A})\cong{\cal A}$ which in turn is an extension algebra of $\phi({\cal B})\cong{\cal B}$. Also, we know a natural automorphism of ${\cal A}^{\prime}$ fixing ${\cal B}$ – the map $\tau:x\otimes y\mapsto$ $y\otimes x$. A lot of technical effort goes into “bringing down” this automorphism (or certain other automorphism $\sigma$ of order $2$ obtained by recursion) from ${\cal A}^{\prime}$ to ${\cal A}$, i.e. getting a ${\cal B}$-automorphism $\sigma^{\prime}$ of ${\cal A}$. The technical arguments fall into two cases, depending on whether ${\rm rk}_{\cal A}{\cal A}^{\prime}={\rm rk}_{\cal B}{\cal A}^{\prime}/{\rm rk}_{\cal B}{\cal A}$ is odd or even.

(1) If the rank ${\rm rk}_{\cal B}{\cal A}$ is even then ${\rm rk}_{\cal A}{\cal A}^{\prime}$ is odd. We find an element $u\in{\cal A}^{\prime}$ with $u^{\tau}=-u$. If $u\in{\cal A}$ then the restriction of $\tau$ is a ${\cal B}$-automorphism of the subalgebra ${\cal B}[u]$ of ${\cal A}$ generated by ${\cal B}$ and $u$. If $u\not\in{\cal A}$ then either the subalgebra ${\cal A}[u]$ of ${\cal A}^{\prime}$ is not a free ${\cal A}$-module or ${\cal A}^{\prime}$ is not a free ${\cal A}[u]$-module. Both cases give us a zero divisor in ${\cal A}^{\prime}$ to go to a smaller ideal ${\cal I}$ of ${\cal A}^{\prime}$ such that we know an automorphism of ${\cal I}$, it contains a “copy” of ${\cal A}$ and ${\rm rk}_{\cal A}{\cal I}$ is odd, thus we can continue this “descent” (from ${\cal A}^{\prime}$ to ${\cal I}$) till we have a ${\cal B}$-automorphism of ${\cal A}$ or of a subalgebra of ${\cal A}$ (this process appears in Section 5.1). In the former case we are done while in the latter case we use two recursive calls and certain techniques to “glue” the three available automorphisms. (2) If the rank ${\rm rk}_{\cal B}{\cal A}$ is odd then ${\rm rk}_{\cal A}{\cal A}^{\prime}$ is even and we can use the technique above to find an ${\cal A}$-automorphism $\sigma$ of ${\cal A}^{\prime}$. It turns out that $\sigma$ and $\tau$ generate a group of automorphisms of ${\cal A}^{\prime}$ which is big enough to find a proper ideal ${\cal I}$ of ${\cal A}^{\prime}$ efficiently. We may further assume that the rank of ${\cal I}$ over ${\cal A}$ is at most ${\rm rk}_{\cal A}{\cal A}^{\prime}/2=({\rm rk}_{\cal B}{\cal A}-1)/2$. This allows us a recursive call with $({\cal I},{\cal A})$ in place of $({\cal A},{\cal B})$ to get an ${\cal A}$-automorphism of ${\cal I}$, which we eventually show is enough to extract an automorphism of ${\cal A}$ using tensor properties and a recursive call (this case 2 gets handled in 5.3).

This algebraic-extensions jugglery either goes through and yields a nontrivial automorphism $\sigma^{\prime}$ of ${\cal A}$ fixing ${\cal B}$ or it “fails” and yields a zero divisor in ${\cal A}$ which we use to “break” ${\cal A}$ into smaller subalgebras and continue working there. As in each recursive call, in the above two cases, the rank of the bigger algebra over the subalgebra is at most half of the original one, the depth of the recursion is at most $\log{\rm rk}_{\cal B}{\cal A}$. This gives an $n^{\log n}$ term in the time complexity analysis.

Roots of unity play a significant role in gluing automorphisms (i.e. in extending an automorphism of a subalgebra, of elements fixed by another automorphism, to the whole algebra). The gluing process is described in Section 4.4. As we do not know roots of unity in $k$ we resort to attaching virtual $r$-th roots of unity for a suitable prime $r$, i.e. working in the cyclotomic extension $k[\zeta_{r}]:=k[x]/(\sum_{i=1}^{r-1}x^{i})$ and ${\cal A}^{\prime}[\zeta_{r}]:=$ $k[\zeta_{r}]\otimes_{k}{\cal A}^{\prime}$. We then need to generalize standard algebraic constructions, like Kummer extensions and Teichmüller subgroups which were first used in a context similar to ours by Lenstra [L91] to find isomorphisms between fields, to our situation of commutative semisimple algebras.

The above theorem and its proof techniques have important applications. The first one is in finding zero divisors in a noncommutative algebra.

Application 1: Let ${\cal A}$ be an algebra of dimension $n$ over a finite field $k$ and let ${\cal A}$ be given in the input in terms of basis elements over $k$. Assume that ${\cal A}$ is noncommutative. Then there is a deterministic algorithm which finds a zero divisor in ${\cal A}$ in time $poly(n^{\log n},\log|k|)$.

The previous best result was due to Rónyai [Ró90] who gave an algorithm invoking polynomial factorization over finite fields and hence taking subexponential time assuming GRH. Our result removes the GRH assumption. It is interesting to note that if we prove such a result for commutative algebras as well then we would basically be able to factor polynomials in subexponential time without needing GRH.

If ${\cal A}$ is a simple algebra over the finite field $k$ then it is isomorphic to the algebra $M_{m}(K)$ of the $m\times m$ matrices with entries from an extension field $K$ of $k$. By Application 1 we find a proper left ideal of ${\cal A}$. A recursive call to a certain subalgebra of the left ideal will ultimately give a minimal left ideal of ${\cal A}$ and using this minimal one-sided ideal an isomorphism with $M_{m}(K)$ can be efficiently computed. Thus, for constant $m$, Application 1 extends Lenstra’s result (on computing isomorphisms between input fields) to noncommutative simple algebras, i.e, the explicit isomorphism problem is solved in this case. We note that, in general, algebra isomorphism problem over finite fields is not “believed” to be NP-hard but it is at least as hard as the graph isomorphism problem [KS05]. We also remark that the analogous problem of constructing isomorphism with the algebra of matrices over the rationals has a surprising application to rational parametrization of certain curves, see [GHPS06].

The techniques used to prove Main Theorem can be applied to find a nontrivial factor of an $r$-th cyclotomic polynomial over a finite field $k$, for almost all $r$’s, in deterministic polynomial time.

Roots of an $r$-th cyclotomic polynomial over $k$ are the $r$-th roots of unity and thus naturally related to all polynomial factoring algorithms. Assuming GRH several algorithms are known to factor these important polynomials (see [Ev89]). The above result gives the first deterministic polynomial time algorithm to nontrivially factor “most” of the cyclotomic polynomials without assuming GRH.

The third application of the techniques used to prove Main Theorem is in the instance of polynomial factoring over prime fields when we know the Galois group of the input polynomial. The following theorem can be seen as the GRH-free version of the main theorem of Rónyai [Ró89b].

Thus over “special” fields (i.e. when $p-1$ has only small prime factors) the above actually gives a deterministic polynomial time algorithm, a significant improvement over Main Theorem.

2 Organization

In Section 2 we collect various standard objects and structural facts associated to algebras. We also discuss the three basic methods that lead to discovering a zero divisor in an algebra – finding discrete log for elements of prime-power order, finding a free base of a module and refining an ideal by a given automorphism.

In this work we use methods for finding zero divisors in algebras in the case when certain groups of automorphisms are given. One of such methods is computing fixed subalgebras and testing freeness over them. In Section 3 we give a characterization of algebras and groups which survive these kinds of attacks. These algebras, called semiregular wrt the group, behave like fields in the sense that the whole algebra is a free module over the subalgebra of fixed points of the group and the rank equals the size of the group.

In Section 4 we build a small theory for the main algebraic construction, Kummer-type extensions over algebras, that we are going to use. We investigate there the action of the automorphisms of an algebra ${\cal A}$ on a certain subgroup, Teichmüller subgroup, of the multiplicative group of a Kummer-type extension of ${\cal A}$. The proofs of Applications 2 and 3 get completed in this section.

In Section 5 we apply the machinery of Section 4 to the tensor power algebras and complete the proof of Main Theorem.

In Section 6 we find suitable subalgebras of a given noncommutative algebra to invoke Main Theorem and complete the proof of Application 1.

In Section 7 we use the techniques developed for the Main Theorem in the case of special finite fields and complete the proof of Application 4.

Preliminaries

In this section we list some algebraic notions that we use in this work and that can be found in standard algebra texts, for example [La80].

Rings, Units and Zero-divisors: A ring with identity (or ring, for short) $R$ is a set of elements together with two operations – denoted by addition $+$ and multiplication $\cdot$ – such that $(R,+)$ is an Abelian group, $\cdot$ is associative, distributes over $+$ and has an identity element $1_{R}$. Note that the set $R^{*}$, containing all the elements of $R$ that have a multiplicative inverse, is a multiplicative group called the group of units. For a prime integer $r$ we call a unit $x$ an $r$-element if the multiplicative order of $x$ is a power of $r$. An element $x$ is called a zero divisor if $x\not=0$ and there exist nonzero $y,y^{\prime}\in{\cal A}$ such that $yx=xy^{\prime}=0$.

Free and Cyclic: For an $R$-module $M$, a set $E\subset M$ is called a free basis of $M$ if: $E$ is a generating set for $M$, i.e. every element of $M$ is a finite sum of elements of $E$ multiplied by coefficients in $R$, and $E$ is a free set, i.e. for all $r_{1},\ldots,r_{n}\in R$; $e_{1},\ldots,e_{n}\in E$, $r_{1}e_{1}+\cdots+r_{n}e_{n}=0$ implies that $r_{1}=\cdots=r_{n}=0$. A free module is a module with a free basis. $|E|$ is called the rank or dimension of the free module $M$ over $R$. Clearly, a vector space is a free module. A module is called a cyclic module if it is generated by one element.

Algebras: Let $(R,+,\cdot)$ be a commutative ring and $({\cal A},+,\cdot)$ be a ring which is also an $R$-module, where the additive operation of ${\cal A}$ as a module coincides with $+$. We say that ${\cal A}$ is an associative $R$-algebra with identity (or just an $R$-algebra for short) if multiplication by elements of $R$ commutes with multiplication by elements of ${\cal A}$: for every $r\in R$ and for every $a,b\in{\cal A}$ we have $r(ab)=(ra)b=a(rb)$.

Subalgebras: A subalgebra ${\cal B}$ of an $R$-algebra $({\cal A},+,\cdot)$ is just a submodule of ${\cal A}$ closed under multiplication. In this paper unless otherwise stated, by a subalgebra of ${\cal A}$ we mean a subalgebra containing the identity element $1_{\cal A}$. Note that if ${\cal B}$ is a commutative subalgebra of ${\cal A}$ then ${\cal A}$ is a ${\cal B}$-module in a natural way. If, furthermore, ${\cal B}$ is contained in the center of ${\cal A}$ (that is, $ab=ba$ for every $a\in{\cal A}$ and for every $b\in{\cal B}$) then ${\cal A}$ is a ${\cal B}$-algebra.

Extension: If ${\cal B}$ is a commutative $k$-algebra and a ${\cal B}$-algebra ${\cal A}$ is also a free module over ${\cal B}$ then we call ${\cal A}$ an algebra extension or an extension algebra over ${\cal B}$. This terminology is justified by the fact that ${\cal B}$ is embedded into (the center of) ${\cal A}$ by the map $b\mapsto b1_{\cal A}$. We denote the rank (“dimension”) of ${\cal A}$ as a ${\cal B}$-module by ${\rm rk}_{\cal B}{\cal A}$ or $[{\cal A}:{\cal B}]$. We sometimes use this notation also when there is an implicit embedding of ${\cal B}$ in ${\cal A}$.

Primitive Element: We call an algebra extension ${\cal A}$ over ${\cal B}$ simple if there is an $\alpha\in{\cal A}$ such that $\{1,\alpha,\ldots$, $\alpha^{n-1}\}$ forms a free basis of ${\cal A}$ over ${\cal B}$. We call $\alpha$ a primitive element and write ${\cal A}={\cal B}[\alpha]$.

Following is a version of the standard Primitive Element Theorem.

If $K\supseteq F$ are fields such that $char\ F$ is or $>[K:F]^{2}$, then $K$ has a primitive element over $F$.

There are two natural operations defined on algebras – the direct sum and the tensor product – each constructs a bigger algebra.

Direct Sum: Let $({\cal A}_{1},+,\cdot)$ and $({\cal A}_{2},+,\cdot)$ be two algebras. Then the direct sum algebra, ${\cal A}_{1}\oplus{\cal A}_{2}$, is the set $\{(a_{1},a_{2})\mid a_{1}\in{\cal A}_{1},a_{2}\in{\cal A}_{2}\}$ together with component-wise addition and multiplication operations. In a similar vein, for subalgebras ${\cal A}_{1},{\cal A}_{2}$ of an algebra ${\cal A}$ we write ${\cal A}={\cal A}_{1}\oplus{\cal A}_{2}$, if ${\cal A}={\cal A}_{1}+{\cal A}_{2}$ and ${\cal A}_{1},{\cal A}_{2}$ are orthogonal i.e. $\forall$ $a_{1}\in{\cal A}_{1}$, $a_{2}\in{\cal A}_{2}$, $a_{1}a_{2}=a_{2}a_{1}=0$.

Tensor Product: Furthermore, if ${\cal B}$ is a commutative algebra such that ${\cal A}_{1},{\cal A}_{2}$ are ${\cal B}$-algebras of dimensions $n_{1},n_{2}$ respectively over ${\cal B}$ then their tensor product algebra wrt ${\cal B}$, ${\cal A}_{1}\otimes_{\cal B}{\cal A}_{2}$, is the set $\{a_{1}\otimes a_{2}\mid a_{1}\in{\cal A}_{1},a_{2}\in{\cal A}_{2}\}$ naturally viewed as a ${\cal B}$-module having the multiplication operation: $(a_{1}\otimes a_{2})\cdot$ $(a_{1}^{\prime}\otimes a_{2}^{\prime})=$ $(a_{1}a_{1}^{\prime}\otimes a_{2}a_{2}^{\prime})$ for all $a_{1},a_{1}^{\prime}\in{\cal A}_{1}$ and $a_{2},a_{2}^{\prime}\in{\cal A}_{2}$. Note that the tensor product algebra has dimension $n_{1}n_{2}$ over ${\cal B}$. Thus, if ${\cal B}$ is finite then $|{\cal A}_{1}\oplus{\cal A}_{2}|=|{\cal B}|^{n_{1}+n_{2}}$, while $|{\cal A}_{1}\otimes_{\cal B}{\cal A}_{2}|=|{\cal B}|^{n_{1}n_{2}}$.

Decomposability: An algebra ${\cal A}$ is called indecomposable if there are no nonzero algebras $R,S$ such that ${\cal A}\cong R\oplus S$.

Following are some standard facts relating decomposability to idempotents in commutative algebras.

Let ${\cal A}$ be a commutative algebra then: (1) ${\cal A}$ decomposes iff ${\cal A}$ has a nontrivial idempotent. (2) If $e$ is an idempotent in ${\cal A}$ then ${\cal A}\cong$ $e{\cal A}\oplus(1-e){\cal A}$. (3) If $e$ is a primitive idempotent in ${\cal A}$ then $e{\cal A}$ is indecomposable.

Ideal: An ideal $I$ of an algebra ${\cal A}$ is a subset that is an additive subgroup of ${\cal A}$, is closed under multiplication and it contains both $aI:=\{a\cdot i\mid i\in I\}$; $Ia:=\{i\cdot a\mid i\in I\}$ for all $a\in{\cal A}$. Note that $\{0\}$ and ${\cal A}$ are ideals of ${\cal A}$, we call them trivial ideals. Also note that proper ideals are not subalgebras in the strict sense used in this paper.

Semisimplicity: An algebra ${\cal A}$ is called simple if it has no nontrivial ideal. An algebra is called semisimple if it is a direct sum of simple algebras.

Following are some standard facts about commutative semisimple algebras.

Let ${\cal A}$ be a commutative semisimple algebra then: (1) ${\cal A}$ is a direct sum of fields. (2) If $I$ is an ideal of ${\cal A}$ and $I^{\perp}:=\{a\in{\cal A}\mid aI=0\}$ (called the complement of $I$) then ${\cal A}=I\oplus I^{\perp}$. Furthermore, there exists an idempotent $e$ of ${\cal A}$ such that $I=e{\cal A}$ thus giving an explicit projection from ${\cal A}$ to $I$.

Following is the celebrated Artin-Wedderburn Theorem that classifies semisimple algebras.

Any semisimple algebra ${\cal A}$ is isomorphic to a direct sum of $n_{i}\times n_{i}$ matrix algebras over division rings $D_{i}$ (i.e. $D_{i}$ satisfies all field axioms except commutative multiplication). Both the $n_{i}$’s and $D_{i}$’s are uniquely determined up to permutation of the indices $i$.

Morphisms: Let $\phi$ be a map between two algebras ${\cal A}$, ${\cal B}$. If $\phi$ preserves the addition and multiplication operations of the algebras then we call it a homomorphism. If the homomorphism $\phi$ is injective then we call it an embedding. If the homomorphism $\phi$ is both injective and surjective then we call it an isomorphism. A homomorphism from an algebra to itself is called an endomorphism. An isomorphism from an algebra to itself is called an automorphism. A set $S$ is said to be invariant under the automorphism $\phi$ of ${\cal A}$ if for all $s\in S$, $\phi(s)\in S$. $\phi$ is said to fix $S$ if $\phi$ fixes each element of $S$, i.e. for all $s\in S$, $\phi(s)=s$. The group of $S$-automorphisms of ${\cal A}$, $Aut_{S}({\cal A})$, is the set of all automorphisms of ${\cal A}$ that fix $S$.

Throughout this paper all algebras are algebras with identity elements. Unless otherwise stated explicitly, by a subalgebra we mean a subalgebra containing the identity element. Thus, in this strict sense a proper ideal is not considered as a subalgebra. In the rest of this section ${\cal A}$ stands for a commutative semisimple algebra over the finite field $k$.

Given two $r$-elements (i.e. having order a power of the prime $r$) in a commutative semisimple algebra there is an algorithm that computes the discrete logarithm or finds a zero divisor (of a special form) in ${\cal A}$. We describe this algorithm below, it is a variant of the Pohlig-Hellman [PH78] algorithm with the equality testing of elements replaced by testing whether their difference is a zero divisor.

Given a prime $r$ distinct from the characteristic of a finite field $k$, a finite dimensional commutative semisimple algebra ${\cal A}$ over $k$ and two $r$-elements $a,b\in{\cal A}^{*}$, such that the order of $a$ is greater than or equal to the order of $b$. There is a deterministic algorithm which computes in time $poly(r,\log|{\cal A}|)$: (1) either two non-negative integers $s,s^{\prime}$ such that $a^{s}-b^{s^{\prime}}$ is a zero divisor in ${\cal A}$, (2) or an integer $s\geq 0$ with $a^{s}=b$.

Let $t_{a}$ be the smallest non negative integer such that $a^{r^{t_{a}}}-1$ is zero or a zero divisor in ${\cal A}$. Since $t_{a}\leq\log_{r}|{\cal A}|$ we can compute $a^{r^{0}}-1,a^{r^{1}}-1,\ldots,a^{r^{t_{a}}}-1$ in $poly(\log|{\cal A}|)$ time via fast exponentiation. We are done if $0\not=a^{r^{t_{a}}}-1=a^{r^{t_{a}}}-b^{0}$ is a zero divisor. Therefore we may assume that $a^{r^{t_{a}}}=1$, i.e. the order of $a$ is $r^{t_{a}}$. Let $t_{b}$ be the smallest non-negative integer such that $b^{r^{t_{b}}}-1$ is a zero divisor. Like $t_{a}$, $t_{b}$ can be computed in polynomial time and we may again assume that $r^{t_{b}}$ is the order of $b$. Replacing $a$ with $a^{r^{t_{a}-t_{b}}}$ we may assure that $t_{a}=t_{b}=t$. In this case for every primitive idempotent $e$ of ${\cal A}$: $ea,eb$ have order $r^{t}$ in the finite field $e{\cal A}$. As the multiplicative group of a finite field is cyclic, this means that there exists a nonnegative integer $s<r^{t}$ such that $(ea)^{s}=eb$. So we now attempt to find this discrete log, $s$, and the corresponding idempotent $e$ as well.

We iteratively compute the consecutive sections of the base $r$ expansion of $s$. To be more specific, we compute integers $s_{0}=0,s_{1},s_{2},\ldots,s_{t}$ together with idempotents $e_{1},\ldots,e_{t}$ of ${\cal A}$ such that, for all $1\leq j\leq t$: $0\leq s_{j}<r^{j}$, $s_{j}\equiv s_{j-1}\pmod{r^{j-1}}$ and $a^{{s_{j}}r^{t-j}}e_{j}=b^{r^{t-j}}e_{j}$.

In the initial case $j=1$ we find by exhaustive search, in at most $r$ rounds, an $s_{1}\in\{1,\ldots,r-1\}$ such that $z_{1}=$ $(a^{r^{t-1}{s_{1}}}-b^{r^{t-1}})$ is zero or a zero divisor. If it is zero then we set $e_{1}=1$ otherwise we compute and set $e_{1}$ equal to the identity element of the annihilator ideal $\{x\in{\cal A}|z_{1}x=0\}$.

Assume that for some $j<t$ we have found already $s_{j}$ and $e_{j}$ with the desired property. Then we find by exhaustive search, in at most $r$ rounds, an integer $d_{j+1}\in\{0,\ldots,r-1\}$ such that $z_{j+1}=$ $(a^{(s_{j}+r^{j}d_{j+1})r^{t-j-1}}-b^{r^{t-j-1}})$ is zero or a zero divisor. We set $s_{j+1}=(s_{j}+d_{j+1}r^{j})$ and take as $e_{j+1}$ the identity element of the annihilator ideal $\{x\in e_{j}{\cal A}|xz_{j+1}=0\}$.

The above procedure clearly terminates in $t$ rounds and using fast exponentiation can be implemented in $poly(r,\log|{\cal A}|)$ time. $\Box$

2 Free Bases of Modules

One of the possible methods for finding zero divisors in algebras is attempting to compute a free basis of a module over it. Following Lemma states the basic tool to do that.

Let $V$ be a finitely generated module over a finite dimensional algebra ${\cal A}$ over a finite field $k$. If $V$ is not a free ${\cal A}$-module then one can find a zero divisor in ${\cal A}$ deterministically in time $poly(\dim_{\cal A}V,\log|{\cal A}|)$.

We give an algorithm that attempts to find a free basis of $V$ over ${\cal A}$, but as there is no free basis it ends up finding a zero divisor.

Pick a nonzero $v_{1}\in V$. We can efficiently check whether a nonzero $x\in{\cal A}$ exists such that $xv_{1}=0$, and also find it by linear algebra over $k$. If we get such an $x$ then it is a zero divisor, for otherwise $x^{-1}$ would exist implying $v_{1}=0$. So suppose such an $x$ does not exist, hence $V_{1}:={\cal A}v_{1}$ is a free ${\cal A}$-module. Now $V_{1}\neq V$ so find a $v_{2}\in V\setminus V_{1}$ by linear algebra over $k$. Again we can efficiently check whether a nonzero $x\in{\cal A}$ exists such that $xv_{2}\in V_{1}$, and also find it by linear algebra over $k$. If we get such an $x$ then it is a zero divisor, for otherwise $x^{-1}$ would exist implying $v_{2}\in V_{1}$. So suppose such an $x$ does not exist, hence $V_{2}:={\cal A}v_{1}+{\cal A}v_{2}$ is a free ${\cal A}$-module. Now $V_{2}\neq V$ so we can find a $v_{3}\in V\setminus V_{2}$ by linear algebra over $k$ and continue this process. This process will, in at most $dim_{\cal A}V$ iterations, yield a zero divisor as $V$ is not a free ${\cal A}$-module. $\Box$

3 Automorphisms and Invariant Ideal Decompositions

Given an ideal $I$ of ${\cal A}$ and an automorphism $\sigma$ of ${\cal A}$ we usually try to find zero divisors from the action of $\sigma$ on $I$. Note that, by Fact 3, ${\cal A}=I\oplus I^{\perp}$. Now $I^{\sigma}$ is an ideal of ${\cal A}$, and if it is neither $I$ nor $I^{\perp}$ then we try computing $I\cap I^{\sigma}$. This can be easily computed by first finding the identity element $e$ of $I$, and then $I\cap I^{\sigma}$ is simply ${\cal A}ee^{\sigma}$. By the hypothesis this will be a proper ideal of $I$, thus leading to a refinement of the decomposition: ${\cal A}=I\oplus I^{\perp}$. This basic idea can be carried all the way to give the following tool that finds a refined, invariant, ideal decomposition.

Given ${\cal A}$, a commutative semisimple algebra over a finite field $k$ together with a set of $k$-automorphisms $\Gamma$ of ${\cal A}$ and a decomposition of ${\cal A}$ into a sum of pairwise orthogonal ideals $J_{1},\ldots,J_{s}$, there is a deterministic algorithm of time complexity $poly(|\Gamma|,\log|{\cal A}|)$ that computes a decomposition of ${\cal A}$ into a sum of pairwise orthogonal ideals $I_{1},\ldots,I_{t}$ such that: (1) the new decomposition is a refinement of the original one – for every $j\in\{1,\ldots,t\}$, there exists $i\in\{1,\ldots,s\}$ such that $I_{j}\subseteq J_{i}$, and (2) the new decomposition is invariant under $\Gamma$ – the group generated by $\Gamma$ permutes the ideals $I_{1},\ldots,I_{t}$, i.e. for every $\sigma\in\Gamma$ and for every index $j\in\{1,\ldots,t\}$, we have $I_{j}^{\sigma}=I_{j^{\sigma}}$ for some index $j^{\sigma}\in\{1,\ldots,t\}$.

Semiregularity

In this section we continue to assume that ${\cal A}$ is a commutative semisimple algebra over a finite field $k$. Given $\Gamma\subseteq{\rm Aut}_{k}({\cal A})$, a basis of ${\cal A}_{\Gamma}$ can be computed by solving a system of linear equations in ${\cal A}$. Thus, we can apply the method of Lemma 2.2 considering ${\cal A}$ as a ${\cal A}_{\Gamma}$-module wrt the multiplication in ${\cal A}$. In this section we describe a class of algebras, together with automorphisms, that are free modules over the subalgebra of the fixed points of the corresponding set of automorphisms, i.e. on which the tool of Lemma 2.2 is ineffective.

Let $\sigma$ be a $k$-automorphism of ${\cal A}$. We say that $\sigma$ is fix-free if there is no nontrivial ideal $I$ of ${\cal A}$ such that $\sigma$ fixes $I$. We call a group $G\leq{\rm Aut}({\cal A})$ semiregular if every non-identity element of $G$ is fix-free. A single automorphism $\sigma$ of ${\cal A}$ is semiregular if $\sigma$ generates a semiregular group of automorphisms of ${\cal A}$.

We have the following characterization of semiregularity.

Let ${\cal A}$ be a commutative semisimple algebra over a finite field $k$ and let $G$ be a group of $k$-automorphisms of ${\cal A}$. Then $\dim_{k}{\cal A}\leq|G|\cdot\dim_{k}{\cal A}_{G}$, where equality holds if and only if $G$ is semiregular. This condition is also equivalent to saying that ${\cal A}$ is a free ${\cal A}_{G}$-module of rank $|G|$.

The proof is based on the observation that ${\cal A}$ is a direct sum of fields and a $k$-automorphism of ${\cal A}$ just permutes these component fields.

Let $e$ be a primitive idempotent of ${\cal A}$. We denote the stabilizer of $e$ in $G$ by $G_{e}$, i.e, $G_{e}=\{\sigma\in G|e^{\sigma}=e\}$. Let $C$ be a complete set of right coset representatives modulo $G_{e}$ in $G$. The orbit of $e$ under $G$ is $\{e^{\gamma}|\gamma\in C\}$ and they are $|G:G_{e}|$ many pairwise orthogonal primitive idempotents in ${\cal A}$. This means that the component field $e{\cal A}$ is sent to the other component fields $\{e^{\gamma}{\cal A}|\gamma\in C\}$ by $G$. Thus, the element $f:=\sum_{\gamma\in C}e^{\gamma}$ $\in{\cal A}_{G}$ is a primitive idempotent of ${\cal A}_{G}$ and equivalently $f{\cal A}_{G}$ is a field.

The subgroup $G_{e}$ acts as a group of field automorphisms of $e{\cal A}$. This gives a restriction map $\lambda:G_{e}\rightarrow Aut_{k}(e{\cal A})$ whose kernel say is $N_{e}$, so $N_{e}=\{\sigma\in G|\sigma\text{ fixes }e{\cal A}\}$ is a normal subgroup of $G_{e}$, thus $G_{e}/N_{e}$ are distinct $k$-automorphisms of the field $e{\cal A}$. We claim that $(e{\cal A})_{G_{e}}=e{\cal A}_{G}$. The inclusion $e{\cal A}_{G}\subseteq(e{\cal A})_{G_{e}}$ is trivial. To see the reverse inclusion, let $x\in(e{\cal A})_{G_{e}}$ and consider $y:=\sum_{\gamma\in C}x^{\gamma}$. Since $x\in e{\cal A}$ we get $ex=x$ and $y=\sum_{\gamma\in C}e^{\gamma}x^{\gamma}$, whence using the orthogonality of the idempotents $e^{\gamma}$, we infer $ey=x$. The fact that $y\in{\cal A}_{G}$ completes the proof of the claim. As $G_{e}$ is a group of automorphisms of the field $e{\cal A}$, this claim implies $e{\cal A}_{G}$ is a field too and also by Galois theory $[e{\cal A}:e{\cal A}_{G}]=|G_{e}/N_{e}|$.

Observe that $ef=e$ and this makes multiplication by $e$ a onto homomorphism from $f{\cal A}_{G}$ to $e{\cal A}_{G}$. This homomorphism is also injective as $e{\cal A}_{G}$, $f{\cal A}_{G}$ are fields, thus making $f{\cal A}_{G}\cong e{\cal A}_{G}$. Together with the fact that $f{\cal A}$ is a free $e{\cal A}$-module of dimension $|G:G_{e}|$ this implies that $\dim_{f{\cal A}_{G}}f{\cal A}=|G:G_{e}|\dim_{e{\cal A}_{G}}e{\cal A}$. Furthermore, from the last paragraph $\dim_{e{\cal A}_{G}}e{\cal A}=|G_{e}:N_{e}|$, thus $\dim_{f{\cal A}_{G}}f{\cal A}=|G:N_{e}|\leq|G|$. Finally, this gives $\dim_{k}f{\cal A}\leq\dim_{k}f{\cal A}_{G}\cdot|G|$. Applying this for all the primitive idempotents $e$ of ${\cal A}$ (and thus to all the corresponding primitive idempotents $f$ of ${\cal A}_{G}$), we obtain the asserted inequality.

Observe that equality holds iff $|N_{e}|=1$ for every primitive idempotent $e$ of ${\cal A}$. In that case for every primitive idempotent $e$ of ${\cal A}$, there is no non-identity automorphism in $G$ that fixes $e{\cal A}$, thus equivalently for every nontrivial ideal $I$ of ${\cal A}$ there is no non-identity automorphism in $G$ that fixes $I$. This means that equality holds iff $G$ is semiregular.

Also, equality holds iff $\dim_{f{\cal A}_{G}}f{\cal A}=|G|$ for every primitive idempotent $e$ of ${\cal A}$. The latter condition is equivalent to saying that every component field of ${\cal A}_{G}$ has multiplicity $|G|$ in the ${\cal A}_{G}$-module ${\cal A}$, this in turn is equivalent to saying that ${\cal A}$ is a free ${\cal A}_{G}$-module of dimension $|G|$. $\Box$

Using the above Lemma we can decide semiregularity in an efficient way.

Given a commutative semisimple algebra ${\cal A}$ over a finite field $k$, together with a set $\Gamma$ of $k$-automorphisms of ${\cal A}$. Let $G$ be the group generated by $\Gamma$. In deterministic $poly(|\Gamma|,\log|{\cal A}|)$ time one can list all the elements of $G$ if $G$ is semiregular, or one can find a zero divisor of ${\cal A}$ if $G$ is not semiregular.

We first compute ${\cal A}_{\Gamma}$ by linear algebra over $k$. We can assume that ${\cal A}$ is a free ${\cal A}_{\Gamma}$-module otherwise the algorithm in Lemma 2.2 finds a zero divisor. By Lemma 3.1 $|G|\geq\dim_{{\cal A}_{\Gamma}}{\cal A}=:m$ so try to enumerate $(m+1)$ different elements in the group $G$. If we are unable to get that many elements then, by Lemma 3.1, $G$ is semiregular and we end up with a list of $m$ elements that exactly comprise $G$.

If we do get a set $S$ of $(m+1)$ elements then $G$ is clearly not semiregular. Let $e$ be a primitive idempotent of ${\cal A}$ such that the subgroup $N_{e}\leq G$, consisting of automorphisms that fix $e{\cal A}$, is of maximal size. Then from the proof of Lemma 3.1 we obtain $|G:N_{e}|\leq m$ which means, by pigeon-hole principle, that in the set $S$ there are two different elements $\sigma_{1},\sigma_{2}$ such that $\sigma:=\sigma_{1}\sigma_{2}^{-1}\in N_{e}$, thus $\sigma$ fixes $e{\cal A}$. We now compute ${\cal A}_{\sigma}$ and we know from this discussion that $e{\cal A}\subseteq{\cal A}_{\sigma}$. Thus we get two orthogonal component algebras $e{\cal A}_{\sigma}$ and $(1-e){\cal A}_{\sigma}$ of ${\cal A}_{\sigma}$. We have from the proof of Lemma 3.1 that $e{\cal A}_{\sigma}=(e{\cal A})_{\sigma}=e{\cal A}$ while $(1-e){\cal A}_{\sigma}=$ $((1-e){\cal A})_{\sigma}\neq(1-e){\cal A}$ (if $((1-e){\cal A})_{\sigma}=(1-e){\cal A}$ then $\sigma$ would fix every element in ${\cal A}$ and would be a trivial automorphism). As a result ${\cal A}$ is not a free module over ${\cal A}_{\sigma}$ and hence we can find a zero divisor of ${\cal A}$ using the method of Lemma 2.2. $\Box$

Subgroup $G_{\cal B}$: Let $G$ be a semiregular group of $k$-automorphisms of ${\cal A}$ and let ${\cal B}$ be a subalgebra of ${\cal A}$. We define $G_{\cal B}$ to be the subgroup of automorphisms of $G$ that fix ${\cal B}$. We give below a Galois theory-like characterization of $G_{\cal B}$.

Given a semiregular group $G$ of automorphisms of a commutative semisimple algebra ${\cal A}$ over a finite field $k$ and a subalgebra ${\cal B}$ of ${\cal A}$ containing ${\cal A}_{G}$, one can find a zero divisor in ${\cal A}$ in deterministic polynomial time if ${\cal B}\not={\cal A}_{G_{\cal B}}$.

If ${\cal A}$ is a field extension of $k$ then by Galois theory ${\cal B}={\cal A}_{G_{\cal B}}$. If $|k|<(\dim_{k}{\cal A})^{2}$ and ${\cal A}$ is not a field then we can find a zero divisor in ${\cal A}$ using Berlekamp’s deterministic polynomial time algorithm. So for the rest of the proof we may assume that $|k|\geq(\dim_{k}{\cal A})^{2}$ and then the usual proof of Fact 1 gives a deterministic polynomial time algorithm for finding a primitive element $x$ of ${\cal A}$ over $k$, see [GI00].

Let $|G|=d$. We may assume that the elements $1,x,x^{2},\ldots,x^{d-1}$ form a free basis of ${\cal A}$ over ${\cal A}_{G}$ since otherwise we find a zero divisor in ${\cal A}$ using the method of Lemma 2.2. Let $x^{d}=\sum_{i=0}^{d-1}a_{i}x^{i}$ with $a_{i}\in{\cal A}_{G}$ and let $f(X):=X^{d}-\sum_{i=0}^{d-1}a_{i}X^{d}\in{\cal A}_{G}[X]$. Obviously $x$ is a root of $f(X)$ and as any $\sigma\in G$ fixes the coefficients of $f(X)$ we get that $x^{\sigma}$ is also a root of $f(X)$. Again by Lemma 2.2 we may assume that ${\cal A}$ is a ${\cal B}$-module with $\{1,x,\ldots x^{m-1}\}$ as a free basis, where $m:=dim_{\cal B}{\cal A}$. Let $x^{m}=\sum_{i=0}^{m-1}b_{i}x^{i}$ with $b_{i}\in{\cal B}$, thus $x$ is a root of the polynomial $g(X):=X^{m}-\sum_{i=0}^{m-1}b_{i}X^{i}\in{\cal B}[X]$.

Let us consider $f(X)$ as a polynomial in ${\cal B}[X]$. As $g(X)$ is monic we can apply the usual polynomial division algorithm to obtain polynomials $h(X)$ and $r[X]$ from ${\cal B}(X)$ such that the degree of $h(X)$ is $(d-m)$; the degree of $r(X)$ is less than $m$ and $f(X)=g(X)h(X)+r(X)$. We have $r(x)=0$ which together with the freeness of the basis $\{1,\ldots,x^{m-1}\}$ implies that $r(X)=0$ and $f(X)=g(X)h(X)$. We know from the last paragraph that for all $\sigma\in G$, $x^{\sigma}$ is a root of $g(X)h(X)$. If neither $g(x^{\sigma})$ nor $h(x^{\sigma})$ is zero then we have a pair of zero divisors. If $g(x^{\sigma})=0$ then we can perform the division of $g(X)$ by $(X-x^{\sigma})$ obtaining a polynomial $g_{1}(X)\in{\cal B}[X]$ with $g(X)=(X-X^{\sigma})g_{1}(X)$ and can then proceed with a new automorphism $\sigma^{\prime}\in G$ and with $g_{1}(X)$ in place of $g(X)$. In $d$ rounds we either find a zero divisor in ${\cal A}$ or two disjoint subsets $K,K^{\prime}$ of $G$ with $g(X)=\prod_{\sigma\in K}(X-x^{\sigma})$ and $h(X)=\prod_{\sigma^{\prime}\in K^{\prime}}(X-x^{\sigma^{\prime}})$. For $\sigma\in K$ let $\phi_{\sigma}:{\cal B}[X]\rightarrow{\cal A}$ be the homomorphism which fixes ${\cal B}$ but sends $X$ to $x^{\sigma}$. As $g(x^{\sigma})=0$, $\phi_{\sigma}$ induces a homomorphism from ${\cal B}[X]/(g(X))$ to ${\cal A}$, which we denote again by $\phi_{\sigma}$. We know that $\phi_{1}$ is actually an isomorphism ${\cal B}[X]/(g(X))\cong{\cal A}$, therefore the maps $\mu_{\sigma}=\phi_{\sigma}\circ\phi_{1}^{-1}$ ($\sigma\in K$) are ${\cal B}$-endomorphisms of ${\cal A}$. Note that we can find a zero divisor in ${\cal A}$ if any $\mu_{\sigma}$ is not an automorphism, also by Proposition 3.2 we can find a zero divisor in ${\cal A}$ if the maps $\mu_{\sigma}$ ($\sigma\in K$) generate a non-semiregular group of ${\cal B}$-automorphisms of ${\cal A}$. Thus, we can assume that $\mu_{\sigma}$, for all $\sigma\in K$, generate a semiregular group of ${\cal B}$-automorphisms of ${\cal A}$. As $|K|=dim_{\cal B}{\cal A}$ this means, by Lemma 3.1, that the set $\{\mu_{\sigma}|\sigma\in K\}$ is a group say $H$. We can as well assume that the group of $k$-automorphisms of ${\cal A}$ generated by $G$ and $H$ is semiregular, for otherwise we find a zero divisor in ${\cal A}$. Again as $|G|=dim_{k}{\cal A}$ this means, by Lemma 3.1, that $H$ is a subgroup of $G$. Thus, by Lemma 3.1, $[{\cal A}:{\cal A}_{H}]=|H|=|K|=[{\cal A}:{\cal B}]$ which together with the fact ${\cal B}\leq{\cal A}_{H}$ gives ${\cal A}_{H}={\cal B}$. As $H\leq G_{\cal B}$ we also get $H=G_{\cal B}$ (if $H<G_{\cal B}$ then $[{\cal A}:{\cal A}_{H}]<$ $[{\cal A}:{\cal A}_{G_{\cal B}}]\leq[{\cal A}:{\cal B}]$ which is a contradiction). Thus, if none of the above steps yield a zero divisor then ${\cal B}={\cal A}_{G_{\cal B}}$. $\Box$