0
$\begingroup$

$x$ and $y$ are two number which share a prime factor. You do not know what the prime factor is. Explain how one can factor $x$ and $y$ quickly. Prove it works by using $x = 41685823$ and $y= 39034579$.

I don't really know how to approach this question because sharing a prime factor, does that mean they can share other factors too? Any help would be splendid! Cheers.

Edit: Apparently a classmate said that the two prime are consecutive primes. Maybe this will make the question clearer. Thanks!

$\endgroup$
3
  • 2
    $\begingroup$ hint: gcd computation $\endgroup$
    – Raymond Manzoni
    Mar 19, 2013 at 23:08
  • $\begingroup$ If $x$ and $y$ share a common divisor, $x-y$ and $x+y$ also share that common divisor and may be easier to factor, at least to remove some of the smaller divisors. $\endgroup$
    – Peter Phipps
    Mar 20, 2013 at 0:08
  • $\begingroup$ LOL,I am a student in UofWaterloo and having Math135 class. I think you are probabily one of my classmates. Anyway, I did not get the right way to solve the quention. But I am sure that it is not as simple as using Euclid's algorithm, as the question required to use RSA and required us to find a way to solve it quickly. Meanwile, the question gives the condition that both N1 and N2 has and only has tow prime factors. $\endgroup$
    – user67593
    Mar 20, 2013 at 5:27

1 Answer 1

Reset to default
2
$\begingroup$

You can use Euclid's algorithm to find the greatest common divisor, which the prime will divide. If you are given that $x$ and $y$ are semiprimes, that they each have only two prime factors, you can just divide them each by the GCD and have the factorization. The example numbers you have meet this criterion, but I don't see it in the problem statement. If $x$ and $y$ each had four large prime factors and shared two of them, the GCD would be the product of the two shared factors and the rest would be the product of the other two. That is a factorization, but not a complete one.

$\endgroup$
5
  • $\begingroup$ I'm not quite sure I follow. You are right that my two numbers given in the question dont specify them as semiprimes which is why I am confused on what the best way to do with this question. Should I treat the question as semi primes or can I just pick and choose which prime I want? $\endgroup$
    – Michael
    Mar 19, 2013 at 23:26
  • $\begingroup$ Still factoring $\frac{x}{GCD}$, $\frac{y}{GCD}$ and $GCD$ is most of the times much easier than factoring $x,y$... $\endgroup$
    – N. S.
    Mar 19, 2013 at 23:32
  • $\begingroup$ I asked one of classmates and the question has changed to that they have consecutive primes which factor into them. Does that change the question to make it solvable clearer? Thanks1 $\endgroup$
    – Michael
    Mar 19, 2013 at 23:35
  • $\begingroup$ @Michael: whether the primes are consecutive doesn't matter, just how many there are. If they are about the same size, instead of factoring $x$ you are factoring something about $\sqrt x$, so if you are doing trial division you now need to go up to $x^{\frac 14}$ instead of $x^{\frac 12}$. This is the point of N.S.'s comment. $\endgroup$
    – Ross Millikan
    Mar 19, 2013 at 23:56
  • $\begingroup$ @Michael, please do follow the advice that's been given to you, and apply the Euclidean algorithm to the two numbers. It's only a handful (OK, make it two) of Euclidean divisions. $\endgroup$
    – Andreas Caranti
    Mar 20, 2013 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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