# 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$?

-

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$.

## 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.)

-
Thank you a lot @JackSchmidt, I missed the fact that p' and q' are prime numbers too. – hellow Jul 6 '12 at 18:28