# Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$.

(a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$.

(b) Given the factorization of $N$ computed above, use the CRT to decrypt the following ciphertext $c = E_{pk}(m) = 3$.

For part a) I am not sure which property of modular arithmetic can be used? I know $187$ has a multiplicative inverse $187$. I also know the Euler function. But I think I am missing how to calculate $\phi$ from this information.

• If you know that $x^2 = 1 \pmod N$ that can be rewritten as $x^2 -1 = 0 \pmod N$, on the left hand side of the equation you have a well know identity... Try to rewrite it differently. And then remember what $\equiv 0 \pmod N$ means ... Dec 6 '15 at 10:45
• additional hint: when you have divisor $u$ of some positive multiple of $N$, $\gcd(u,N)$ will often be a factor of $N$.
– fgrieu
Dec 6 '15 at 16:21

For part a) of your question: In this case 2 would be the order of 187 in the multiplicative group modulo 1457. This means you could retrieve the factors of 1457 using the formula gcd($187^{2/2}-1$, 1457) and gcd($187^{2/2}+1$, 1457).

Having the factors of 1457, you can compute $\phi$ with ease.

@fgrieu: The calculation is taken from the non-quantum part of Shor's Algorithm. Basically it's the same as what you mentioned in the comments of the question. Thanks for pointing out my mistake. I mixed up some numbers in my gcd calculation...

• $\gcd(187^2-1,1457)=1457$, and $\gcd(187^2+1,1457)=1$.
– fgrieu
Dec 8 '15 at 16:32
• My mistake. My answer followed the non-quantum part of Shor's Algorithm for factoring integers. It should be $187^{2/2}$. Yet it still does not work as gcd(186, 1457) is obviously 1. I will delete my answer as it is misleading in this case. Dec 8 '15 at 16:59
• Glad that you got it fixed. The origin of the to the $2/2$ th power evades me, but we can do without it :-)
– fgrieu
Dec 11 '15 at 14:32
• $x^r = 1 \bmod n \rightarrow x^r - 1 = 0 \bmod n \rightarrow (x^{r/2} - 1)(x^{r/2} + 1) = 0 \bmod n$ Dec 11 '15 at 15:38