Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small.

Suppose that $u=|p-q|<20$ and $p \times q =2189284635403183$. Find the values of $p$ and $q$.

I have no idea how to compute $p$ and $q$. I use calculator to compute square root of thr product. But it is definitely not correct as I get something ends with $2$. Can anyone help me?

share|improve this question
1  
1) Compute the square root of the product. 2) Go to the next odd number. 3) Test if division works. 4) If not, add 2 and repeat from step 3. –  CodesInChaos yesterday
1  
If it exists $l$ such that $N + l^2$ is a square, say $t^2$, over the integers, you can factorize $N = (t-l) (t+l) $. Try to find that $l$. Call $p=t-l$ and $q=t+l$, if you compute the difference: $|p-q| = 2l$, so that give you a upper bound for your tests. –  ddddavidee yesterday
    
It is correct that "The difference between $p$ and $q$ should not be small"; however, under the assumption that $p$ and $q$ are randomly seeded and appropriately large for cryptographic use, odds are entirely negligible that the difference between $p$ and $q$ is dangerously small. So much that the (often mandated) check that$|p-q|$ is above some limit really is useful only as an additional check that said assumptions hold, and to reassure those who do not trust math. –  fgrieu yesterday

2 Answers 2

First, note that if you know $p-q=a$ and $p+q=b$, for some $a,b$, you have two equations with two unknowns and can solve for $p,q$.

Now,

$$ n=p*q=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$$

Rearrange

$$ \left(\frac{p+q}{2}\right)^2 = n + \left(\frac{p-q}{2}\right)^2$$

Then start guessing values for $p-q$. Start with $2$ and substitute in to the equation. Then check to see if the square root of the right hand side is a whole number. If it is, you have found $p-q$. You can then solve for $p+q$ easily. Then you can solve for $p,q$. Otherwise, try 4, 6, 8,... until RHS is a square.

share|improve this answer
    
Where is the advantage of this over straight up trial division starting at $\sqrt{n}$? –  CodesInChaos yesterday
1  
The big benefit of this approach is that it works not just for a small $p-q$ difference, but also when $p-q$ might come from a small range of numbers (which could be fairly large themselves). For this specific question, starting at $\sqrt{n}$ is likely the better option, but I didn't want to steal your comment (which should be an answer) :) –  mikeazo yesterday
1  
@mikeaso: Your technique makes $(p-q)/2$ guesses. $\;$ I initially thought it was equivalent to the Fermat factorization method (see Wikipedia or MathWorld), but the later makes about $(p-q)^2\over8\sqrt n$ guesses, which can be MUCH less. With $n=2189284635403183$ (such that $p-q=18)$, your technique makes $9$ guesses, Fermat's only $1$. With the similarly sized $n=2189283205227561$ (such that $p-q=40040)$, your technique makes $20020$ guesses, Fermat's only $5$. –  fgrieu 7 hours ago
1  
@fgrieu very interesting. –  mikeazo 7 hours ago
1  
@fgrieu, so the method I outlined is really no better than trial division, but fermat's method is. I hope you plan to write up an answer. –  mikeazo 7 hours ago

We want a non-trivial factorization of an odd integer $n\ge7$ into positive integers $p$ and $q$ (as $n=p\times q$), knowing that that such factorization with $|p-q|$ suitably small exists. We'll make that bound: $|p-q|<(64n)^{1/4}$. With the given $n=2189284635403183$, that bound translates to $|p-q|<19347$, which holds by a mile since $|p−q|<20$ is given.

The following non-iterative algorithm outputs a non-trivial factorization of $n$:

  1. compute $a=\lceil\sqrt n\rceil$ (that is, the smallest non-negative integer which square is at least $n$)
  2. compute $s=a^2-n$, which amazingly will be the square of some integer
  3. compute $b=\sqrt s$ (that is, the non-negative number which square is $s$)
  4. output $a+b$ and $a-b$.

Proof: We have as hypothesis that there exists integers $p$ and $q$ with $n=p\times q$, $|p-q|<(64n)^{1/4}$, $n$ odd with $n\ge5$. Without loss of generality we reorder $p$ and $q$ so that $p\ge q$.

We know $p$ and $q$ are odd, since their product is. Thus, when we define $c={p+q\over2}$ and $d={p-q\over2}$, these are non-negative integers. Further, $c^2-n=d^2$ holds.

In step 1 of our algorithm, $a$ is computed as the only non-negative integer $x$ satisfying $x^2-n\ge 0$ and $(x-1)^2-n<0$. From $c^2-n=d^2$ it follows that $x=c$ satisfies the first of these conditions. The second condition is $(x-1)^2<n$, which is satisfied if $0\le x-1<\sqrt n$, that is $1\le x<\sqrt n+1$. $x=c$ satisfies $1\le x$, since $c={p+q\over2}$ with $p\ge1$ and $q\ge1$. Thus $c<\sqrt n+1$ would imply $a=c$.

Towards this goal, it is enough to prove $c^2<(\sqrt n+1)^2$, that is $n+d^2<(\sqrt n+1)^2$, that is $({p-q\over2})^2<(\sqrt n+1)^2-n$, that is $(p-q)^2<4((\sqrt n+1)^2-n)$. Our hypothesis $|p-q|<(64n)^{1/4}$ implies that $(p-q)^2<8\sqrt n$, hence proving $2\sqrt n\le(\sqrt n+1)^2-n$ is enough. An easy simplification shows that.

We have shown that step 1 produces $a=c$; it follows that step 2 produces $s=a^2-n$ equal to $d^2$; thus step 3 produce $b$ equal to $d$; thus step 4 outputs $p$ (for $a+b$) and $q$ (for $a-b$).

It only remains to show that this factorization $n=p\times q$ can't be the trivial $(p,q)=(n,1)$. We consider the function $f$ over $\mathbb R$ with $f(x)=(x-1)^4-64x$. $f(7)>0$, $f'(x)=4(x-1)^3-64$ is such that $x\ge7\implies f'(x)>0$, hence $x\ge7\implies f(x)>0$. Hence $f(n)>0$, that is $(n-1)^4>64n$, thus $n-1>(64n)^{1/4}$. Hence $p=n$ and $q=1$ would contradict $|p-q|<(64n)^{1/4}$, and can't hold. Thus step 4 outputs a non-trivial factorization of $n$, Q.E.D.


The above is the Fermat factorization method, reduced to its first step and without any test, because we can given the parameters in the question, and that simplifies our proof. Description of Fermat's method, and standard improvements, would be the subject of a different question.

share|improve this answer

Your Answer

 
discard

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.