Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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!

share|cite|improve this answer
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. – Rick Decker Nov 15 '12 at 2:26

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.