# Tag Info

What you are doing is the following: Choose a random number $r$ in $[1,2^n-1]$. Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1. Check if $(\frac{r}{p})=(\frac{r}{q})=1$($(\frac{a}{n})$ denotes the jacobi symbol), if not go to 1. So in order to ...