0

x^2 = 71 mod 77 has four answers as x = 15 mod 77, x = 29 mod 77 , x= −15 mod 77 and x = −29 mod 77. According to the formula when we know the solutions we can try to factorize n as follows: 

 x = ±a,±b of x2 = y mod n where n = p × q
 a = b mod p and a = −b mod q.

However when I plug in a's and b's to the formula it doesnt give me the result ?

Cem Aytekin
  • 45
  • Use the solutions $29$ and $62$ and calculate $\gcd(62-29,77)$ and $\gcd(62+29,77)$ to get the non-trivial factors of $n$. Note that you only get a non-trivial solution, if the sum of the solutions is not divisible by $77$. Taking $15$ and $48$ works as well. – Peter Oct 13 '17 at 14:23

1 Answers1

0

You mean $x^2\equiv71\pmod{77}$ etc.

If $a=15$ and $b=29$, then indeed $a\equiv b\pmod 7$ and $a\equiv -b\pmod{11}$ so you can take $p=7$ and $q=11$.

To factor $n$ what you do is find $a$, $b$ with $a^2\equiv b^2\pmod n$ but $a\not\equiv \pm b\pmod n$ and compute the greatest common divisor of $a-b$ and $n$. That will be a proper factor of $n$. Here $\gcd(a-b,n)=\gcd(-14,77)=7$.

Angina Seng
  • 158,341
  • Thanks for the answer by the way do they always have to be in the form like ( a, -a and b , -b) or can they be in the form of ( a,b,c,d) – Cem Aytekin Oct 13 '17 at 14:52
  • @CemAytekin Well, if $n$ is a product of two distinct odd primes, and if $c$ is coprime to $n$ and has a square root modulo $n$, then it has four square roots modulo $n$, falling into two pairs $\pm a$ and $\pm b$ modulo $n$. – Angina Seng Oct 13 '17 at 15:03
  • If $x^2=b \mod c$, then $(c-x)^2=b \mod c$ – Steven Alexis Gregory Oct 13 '17 at 15:13