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$
2
$\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$
  • $\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 '14 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$ – Edvard Fagerholm Nov 4 '14 at 13:23
  • $\begingroup$ well than x+y=0 mod p and x-y=0 mod q $\endgroup$ – dante Nov 4 '14 at 13:34
  • $\begingroup$ so what can you say about greatest common divisors? $\endgroup$ – Edvard Fagerholm Nov 4 '14 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 '14 at 13:48

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.