Question

In this problem we will show that if N=pq is the product of two odd primes, and if x is chosen uniformly at random between 0 and N-1, such that $\mathbf{gcd}\left(x,N\right)\mathbf{=}\mathbf{1}$, then with probability at least role="math" localid="1658908286522" $\frac{\mathbf{3}}{\mathbf{8}}$, the order r of x mod N is even, and more over ${\mathbf{x}}^{\frac{\mathbf{r}}{\mathbf{2}}}$is a nontrivial square root of 1 mod N.

a) Let p be an odd prime and let x be a uniformly random number modulo p. Show that the order of x mod p is even with probability at least$\frac{\mathbf{1}}{\mathbf{2}}$ (Hint:Use Fermat’s little theorem (Section 1.3).)

b) Use the Chinese remainder theorem (Exercise 1.37) to show that with probability at least $\frac{\mathbf{3}}{\mathbf{4}}$, the order r of x mod N is even.

c) If r is even, prove that the probability that role="math" localid="1658908648251" ${\mathbf{x}}^{\frac{\mathbf{r}}{\mathbf{2}}}\mathbf{\equiv }\mathbf{\pm }\mathbf{1}$is at most$\frac{\mathbf{1}}{\mathbf{2}}$.

Short answer

$$\begin{gathered} \mathrm{a})\mathrm{The}\mathrm{order}\mathrm{of}\mathrm{x}\mathrm{mod}\mathrm{p}\mathrm{is}\mathrm{even}\mathrm{with}\mathrm{probability}\frac{1}{2} \\ \mathrm{b})\mathrm{It}\mathrm{is}\mathrm{even}\mathrm{with}\mathrm{probability}\frac{3}{4} \\ \mathrm{c})\mathrm{The}\mathrm{probability}{\mathrm{x}}^{\frac{\mathrm{r}}{2}}\equiv \pm 1\mathrm{is}\mathrm{at}\mathrm{most}\frac{1}{2}. \end{gathered}$$

Step-by-step solution

Step 1:Show that the order of x mod p is even with probability at least 12

(a)

For the given odd number p and random number modulo p, the aim is to prove that the order of x mod p is even.

Assume that r be the order of x. As per the Fermat's little theorem

$x^{\left(p-1\right)}=1modp$

In a cyclic group, there exists an element that generates all the other elements of the group.

Because, the multiplicative group modulo p is a cycle group, elements x can be written as localid="1658909125595" $g^{K}modp$where cyclic group element g is generates all other elements of the group. It is given that x is uniformly random.

So, the probability of K being odd is $\frac{1}{2}$. Because the value of p is odd, and the value of K is odd as well, r has to be even.

Also, the is even with probability$\frac{1}{2}$

Therefore, the order of x mod p is even with probability$\frac{1}{2}$

Step 2:(b)Proof using Chinese remainder theorem:

The objective is to use the Chinese remainder theorem to prove that the order r of x mod N is even.

The value of N=pq where p and q are odd prime numbers.

The Chinese remainder theorem states that choosing uniformly at random x from 0 to N or y from 0 to p-1 or z to q -1 are the same.

Assume that r-1 be the order of x-1 and r-2 be the order of x-2 .

Since, p and q are odd, N is odd too.

Also, because both the orders r-1 and r-2 are even, the probability that r is even is at least$\frac{3}{4}$. Because, the order r is even when either is even r-1 or r-2 is even.

Therefore, it is even with probability$\frac{3}{4}$.

Step 3:c)Proof:

The objective is to prove that the probability of is $x^{\frac{r}{2}}\equiv \pm 1atmost\frac{1}{2}$ .

The Chinese theorem states that there are four roots of the 1 modulo prime number.

Among, these four roots, only two of the roots$x^{\frac{r}{2}}\equiv 1modp$.

Because from the possible four roots, at most two roots gives the desired result, the probability is less than or equal to $\frac{1}{2}$

Therefore, the probability of is$x^{\frac{r}{2}}\equiv \pm 1atmost\frac{1}{2}$