Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

   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!

share|cite|improve this question
up vote 3 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.