How to compute a generator of this cyclic quadratic residue group? 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!
 A: The author means and.
You want $g$ to have multiplicative order $p'q'$ mod $N$, so $g$ is the square of an element $a$ of order $2p'q'$.  Clearly we need to have $a$ relatively prime to $N$.
Necessity of condition
Calculating a gcd with $N$ is fancy talk for "Does $p$ or $q$ divide it?" If $p$ divides $a^2-1$, then consider $a^{q-1} -1$. It is divisible by $q$ by Fermat's little theorem, but it is also divisible by $p$ since $q-1 = 2q'$ and $a^2$ is congruent to 1 mod $p$.  Hence if $p$ divides $a^2-1$, then $a$ only has order dividing $2q'$.  Since $p$ is prime, $p$ divides $a^2-1 = (a-1)(a+1)$ if and only if it divides $a-1$ or $a+1$.  Hence you need to make sure $p$ does not divide either of them.
So it is necessary that $\gcd(N,a\pm1)=1$ (where we mean and).
Sufficiency of condition
The multiplicative group mod $N$ has structure $C_2 \times C_{2p'q'}$ so the only orders other than $2p'q'$ and $p'q'$ are $2, p', q', 2p', 2q'$. We need to rule out these last 5 possible orders.
If the order of $a$ is 2, then $\gcd(a^2-1,N)=N$.
If $a^{p'} \equiv 1 \mod N$, then $a^{p'} \equiv 1 \mod q$, but $p'$ and $q-1=2q'$ are relatively prime (assuming $p\neq q$; never use $N=p^2$), so $a \equiv 1 \mod q$ and so $\gcd(a^2-1,N)=q$.
The other cases follow similarly.
Finding one quickly
We take advantage of the fact that almost every element works:
isGoodNumber = function( a, p, q ) {
  local aModP, aModQ;
  aModP = a mod p;
  if ( ( aModP == 0 ) || ( aModP == 1 ) || ( aModP == (p-1) ) )
    return false;
  aModQ = a mod q;
  if ( ( aModQ == 0 ) || ( aModQ == 1 ) || ( aModQ == (q-1) ) )
    return false;
  return true;
}

How many bad numbers are there? Well $q=N/p$ are divisible by $p$, $p=N/q$ are divisible by $q$, so that is at most $3q + 3p$ bad numbers (the factor of 3 being "0, 1, or -1").  The actual number is a little lower.  How many numbers are there total? $pq$.  What percentage are good numbers? $\frac{pq - 3q - 3p}{pq} = 1 - \tfrac3p - \frac3q \approx 100\%$ as long as $p$ and $q$ are large.
In other words:
repeat a := Random( [1..N] );
until (a mod p notin [0,1,p-1]) and (a mod q notin [0,1,q-1]);

Is probably not actually going to repeat.  It will probably find you a good $a$ on the first try.  Don't forget to square it to get $g$. (If it was already a $g$, then squaring it won't hurt it.)
