# Bound on success Probability for Regev's factoring algorithm

Theorem 4.1 in Regev's paper talks about a theorem due to Pomerance as follows:

Theorem 4.1: Suppose G is a finite abelian group with minimal number of generators $$r$$. Then, when choosing elements from $$G$$ independently and uniformly, the expected number of elements needed to generate G is less than r + σ, where σ = 2.118456563....

Then, Corollary 4.2 is derived from it, which states that $$r+4$$ uniform and random sample from $$G$$ is sufficient to generate $$G$$ with a probability of at least $$1/2$$. Or the sample is 'likely' to contain the basis for the lattice (group). As per the paper, the proof is as follows:

Proof: Otherwise, with probability at least 1/2, r+ 5 elements are needed to generate G. Since this random variable is never smaller than r by assumption, and its expectation is at least r + 5/2 > r + σ, in contradiction.

I need some help understanding the above-highlighted line.

This is just Markov's inequality that states that for a positive random variable $$X$$ and $$a > 0$$ then $$P( X \geq a ) \leq \frac{E(X)}{a}.$$ see the wikipedia: https://en.wikipedia.org/wiki/Markov%27s_inequality.
Now, $$a = 5$$ and $$X$$ is the number of elements needed to generate the group minus $$r$$. Thus,
$$\frac{5}{2} \leq E(X).$$
If $$Y$$ is the random variables corresponding to the number of samples needed to generate the group, then $$X = Y-r$$ and so
$$\frac{5}{2} + r \leq E(Y).$$
• Good, point we need to use that $X \geq r$. Let me edit. Apr 4 at 17:25