2
$\begingroup$

In the paper Safe Prime Generation with a Combined Sieve by Michael J. Wiener, the author states:

For any small odd prime $r$, we can eliminate candidates for $q$ that are congruent to $(r − 1)/2\mod r$ because they lead to $p$ being divisible by $r$.

(where $p = 2q + 1$)

But he did not explain why for the uninitiated. As such I would like to know why $(p-1)/2 \equiv (r-1)/2 \mod r$ means that $p \equiv 0 \mod r$.

Or to put it another way, why does $q \equiv (r-1)/2 \mod r$ mean that $2q \equiv -1 \mod r$?

  • 0
    That's OK, I k$n$ew that quickly e$n$ough would come a$n$ answer that you could accept.2011-06-14

1 Answers 1

2

Just expand:

$\begin{eqnarray} q&\equiv&(r-1)/2\mod r\\ 2q&\equiv&r-1\mod r\\ 2q&\equiv&-1\mod r \end{eqnarray}$