English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we develop techniques that eliminate the need of theGeneralized Riemann Hypothesis (GRH) from various (almost all) known resultsabout deterministic polynomial factoring over finite fields. Our main resultshows that given a polynomial f(x) of degree n over a finite field k, we canfind in deterministic poly(n^{\log n},\log |k|) time "either" a nontrivialfactor of f(x) "or" a nontrivial automorphism of k[x]/(f(x)) of order n. Thismain tool leads to various new GRH-free results, most striking of which are:  (1) Given a noncommutative algebra over a finite field, we can find a zerodivisor in deterministic subexponential time.  (2) Given a positive integer r such that either 8|r or r has at least twodistinct odd prime factors. There is a deterministic polynomial time algorithmto find a nontrivial factor of the r-th cyclotomic polynomial over a finitefield.  In this paper, following the seminal work of Lenstra (1991) on constructingisomorphisms between finite fields, we further generalize classical Galoistheory constructs like cyclotomic extensions, Kummer extensions, Teichmullersubgroups, to the case of commutative semisimple algebras with automorphisms.These generalized constructs help eliminate the dependence on GRH.

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