# If p mod 4 = 3, does choosing a=1 in the parameters of EdDSA really achieve best performance?

I am implementing Ed448 in my crypto library. I found that if $$a=-1$$, I can use the formulas describing in this webpage, which saves some multiplications.

However, in the page 6 of RFC 8032, it says

A non-zero square element $$a$$ of $$GF(p)$$. The usual recommendation for best performance is $$a = -1$$ if $$p \bmod 4 = 1$$, and $$a = 1$$ if $$p \bmod 4 = 3$$.

Why does choosing $$a=1$$ if $$p \bmod 4 = 3$$ achieve the best performance?

## 1 Answer

There are probably better ways to do this, but at least this is quite elementary.

Let $p$ be an odd prime, and $\mathbb{F}_p^*=\langle\alpha\rangle$ be the cyclic subgroup of order $p-1$. Let $x\in\mathbb{F}_p^*$ such that $x^2=-1$. Take $t\in\{0,\ldots,p-2\}$ such that $x=\alpha^t$. Then $\alpha^{4t}=x^4=1$, so $4t\equiv 0\bmod p-1$. As $0\leq 4t\leq 4p-8$, there are 4 options:

1. $4t=0$. Then $t=0$, so $x=1$, a contradiction.
2. $4t=p-1$. Then $p=4t+1$, so $p\equiv 1\bmod 4$.
3. $4t=2p-2$. Then $t = (p-1)/2$, so $x^2 = 1$, a contradiction.
4. $4t = 3p-3$. Then $3p\equiv 3\bmod 4$, so $p\equiv 1\bmod 4$.

In other words, $-1$ is not a square if $p\equiv 3\bmod 4$. This is an explicit assumption in your quote.