# Tag Info

Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points: in the eBATS benchmarks for a skylake CPU, ronald3072 signature verification (RSA with $e=3$ as an OpenSSL wrapper, by ...
The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$. There are solutions if $a$ is a square modulo both $p$ and $q$. This can be checked by computing the Legendre of symbol of $x$ modulo $p$ and modulo $q$. Assuming that the two Legendre symbols are +1, when $p \equiv 3 \pmod 4$, a square-root of $a$ modulo $p$ is given by $x_p = a^{(p+1)/4} ... 1 Consider two numbers$a$and$b$that square to the same value modulo$n$and don't just differ by the sign. $$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$ Neither of the factors on the left is 0 (or equivalently a multiple of$n$), thus each of them must contain one of the prime factors of$n$. Thus you can use$\operatorname{GCD}(a-b, n)\$ ...