This question refers to the article: G. Ateniese et al., "Remote data checking using provable data possession"
Let $p = 2p' + 1$ and $q = 2q' + 1$ be large primes. $N = pq$.
Let $g$ be a generator of $QR_N$ (the set of quadratic residues modulo $N$). $QR_N$ is the unique cyclic group of $Z_N^*$ of order $p'q'$.
In the article, authors says:
"We can obtain $g$ as $g = a^2 \mod N$, where $a \overset{R}{\leftarrow} Z_N^*$ such that $gcd(a \pm 1, N) = 1$"
where $\overset{R}{\leftarrow}$ denotes the operation of "picking an element at random".
Actually I have two questions:
1) First, I do not exactly understand how to interpret the author's sentence. Is it:
"[...] such that $gcd(a+1,N) = 1$ and $gcd(a-1,N) = 1$" ?
Or rather it is:
"[...] such that $gcd(a+1,N) = 1$ or $gcd(a-1,N) = 1$" ?
I think the second one (or) is the correct interpretation, but I'm not sure, and in any case I don't see why it is so.
Can any one provide me a proof?
2) Second, I'm wondering how to efficiently choose $a$ at random.
For a prime $p$ it is trivial to choose an element in $Z_p^*$ since $Z_p^* = \lbrace 1, \dots, p - 1\rbrace$.
But here $N$ is not prime. The only algorithm that comes to my mind is:
repeat pick a random number a in [1, N-1] until gcd(a, N) = 1
Is there a more efficient way to compute $a$?
Thank you in advance!