1

Can it be said that

$$x^3 + a_4 x + a_6 \; (\text{mod}\,p)$$

is a perfect square half of the time?

Apparently it does not. Simulating the elliptic curve points $\text{mod}\,103217$ only $310$ of them are perfect squares.

>>> from gmpy2 import is_square
>>> P = 103217
>>> len(list(filter(is_square, map(eq, range(P))))) / P
0.0030033812259608397

Yet, reading from Trappe's "Introduction to Cryptography with Coding Theory" (page 356) it's said that

Since $x^3 + a_4 x + a_6$ is a square half of the time, we have about $1/2^K$ chance of failure. (...)

Giuseppe Crinò
  • 273
  • 1
    Is is_square checking if your numbers are squares of integers, or squares of residue classes of integers (i.e., working mod $p$)? I'm not sure this resolves things, but I suspect it will. – pjs36 Jan 28 '17 at 23:12
  • @pjs36 I guess that it checks if they're squares of integers. Indeed, implementing that function as def is_square(x): return ceil(sqrt(x)) ** 2 == x yield the same result - i.e. $.3%$ – Giuseppe Crinò Jan 28 '17 at 23:23
  • 1
    But Trappe means "$x^3+a_4x+a_6$ is a square modulo $p$" - that is, there is some $k$ such that $x^3-a_4x+a_6-k^2$ is divisible by $p$. – Thomas Andrews Jan 28 '17 at 23:26
  • Yeah, since the book mentions the polynomial is evaluated mod $p$, I'm guessing it means square in this sense (e.g. $4^2 = 16 \equiv 5 \pmod {11}$, so if $p = 11$, we'd say $5$ is a square). I'm not sure if any libraries have functions for determining if something is a quadratic residue, but that's what you're looking for (I suspect). I know Sage has this functionality – pjs36 Jan 28 '17 at 23:30
  • 1
    If $p$ is prime, then about half of the finite field elements are quadratic residue ($y$ is a quadratic residue if $\exists x ~ x^2 \equiv y \pmod p$). If $a_6$ ranges uniformly over $0 \dots p - 1$, then $\dots+a_6$ will have a 50% chance of being a quadratic residue. – DanielV Jan 29 '17 at 00:08
  • If $x^3+a_4x+a_6$ is a "permutation polynomial" see this , as approx. the half of the elements of $\mathbb{Z_p}$ are squares, the work is done. – Jean Marie Jan 29 '17 at 00:50

0 Answers0