## 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 ?

1. freckles

can we use fermat's little theorem for the first question

2. ganeshie8

Looks $$k$$ is public key here which he needs to choose, not much to solve as such it seems..

3. freckles

also question b seems weird that question seems equivalent to evaluating 53 mod 91

4. freckles

you know since b is equivalent to a mod 91

5. freckles

a mod 91=b mod 91=53 mod 91

6. ganeshie8

suppose we choose $$k=5$$, then he needs to generate the cipher text by rising $$53$$ to the power $$5$$

7. ganeshie8

a = ciphertext b = plaintext

8. anonymous

you are suppose to determin k which I got to 73 in somehow...

9. ganeshie8

I am beginning to feel that question has something missing..

10. anonymous

Cant a be all the relatively primes to under 91? phi(91)?

11. anonymous

and the thing is I know b≡a mod 91 and need to show that b^k≡a mod 91

12. anonymous

I mean proove it right?

13. ganeshie8

could you take a screenshot of actual question and post if psble

14. anonymous

its in swedish, and thats all there is...

15. anonymous

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 ?

16. thomas5267

$\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}$$?

17. anonymous

yes thomas thats what I did, but is that proof enough?

18. thomas5267

I guess so. If $$\gcd(b,91)=1$$ then I think the proof is good enough.

19. anonymous

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?

20. anonymous

@ganeshie8 , @freckles

21. anonymous

@thomas5267 and how do we know that GCD(b,91)=1?

22. thomas5267

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

23. thomas5267

@ganeshie8 is the number theory guy on this website so I will defer this to him. I need to cook an instant noodle now.

24. thomas5267

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.

25. thomas5267

Actually $$\gcd(a,91)=1$$ has nothing to do with b and a having the same remainder when divided by 91.

26. anonymous

So Thomas, how can we determine k from that? @thomas5267

27. 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}$

28. thomas5267

Now excuse me, I have to go make myself a instant noodle.