91Ó°ÊÓ

(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}$

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

The objective is to prove that the probability of is $x^{\frac{r}{2}}≡Â\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}}≡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}}≡Â\pm 1atmost\frac{1}{2}$