1
$\begingroup$

Let $p$ and $q$ be odd primes s.t. $pFermat'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$
  • 0
    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.2015-02-16

2 Answers 2

1

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

0

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.

  • 0
    That is a great running time! Did you see the last part of my question?2012-10-11
  • 0
    No easy answer ,but I think this may be dug up from Theorems 2 & 3 of the Carella paper.2012-10-11
  • 0
    @CodeKingPlusPlus, $O(n^{1/4+ \epsilon})$ is *not* a great running time: it's exponential in the number of digits of $n$.2012-10-11
  • 0
    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$.2012-10-12
  • 0
    @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.2014-06-10