A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
RSA encryption
For integers a and b, this is true b ≡ a (mod 91 ) and GCD (a, 91 ) = 1.
a)Determine a positive integer k> 1 such that b ^ k ≡ a (mod 91 ) .
b)What is a mod 91 for b = 53 ?
anonymous
 one year ago
RSA encryption For integers a and b, this is true b ≡ a (mod 91 ) and GCD (a, 91 ) = 1. a)Determine a positive integer k> 1 such that b ^ k ≡ a (mod 91 ) . b)What is a mod 91 for b = 53 ?

This Question is Closed

freckles
 one year ago
Best ResponseYou've already chosen the best response.0can we use fermat's little theorem for the first question

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0Looks \(k\) is public key here which he needs to choose, not much to solve as such it seems..

freckles
 one year ago
Best ResponseYou've already chosen the best response.0also question b seems weird that question seems equivalent to evaluating 53 mod 91

freckles
 one year ago
Best ResponseYou've already chosen the best response.0you know since b is equivalent to a mod 91

freckles
 one year ago
Best ResponseYou've already chosen the best response.0a mod 91=b mod 91=53 mod 91

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0suppose we choose \(k=5\), then he needs to generate the cipher text by rising \(53\) to the power \(5\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0a = ciphertext b = plaintext

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0you are suppose to determin k which I got to 73 in somehow...

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0I am beginning to feel that question has something missing..

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Cant a be all the relatively primes to under 91? phi(91)?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and the thing is I know b≡a mod 91 and need to show that b^k≡a mod 91

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I mean proove it right?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0could you take a screenshot of actual question and post if psble

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0its in swedish, and thats all there is...

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0or maybe For integers a and b, applies to b ≡ a (mod 91 ) and gcd (a, 91 ) = 1. Determine a positive integer k> 1 such that b ^ k ≡ a (mod 91 ) . What is a mod 91 for b = 53 ?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0\[ \left(\gcd(a,91)=1\land a\equiv b\pmod{91}\right)\implies\gcd(b,91)=1? \] Since \(\phi(91)=72\), \(b^{72}=1\pmod{91}\) and \(b\equiv a \pmod {91}\), \(b^{73}\equiv b\equiv a\pmod{91}\)?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0yes thomas thats what I did, but is that proof enough?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0I guess so. If \(\gcd(b,91)=1\) then I think the proof is good enough.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0but if we know b≡ a(mod91) and we want to show b^k≡ a(mod91) we can write it as\[b*b ^{k1}≡ a*1(\mod 91)\] right? and we want to show that \[b ^{k1}≡ 1(\mod91)\] how we proove that? how does the actually proof looks like?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@ganeshie8 , @freckles

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@thomas5267 and how do we know that GCD(b,91)=1?

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0Fermat's little theorem does not work here since 91 = 13 x 7. We have to use the Euler theorem. No idea how to prove it but the prove is in wikipedia. https://en.wikipedia.org/wiki/Euler's_theorem

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0@ganeshie8 is the number theory guy on this website so I will defer this to him. I need to cook an instant noodle now.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0I guess we could do a Euclidean algorithm on \(\gcd(b,91)\)? \[ b=91q_{b0}+r_{b0}\\ \text{But }\gcd(a,91)=1\text{ and }{a\equiv b\pmod{91}}\\ \text{So }b=a+91n\text{ for some }n\in\mathbb{N}\\ \text{So }b\div 91\text{ must have the same remainder as }a\div91\\ r_{a0}=r_{b0}=r_0\\ \text{Consider the calculation of }\gcd(a,91)\text{ and }\gcd(b,91)\\ \begin{align*} a&=91q_{a0}+r_{0}&b&=91q_{b0}+r_{0}\\ 91&=q_{a1}r_0+r_{a1}&91&=q_{b1}r_0+r_{b1} \end{align*} \] We can see that in the second step of calculating \(\gcd(a,91)\) and \(\gcd(b,91)\) are the same. Therefore, so should the subsequent steps and the final result.

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0Actually \(\gcd(a,91)=1\) has nothing to do with b and a having the same remainder when divided by 91.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0So Thomas, how can we determine k from that? @thomas5267

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0Euler theorem states that: \[ a^{\varphi (n)} \equiv 1 \pmod{n} \] if \(\gcd(a,n)=1\) for a function \(\varphi\) named Euler's toitent function which I don't understand. Since \(\gcd(b,91)=1\), \[ b^{\varphi (91)} \equiv 1 \pmod{91}\\ \varphi(91)=72\quad\text{WolframAlphaed the answer.}\\ b^{72} \equiv 1 \pmod{91}\\ b^{73}\equiv b \equiv a \pmod{91}\quad\text{since }b\equiv a \pmod{91} \]

thomas5267
 one year ago
Best ResponseYou've already chosen the best response.0Now excuse me, I have to go make myself a instant noodle.
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.