Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GRH:
Reports tagged with GRH:
TR08-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

#### Schemes for Deterministic Polynomial Factoring

In this work we relate the deterministic
complexity of factoring polynomials (over
finite
fields) to certain combinatorial objects we
call
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate ... more >>>

TR08-099 | 19th November 2008
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

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

In this paper we develop techniques that eliminate the need of the Generalized
Riemann Hypothesis (GRH) from various (almost all) known results about deterministic
polynomial factoring over finite fields. Our main result shows that given a
polynomial f(x) of degree n over a finite field k, we ... more >>>

TR12-068 | 25th May 2012
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

#### Deterministic Polynomial Factoring and Association Schemes

The problem of finding a nontrivial factor of a polynomial \$f(x)\$ over a finite field \$\mathbb{F}_q\$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

TR17-016 | 31st January 2017
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

#### Irreducibility and deterministic r-th root finding over finite fields

Constructing \$r\$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree \$r^e\$ (where \$r\$ is a prime) over a given finite field \$\F_q\$ of characteristic \$p\$ (equivalently, constructing the bigger field \$\F_{q^{r^e}}\$). Both these problems have famous randomized ... more >>>

ISSN 1433-8092 | Imprint