: Let G be a group and denote its operation *. For any a G,...

   

Transcribed Image Text:

: Let G be a group and denote its operation *. For any a € G, let's define a² to be a * a, the group operation applied to a and itself. Define a³ to be the product a² * a, a¹ = a³ * a, and so on. In this way, we can define exponentiation in an arbitrary group: ak =a*a* a* ... * a, where there are k a's on the right hand side of the equality. Hence, we can ask the question, for some elements a, b e G, to find a number k such that a = b. (Note that k is a natural number k, not an element of G.) This is called the discrete logarithm problem, again because of the analogy to logarithms in the real numbers: log, a = k. = While computing b ak from a and k is straightforward, finding k from a and b in general is believed to be computationally intractable and is the basis for many cryptosystems. For this question, we'll compute discrete logs over some small groups to get a feel for this important problem. Problem: Let G be the group of integers modulo 17 under multiplication, denoted *. So the elements are {0, 1, 2,..., 16) and a*b = axb mod 17, where x is standard multiplication over the integers. For example, 15*2 = 13 because which is 15 x 2 = 30, and 30 mod 17 is 13. a) Compute 137. (Note that it suffices to take the mod at the end only.) b) Find k such that 12k=5. That is, find log12 5. Hint: You can compute 12k for different (ex. increasing) values of k until you find the one that works.) c) Find k such that 6 = 15. That is, compute log6 15. d) I was able to create parts b) and c) so that I knew the answers without having to do the brute force search over the possible values of k. Explain how I did that. : Let G be a group and denote its operation *. For any a € G, let's define a² to be a * a, the group operation applied to a and itself. Define a³ to be the product a² * a, a¹ = a³ * a, and so on. In this way, we can define exponentiation in an arbitrary group: ak =a*a* a* ... * a, where there are k a's on the right hand side of the equality. Hence, we can ask the question, for some elements a, b e G, to find a number k such that a = b. (Note that k is a natural number k, not an element of G.) This is called the discrete logarithm problem, again because of the analogy to logarithms in the real numbers: log, a = k. = While computing b ak from a and k is straightforward, finding k from a and b in general is believed to be computationally intractable and is the basis for many cryptosystems. For this question, we'll compute discrete logs over some small groups to get a feel for this important problem. Problem: Let G be the group of integers modulo 17 under multiplication, denoted *. So the elements are {0, 1, 2,..., 16) and a*b = axb mod 17, where x is standard multiplication over the integers. For example, 15*2 = 13 because which is 15 x 2 = 30, and 30 mod 17 is 13. a) Compute 137. (Note that it suffices to take the mod at the end only.) b) Find k such that 12k=5. That is, find log12 5. Hint: You can compute 12k for different (ex. increasing) values of k until you find the one that works.) c) Find k such that 6 = 15. That is, compute log6 15. d) I was able to create parts b) and c) so that I knew the answers without having to do the brute force search over the possible values of k. Explain how I did that.

Answer rating: 100% (QA)

SOLUTION a To compute 137 in the group of integers modulo 17 under multiplication we can perform the ... View the full answer