1
$\begingroup$

Let $p$ and $q$ be odd primes s.t. $p 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$
  • 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
    @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