Deterministically factoring integer polynomials modulo many primes simultaneously

Speaker: 

Daniel Altman

Affiliation: 

University of New South Wales

Date: 

Tue, 23/05/2017 -
1:00pm to 2:00pm

Venue: 

RC-4082, The Red Centre, UNSW

Abstract: 

Consider the problem of factorising a degree n polynomial over F_p. Randomised algorithms whose complexities are polynomial in n and log p date back half a century. The salient open problem in the area is to produce a deterministic algorithm whose complexity is polynomial in n and log p. The best known deterministic algorithms in the literature are exponential in log p. We present a new deterministic algorithm which tackles the problem for a large set of primes simultaneously; the amortised cost is polynomial in n and log p. In particular, given a monic, irreducible polynomial in Z[x] such that Q[x]/(f) is Galois over Q, the Galois group, and a large integer N,  the algorithm factorises f mod p for all p N.

School Seminar Series: