# Running Time for Fermat's Factorization Algorithm

Let $p$ and $q$ be odd primes s.t. $p<q$ and $n= pq$. How many cycles will Fermat's Factorization produce for $n = pq$? Here is some sample data I iterated: (I am having trouble solving for an explicit formula in terms of $n, p$ and $q$

FermatFactorization(15) (5)(3)
NumCycles: 1
FermatFactorization(21) (7)(3)
NumCycles: 2
FermatFactorization(33) (11)(3)
NumCycles: 5
FermatFactorization(35) (7)(5)
NumCycles: 1
FermatFactorization(39) (13)(3)
NumCycles: 6
FermatFactorization(51) (17)(3)
NumCycles: 9
FermatFactorization(55) (11)(5)
NumCycles: 3
FermatFactorization(57) (19)(3)
NumCycles: 11
FermatFactorization(65) (13)(5)
NumCycles: 4
FermatFactorization(69) (23)(3)
NumCycles: 14
FermatFactorization(77) (11)(7)
NumCycles: 2
FermatFactorization(85) (17)(5)
NumCycles: 7
FermatFactorization(87) (29)(3)
NumCycles: 19
FermatFactorization(91) (13)(7)
NumCycles: 3
FermatFactorization(93) (31)(3)
NumCycles: 21
FermatFactorization(95) (19)(5)
NumCycles: 9

1. I want to find an explicit formula for the number of cycles in terms of $n, p, q$
-
Fermat's factorization method is basically just trial division starting at the square root rather than starting at 2. So it's just as slow as trial division, the only real significance of the algorithm is that it is easy to do by hand. – DanielV Feb 16 '15 at 0:41

There are three cases for running time.

1st case: let $q-p = 2n$ where $n$ is odd then the running time $\sim= (((n(n - 4) + 7)/4 - p) + 2)$

2nd case let $q - p = 4n$ where $n$ is odd then the running time $\sim= ((n(n - 2) + 2) - p) + 2)$

3rd case let $q - p = 4n$ where $n$ is even then the running time $\sim= ((n(n - 2) + 1) - p) + 2)$

-

I believe you can do this in $O(n^{1/4+ \epsilon})$ time. See James McKee's article here and another Arxiv Preprint by Carella here . Also, Knuth's TAOCP Volume 2 discusses this in Pages 371-372, in Sec. 4.5.4. It doesn't give the complexity analysis though.

-
That is a great running time! Did you see the last part of my question? – CodeKingPlusPlus Oct 11 '12 at 19:48
No easy answer ,but I think this may be dug up from Theorems 2 & 3 of the Carella paper. – Ganesh Oct 11 '12 at 19:52
@CodeKingPlusPlus, $O(n^{1/4+ \epsilon})$ is not a great running time: it's exponential in the number of digits of $n$. – lhf Oct 11 '12 at 19:59
I don't think McKee is doing what CodeKing is doing, and I don't think $O(n^{1/4+\epsilon})$ applies to what CodeKing is doing. Actually, I'm not at all sure what CodeKing is doing, but I have a hunch it's $O(n)$, as bad as just dividing by all the numbers from 1 up to $n$. – Gerry Myerson Oct 12 '12 at 5:44
@lhf Not great, but not bad either for certain ranges. Other famous non deterministic methods are of the same order (e.g. Pollard's rho). There is also a deterministic method (Pollard-Strassen) that achieves this complexity. The method of Lehman, cited in the article, is deterministic $O(n^{1/3})$. I've always considered that very cute. – WimC Jun 10 '14 at 19:08