New answers tagged

3

The paper is rather sloppily written, however it can be changed into the correct statement. The statement in the paper is: She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$. As written, that's wrong. However, if we modify it to: She takes a random ...


2

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} ...



Top 50 recent answers are included