Question

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

Answer 1

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

Answer 2

Then what should I try?

Answer 3

start by factoring 527

Answer 4

17 and 31

Answer 5

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

Answer 6

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

Answer 7

I have to find the inverse of 37, right?

Answer 8

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

Answer 9

yes

Answer 10

It's 13

Answer 11

\[\large x \equiv 3^{13} \pmod{527}\]

Answer 12

\[x\equiv1594323(\mod527)\] which is \[x\equiv148 (\mod527)\]?

Answer 13

Looks good!

Answer 14

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

Answer 15

thank you!

Answer 16

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

Answer 17

That was RSA?

Answer 18

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

Answer 19

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