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
    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
    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
    Sep 3, 2019 at 13:44
  • 5
    $\begingroup$ Tonelli–Shanks algorithm en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm $\endgroup$
    – Alexey Ustinov
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.