1
$\begingroup$

This is a sequel to How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from "if all these powers of $2$ agree"?


Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [p. 16]

The multiplicative group (mod $p^\alpha$) for any odd prime power $p^\alpha$ is cyclic [Knuth 1981], so for any odd prime power $p_i^{a_i}$, the probability is at most 1/2 of choosing an $x_i$ having any particular power of two as the largest divisor of its order $r_i$. Thus each of these powers of 2 has at most a 50% probability of agreeing with the previous ones, so all k of them agree with probability at most $1/2^{k−1}$, and there is at least a $1 - 1/2^{k-1}$ chance that the $x$ we choose is good. This scheme will thus work as long as $n$ is odd and not a prime power; finding factors of prime powers can be done efficiently with classical methods.

  1. Why is the probability of choosing an $x_i$ having any particular power of two as the largest divisor of its order $r_i$ at most $\frac{1}{2}$?

  2. Why is the probability of each of these powers of 2 agreeing with the previous at most 50%?


Related: Expected repetitions of the quantum part of Shor's algorithm

$\endgroup$
2
$\begingroup$
  1. Let $m = p_{i}^{a_i-1}(p_i-1)$ – the order of our multiplicative group. Cyclic group means there is a primitive element $a$ with the order equals to the size of the group, that is $m$. Moreover, the cyclic group consists of the elements $a^1, a^2, ... , a^m=1$. The order of the element $a^k$ is exactly $m/\text{gcd}(m, k)$. If $m/\text{gcd}(m, k)$ has a particular power of $2$ as its largest divisor, then $k$ has corresponding particular power of $2$. All numbers $k$, i.e. numbers from $1$ to $m$, are split into sets by this power value. And the largest set can't have more than $m/2$ elements, because there is a set with all odd numbers $k$, with a size of $m/2$.

  2. Because the probability of observing two same results in two experiments is $$P_1 \cdot P_1 + P_2\cdot P_2 + ... + P_j\cdot P_j,$$ where $(P_1,...,P_j)$ – is the probability distribution for events. Since every $P_i \leq 1/2$ and $P_1+..+P_j = 1$, that total expression is also $ \leq 1/2 $ (observe that $P_i\cdot P_i \leq P_i/2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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