0
$\begingroup$

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?

3 Answers 3

3

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!

  • 0
    I've taken the liberty of formatting your mathematics. To see what I've done, click on the "edited" text above my name and then select "source". For a tutorial on how to do this yourself, see [here](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference).2012-11-15
1

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.

0

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