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