5
$\begingroup$

I saw some papers from famous mathematicians (assuming GRH or without it) which are devoted to finding bound for least quadratic nonresidues modulo prime number $p$.

My question is that why it is so important and what are the applications of it?

Thanks.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Is it a recent paper? What estimate have they proved? Anyway, this is a classical, notoriously difficult problem; so, definitely interesting on its own. $\endgroup$
    – Seva
    Commented Sep 3, 2019 at 12:38
  • $\begingroup$ @Seva, no. they are classic. but I saw one related to from Terence Tao (The Elliott–Halberstam conjecture implies the Vinogradov least quadratic nonresidue conjecture). $\endgroup$
    – asad
    Commented Sep 3, 2019 at 12:54
  • 3
    $\begingroup$ For instance, if we want to explicitly construct a field with $p^2$ elements, we can take the quotient $$\mathbb{F}_p[x]/(x^2-a),$$ where $a$ is not a square in $\mathbb{F}_p$. $\endgroup$
    – Francesco Polizzi
    Commented Sep 3, 2019 at 13:44
  • 5
    $\begingroup$ Tonelli–Shanks algorithm en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm $\endgroup$
    – Alexey Ustinov
    Commented Sep 3, 2019 at 14:22

1 Answer 1

Reset to default
2
$\begingroup$

Let me expand my comment into a short answer.

The explicit knowledge of a quadratic nonresidue $a$ modulo $p$ allows us to construct the irreducible quadratic polynomial $x^2-a$ in $\mathbb{F}_p[x]$, and so we have a very explicit description of the field with $p^2$ elements as $$\mathbb{F}_{p^2}=\mathbb{F}_p[x]/(x^2-a).$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .