Find an integer x such that 0

Question

Find an integer x such that 0 <= x < 527 and x^37 ≡3 (mod 527).

usukidoll · Answer

so we need a number x such that the remainder will be 3 in mod 527. Trial and error will take too long because the exponent is just too big here

h0pe · Answer

Then what should I try?

ganeshie8 · Answer

start by factoring 527

h0pe · Answer

17 and 31

ganeshie8 · Answer

that means $\phi(527) = (17-1)(31-1) = 480$

ganeshie8 · Answer

Now solve below equation
$$37y \equiv 1 \pmod{480}$$

h0pe · Answer

I have to find the inverse of 37, right?

ganeshie8 · Answer

that is, find the inverse of exponent "37" in mod 480

ganeshie8 · Answer

yes

h0pe · Answer

It's 13

ganeshie8 · Answer

$$\large x \equiv  3^{13} \pmod{527}$$

h0pe · Answer

$$x\equiv1594323(\mod527)$$ which is $$x\equiv148 (\mod527)$$?

ganeshie8 · Answer

Looks good!

ganeshie8 · Answer

since they want x to be between 0 and 527, just pick x = 148

h0pe · Answer

thank you!

ganeshie8 · Answer

as you can see breaking RSA is trivial when you're able to factor the modulus

h0pe · Answer

That was RSA?

ganeshie8 · Answer

RSA is the name of an encryption system, I thought you're working on encryption algorithms... I went through your past questions...

h0pe · Answer

Oh, so that's what it's called..