3
$\begingroup$

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

  • 0
    *I guess this problem might only be comprehensible when you already read the whole paper*... If your guess is right, this is not a question for this site.2012-06-24
  • 0
    You just need to read the overview of the algorithm and the small proof of the main theorem, not the whole paper.2012-06-24

1 Answers 1

2

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

  • 0
    Thank you very much for your help! I am currently thinking about it :-) Are you sure we can assume that N=4hv? I thought the given bound might come from the expected value for a square to be p-smooth (the probability holds $p<\frac{1}{v}$, thus $E) and this procedure times (h+1) times the expected value of step 5 (which is 2), thus $$v \cdot (h+1) \cdot 2$$, which is close to Dixons bound as well and seems legit to me. But its probabilistic. What do you think of this bound?2012-06-24
  • 0
    This is basically the same bound but without the "safety margin" that allows to derive a rigorous bound on the probability of failure (with Chebyshev's inequality). Under the assumption that $N$ is nothing more than a cutoff on the number of tests, $N$ just needs to be high enough for the probability of success to be high, and since this bound is valid for all $N\ge 4hv$ we should be able to take $N=4hv$.2012-06-25
  • 0
    Wow, I am delighted! :-) Thank you for your answer, I understand it now! Great work, best regards, Robert2012-06-25
  • 0
    My pleasure :-) Don't forget to accept the answer so that the question doesn't show up as unanswered in the list of questions.2012-06-25