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

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