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 ?

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

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 ?

Mathematics
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

can we use fermat's little theorem for the first question
Looks \(k\) is public key here which he needs to choose, not much to solve as such it seems..
also question b seems weird that question seems equivalent to evaluating 53 mod 91

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

you know since b is equivalent to a mod 91
a mod 91=b mod 91=53 mod 91
suppose we choose \(k=5\), then he needs to generate the cipher text by rising \(53\) to the power \(5\)
a = ciphertext b = plaintext
you are suppose to determin k which I got to 73 in somehow...
I am beginning to feel that question has something missing..
Cant a be all the relatively primes to under 91? phi(91)?
and the thing is I know b≡a mod 91 and need to show that b^k≡a mod 91
I mean proove it right?
could you take a screenshot of actual question and post if psble
its in swedish, and thats all there is...
or 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 ?
\[ \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}\)?
yes thomas thats what I did, but is that proof enough?
I guess so. If \(\gcd(b,91)=1\) then I think the proof is good enough.
but if we know b≡ a(mod91) and we want to show b^k≡ a(mod91) we can write it as\[b*b ^{k-1}≡ a*1(\mod 91)\] right? and we want to show that \[b ^{k-1}≡ 1(\mod91)\] how we proove that? how does the actually proof looks like?
@thomas5267 and how do we know that GCD(b,91)=1?
Fermat'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
@ganeshie8 is the number theory guy on this website so I will defer this to him. I need to cook an instant noodle now.
I 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.
Actually \(\gcd(a,91)=1\) has nothing to do with b and a having the same remainder when divided by 91.
So Thomas, how can we determine k from that? @thomas5267
Euler 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{Wolfram|Alpha-ed the answer.}\\ b^{72} \equiv 1 \pmod{91}\\ b^{73}\equiv b \equiv a \pmod{91}\quad\text{since }b\equiv a \pmod{91} \]
Now excuse me, I have to go make myself a instant noodle.

Not the answer you are looking for?

Search for more explanations.

Ask your own question