Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 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.

share|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 at 19:08

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 http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html

share|improve this answer

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.