With fgrieu's idea: If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be ...

I give an answer summarizing and precising the comments you provided. Being invertible in $\mathbb{Z}_{n }$ is equivalent to having some power equal to 1. If $b$ is invertible there exist $b^{-1}$ ...

Consider the following game: I assume certain familiarity with the definitions of Katz and Lindell book (this is exercise 3.14 in the book). In particular, $O$ is denoting an oracle. It can be either ...

The solution proposed in Katz and Lindell for this goes along these lines. Let $q(n)$ be a polynomial upper-bound on the length of the ciphertext when $\Pi$ is used to encrypt a single bit, i.e., if ...

Hales proposed and verified a proof for the group law of elliptic curves in Edwards form. It does not use sophisticated tools. I'm currently porting his proof fully into a proof assistant.

The more space efficient but cannot always be reverted, for instance if one inputs $m = 1$. The second space efficient but can always be reverted, this appears in Wikipedia entry as bit padding. and ...
Thanks to poncho's hints we can work as follows: 1.Compute $(g^r)^q$. I claim that: \$ (g^r)^q = \begin{cases} 1 &\quad\text{if r is even}\\ \neq 1 &\quad\text{if r is odd}...