CMI Seminar

    Given a prime power p^n, a finite field of cardinality p^n may be constructed as the quotient of the ring of polynomials over the prime order field Z/pZ modulo an irreducible polynomial of degree n. This construction however is non canonical, for all known (unconditional) algorithms for finding irreducible polynomials are randomized. Irrespective of the choice of irreducible polynomial, one obtains the "same" field since two finite fields of the same cardinality are isomorphic. This poses the following algorithmic problem in several applications: Given two irreducible polynomials of degree n over Z/pZ, compute an isomorphism between the respective finite fields obtained modulo them.
    We begin by surveying the fastest known (randomized) algorithm for the problem, which has run time quadratic in n. We then present a new (randomized) algorithm based on elliptic curve isogenies with run time sub quadratic in n for most n. The crux of our approach is finding pre-images under the Lang map on elliptic curves over finite fields. We conclude by posing an open computational problem concerning Lang maps whose resolution would solve the isomorphism problem with run time linear in n. The discussion will be self contained and familiarity with elliptic curves, while helpful, is not required.