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 Oct 21 at 8:42
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 Oct 21 at 8:48
    
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 Oct 21 at 16:30

2 Answers 2

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists.

Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by at most (very slightly less than) $|p-q|\over2$ candidates. Some easy speedups are possible (skipping even candidates, generalizable to candidates divisible by the first few small primes).

The method described in this comment, and equivalently in this answer, also work. They succeed after testing at most $|p-q|\over2$ candidates. Depending on implementation (of the squareness test in particular), speed can be slower or faster than trial division.


I'll describe a method that avoids any trial and error under the assumption that $|p-q|<(64n)^{1/4}$. With the given $n=2189284635403183$, that translates to $|p-q|<19348$, which very comfortably holds since $|p−q|<20$ is given.

Theorem: Given any odd integer $n$, if there exist unknown integers $p$ and $q$ with $n=p\times q$ and $(p-q)^2<8\sqrt n$, the following non-iterative algorithm outputs these $p$ and $q$:

  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:

  • 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$.
  • Since $c\ge0$, we can equivalently 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-(\sqrt n)^2))$, that is $(p-q)^2<4(2\sqrt n+1)$. It follows from our hypothesis $(p-q)^2<8\sqrt n$.
  • We have shown that step 1 produces $a=c$; thus step 2 produces $s=a^2-n$ equal to $d^2$; thus step 3 produces $b$ equal to $d$; thus step 4 outputs $p$ (for $a+b$) and $q$ (for $a-b$), Q.E.D.

The above is the basic Fermat factorization method, but reduced to its first step and without any test (because we can do without it in the question, and that simplifies our algorithm and proof). The full basic Fermat method performs $\Big\lceil{(p-q)^2\over8\sqrt n}\Big\rceil$ tests, and thus requires less computing effort than trial division by a factor of $O\big({\sqrt n\over|p-q|}\big)$ as a first-order approximation; this can be huge, but only when $|p-q|$ is much smaller than likely under random selection of $p$ and $q$ in an interval of width a sizable fraction of $\sqrt n$. Description of Fermat's methods, classic improvements, and computing cost, would be the subject of a different question.

share|improve this answer

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 Oct 21 at 14:59
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 Oct 21 at 15:20
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 2 days ago
1  
@fgrieu very interesting. –  mikeazo 2 days 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 2 days ago

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.