2
$\begingroup$

I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes:

factorize n = 88416763 in case that you know that the square roots of 51733469 (mod 88416763) are 50224876, 38191887, 22222, 88394541.

$\endgroup$

1 Answer 1

3
$\begingroup$

Following CodesInChaos request to turn the hint into a full solution, here's a full solution. Let $x$ and $y$ be square roots of $51733469$ modulo $n$. It follows that

$$0\equiv x^2-y^2=(x+y)(x-y)\,(\textrm{mod }n).$$

If we choose $x\not\equiv \pm y\, (\textrm{mod }n)$, then $x-y$ and $x+y$ are not divisible by $n$. On the other hand, $n\mid (x+y)(x-y)$, so $\gcd(x+y,n)\neq 1\neq \gcd(x-y,n)$. Choosing for instance $x = 38191887$ and $y=22222$ gives

$$\gcd(x-y,n) = 8887,\;\; \gcd(x+y,n)=9949.$$

A direct computation shows that $n=88416763 = 8887\times 9949$. It's easy to use the Sieve of Eratosthenes to calculate all primes smaller than $100$ and then check if any of them divide either factor, which will show that $8887$ and $9949$ are both prime.

$\endgroup$
7
  • $\begingroup$ so when I know that (x-y)(x+y)=0 mod p and (x-y)(x+y)=0 mod q how can i find q and p? $\endgroup$
    – dante
    Nov 4, 2014 at 13:17
  • $\begingroup$ What happens when $(x+y)(x-y)=0\,\textrm{mod }N$ and you know that $|x+y|,|x-y|<N$? $\endgroup$ Nov 4, 2014 at 13:23
  • $\begingroup$ well than x+y=0 mod p and x-y=0 mod q $\endgroup$
    – dante
    Nov 4, 2014 at 13:34
  • $\begingroup$ so what can you say about greatest common divisors? $\endgroup$ Nov 4, 2014 at 13:40
  • $\begingroup$ oh ofc I just make gcd((x+y),(N-(x+y)) and i get p. Thank you for your time $\endgroup$
    – dante
    Nov 4, 2014 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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