. Consider the situation where $$$x^2 \equiv y^2 \pmod{p}$$$, this is equivalent to saying that $$$x^2 - y^2 \equiv 0 \pmod{p}$$$. Using the difference-of-squares formula, we get $$$(x - y) \cdot (x + y) \equiv 0 \pmod{p}$$$. It follows that either $$$x - y \equiv 0 \pmod{p}$$$ or $$$x + y \equiv 0 \pmod{p}$$$, that is, either $$$x \equiv y \pmod{p}$$$ or $$$x \equiv -y \pmod{p}$$$.

It turns out that all numbers split into pairs $$$x$$$ and $$$-x$$$, so each quadratic deduction has exactly $$$2$$$ roots, with each number being the root of some quadratic deduction $$$\implies$$$ of quadratic deductions of exactly $$$\frac{p - 1}{2}$$$ $$$\implies$$$ of quadratic non-deductions $$$p - 1 - \frac{p - 1}{2} = \frac{p - 1}{2}$$$.

Let $$$x$$$ and $$$y$$$ be quadratic deductions, let $$$a^2 \equiv x \pmod{p}$$$

Unable to parse markup [type=CF_MATHJAX]

$$$H \cdot B = H$$$

Let $$$x$$$ be a quadratic nondeduction and $$$y$$$ be a quadratic deduction, we prove that $$$\frac{1}{y}$$$ is also a quadratic deduction. Let $$$b^2 \equiv y \pmod{p}$$$, then $$$(\frac{1}{b})^2 \equiv \frac{1}{y} \pmod{p}$$$.

$$$x \cdot y \equiv z \pmod{p}$$$

Unable to parse markup [type=CF_MATHJAX]

$$$H \cdot H = B$$$

Let $$$x$$$ and $$$y$$$ be quadratic nondeductions, $$$x \cdot y \equiv z \pmod{p}$$$ and $$$z$$$ a quadratic nondeduction, and $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}$$$

Unable to parse markup [type=CF_MATHJAX]

. First, let us prove that if $$$a$$$ is not divisible by $$$p$$$, then $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$. By Fermat's small theorem, $$$a^{p - 1} \equiv 1 \pmod{p}$$$, it was proved above that any quadratic subtraction has exactly $$$2$$$ roots, with $$$1$$$ being $$$1$$$ and $$$-1$$$. $$$(a^{\frac{p - 1}{2}})^2 = a^{p - 1}$$$ $$$\implies$$$ $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$.

Let $$$a$$$ be a quadratic deduction and $$$x^2 \equiv a \pmod{p}$$$, then $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, since $$$(x^2)^{\frac{p - 1}{2}} = x^{p - 1} \equiv 1 \pmod{p}$$$, and this is true by Fermat's small theorem.

Consider the polynomial $$$x^{{\frac{p - 1}{2}} - 1$$$ modulo $$$p$$$, its degree is $$$\frac{p - 1}{2}$$$ and we have already found it has $$$\frac{p - 1}{2}$$$ roots $$$\implies$$$ no more roots $$$\implies$$$ if $$$b$$$ is quadratically non-degenerate, then $$$b^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

int power(int a, int x, int mod) {
    int res = 1;
    while (x != 0) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p — 1) / 2, p) == 1;
}

mt19937_64 mt(123);

int power(int a, int x, int mod) {
    int res = 1;
    while (x) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p — 1) / 2, p) == 1;
}

int find_i(int p) {
    if (p % 4 == 3) {
        return -1;
    }
    if (p == 2) {
        return 1;
    }
    while (true) {
        int a = mt() % (p — 1) + 1;
        if (!check(a, p)) {
            return power(a, (p — 1) / 4, p);
        }
    }
}