A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

h0pe

  • one year ago

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

  • This Question is Closed
  1. UsukiDoll
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Then what should I try?

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    start by factoring 527

  4. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    17 and 31

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  7. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I have to find the inverse of 37, right?

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  9. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    yes

  10. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    It's 13

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  12. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Looks good!

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  15. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thank you!

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  17. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    That was RSA?

  18. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  19. h0pe
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  20. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.