Dixon's random squares algorithm: a step in the proof of its subexp. running time

Question

I am currently working to understand Dixon's running time proof of his subexp integer factorization algorithm (random squares).

But unfortunately I can not follow him at a certain point in his work. His work is available for free here: http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/home.html

My problem occurs on the last page (page 6 of file, named page 260) where he states that in case of success the execution of step 1 is bound by 4hv+2, where h is the number of primes smaller v, and v is a fixed integer depending on n (the number we want to factorize). I really do not have a clue where this bound comes from. It might have to do something with the expected values of some steps in the algorithms, but these bound seems not probalistic as far as I unterstand him.

I guess this problem might only be comprehensible when you already read the whole paper. I am hoping to fluke here.

Best regards! Robert

Answer 1

The $4hv+2$ bound is indeed deterministic, but only applies when we're not in a "bad" case. So the question we need to ask is how "bad" cases are defined.

I think the idea of the author is that the previous paragraph can be read by relaxing the condition $N=v^2+1$ to any $N\ge 4hv$, and in particular $N=4hv$. But then we need to change the last line of the paragraph:

$$2c^{-1}+2^{-h}=O(vN^{-1})+O(n^{-1})=O(h^{-1})$$

This means that we also need to change the next sentence so that it reads

All but $O(h^{-1})$ of the $A_L$ will have $N_1\le 4hv+2$.

instead of $O(v^{-1})$. I don't think there is any reason for choosing $4hv+2$ instead of $4hv+1$.

But this doesn't matter in the grand scheme of things, because it still allows us to write the bound

$$\begin{align} &O(h^{-1}(N+1)h\log n + (4hv+2)h\log n)\quad\text{(*)}\\ =&O(N\log n)+O(vh^2\log n)\\ =&O(vh^2\log n)\\ =&O(v^3) \end{align}$$ (*): in the original text, $n\log n$ is a typo and should of course read $h\log n$.