Pattern in Fermat Factorization

Question

I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. Here is a set of integers I have interated over:

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)

Can you find the formula for the given data as described above?

Answer 1

The first question to ask is how is the value of $X = s + a$ ( half the sum of the factors) related to $p\text{ and }q$, the factors of $N$. $2X = 2s + 2a$ is the sum of the factors of $N$; how can we relate this to $p\text{ and }q$?

We define p and q as follows: $$ \begin{align} s &= \lfloor\sqrt{N}\rfloor\\ q &= s - t &\text{($t$ is an integer)}\\ p &= s + t + k &\text{( $k$ is an integer)} \end{align} $$ I have used $p$ as the larger number as it was used like that in the answer above.

The sum of the factors $= q + p = ( s - t) + ( s + t + k) = 2s + k$.

We also know that the sum of the factors is $2s + 2a$ therefore we have $2s + 2a = 2s + k$, and $a = k/2$.

From this we can use the defined $p$ and $q$ as follows: $$ \begin{align} N &= qp = (s- t)(s + t + k)\\ N &= s^2 - t^2 + sk - tk\\ \end{align} $$ Solving for $k$ gives $k = (t^2 + N - s^2)/(s - t)$

This will give you a formula for $2a$, so half the value will be the values that you have calculated above.

There is no formula in terms of $N,p\text{ and }q$ though!

Answer 2

I'm going to assume that what you are doing to factor $n$ is you are adding odd numbers until you get a square, e.g., to factor 65, you go $$65+1=66;\quad 66+3=69;\quad 69+5=74;\quad 74+7=81=9^2$$ Having done 4 cycles, you have $$65+4^2=9^2;\quad 65=9^2-4^2=(9+4)(9-4)=(13)(5)$$ In general, and assuming $p\gt q$, we have $$n=pq=\Bigl({p+q\over2}\Bigr)^2-\Bigl({p-q\over2}\Bigr)^2$$ so the number of cycles is $(p-q)/2$.

If this is the correct decryption of your question, then there are lots of errors in your table.

Answer 3

There are three cases for running time. 1st case: let $q-p = 2n$ where $n$ is odd then the running time $t \approx (((n(n - 4) + 7)/4 - p) + 2)$

2nd case let $q - p = 4n$ where $n$ is odd then the running time $t \approx ((n(n - 2) + 2) - p) + 2)$

3rd case let $q - p = 4n$ where $n$ is even then the running time $t \approx ((n(n - 2) + 1) - p) + 2)$ Fore more reference http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html