Knowing that $n= 3598057$ is a product of two different prime numbers and that 20779 is a square root of $1$ mod $n$, find prime factorization of $n$.

What I have done so far:

$n = p \cdot q$

$x^2 \equiv 1\pmod{n}$

$x^2 -1 \equiv 0\pmod{n}$

$(x-1)(x+1) \equiv 0\pmod{n}$

$x-1 = 20779 \lor x + 1=20779$

I have also noticed that:

$(x-1)(x+1) \equiv 0\pmod{p \cdot q}$

$(x-1)(x+1) \equiv 0\pmod{p} \land (x-1)(x+1) \equiv 0\pmod{q}$

But I have no idea what to do next. Any hints?

  • 1
    $\begingroup$ Tiny hint:you know that $(x-1)(x+1)\equiv 0\pmod p$; when can a product of two factors be equal to $0$ modulo a prime? $\endgroup$ – Steven Stadnicki May 17 '13 at 0:02
  • $\begingroup$ Your step $$(x-1)(x+1)\equiv 0\pmod{n}\implies x-1=20779\text{ or }x+1=20779$$ is incorrect; there can be more than two square roots of $1$ when the modulus $n$ is not prime (as we know it is not in this setting). $\endgroup$ – Zev Chonoles May 17 '13 at 0:03

From $(x-1)(x+1)\equiv 0 \pmod n$ you cannot conclude that $x-1 = 20779 \lor x + 1=20779$ when $n$ is not prime. You can conclude that $x-1 \equiv 0 \pmod p$ and $x+1 \equiv 0 \pmod q$ (or the other way-we could swap $p,q$) when you know that $n$ has only two prime factors unless $pq$ divides one of $x+1, x-1$. So factor $20778$ and $20780$ looking for factors that will multiply to make $3598057$. The other factors are small enough to find by hand.

  • 2
    $\begingroup$ Don't try to factor $20778$ or $20780$. Find the gcds instead; if $p | n$, $p | 20778$ or $p | 20780$. So, $p | (20778, n)$ or $p | (20780, n)$. Use Euclid's algorithm to find the gcds. $\endgroup$ – Eric Jablow May 17 '13 at 1:02
  • $\begingroup$ @Eric: a better approach. That will work with large multiples $\endgroup$ – Ross Millikan May 17 '13 at 1:22

From the condition (x-1)(x+1)=0 mod n

you can conclude (a) n divides (x-1), or (b) n divides (x+1), or (c) some factor of n divides (x-1) and some other factor of n divides (x+1)

Since (a) and (b) are ruled out (x is not plus or minus 1) we get two factors as f1 = gcd(x-1,n) f2 = gcd(x+1,n)

If n is not known to be a product of two primes, then one will try to factor f1 and f2 or prove their primality.


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.