Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$
share|cite|improve this question
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)$

Fore more reference

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.