Alladi Ramakrishnan Hall

Finding quadratic non-residue over finite fields

Rajat Mittal

IIT Kanpur

It is known that finding square roots is equivalent to solving quadratic equations over finite fields. By Tonelli-Shanks algorithm, finding square roots is equivalent to finding an element in the finite field which does not have a square root (called a quadratic non-residue).

We will show that given an irreducible polynomial of even degree over $\mathbb{F}_p$, we can find quadratic non-residues in any finite field of characteristic $p$. If time permits, we will show that this can be generalized to $r$th non-residues.

This is joint work with Vishwas Bhargava and Nitin Saxena.