## h0pe one year ago Find an integer x such that 0 <= x < 527 and x^37 ≡3 (mod 527).

1. UsukiDoll

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

2. h0pe

Then what should I try?

3. ganeshie8

start by factoring 527

4. h0pe

17 and 31

5. ganeshie8

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

6. ganeshie8

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

7. h0pe

I have to find the inverse of 37, right?

8. ganeshie8

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

9. ganeshie8

yes

10. h0pe

It's 13

11. ganeshie8

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

12. h0pe

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

13. ganeshie8

Looks good!

14. ganeshie8

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

15. h0pe

thank you!

16. ganeshie8

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

17. h0pe

That was RSA?

18. ganeshie8

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

19. h0pe

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