4 ms·

Does anyone have more details on slide 9 "Proof of time: Modular roots"? > In group of order 2^k, square k-1 times to find a square root I don't want to say a

by ecesena 10y ago

Does anyone have more details on slide 9 "Proof of time: Modular roots"? > In group of order 2^k, square k-1 times to find a square root I don't want to say anything stupid, but I don't know if this is trivially true, for instance in [the multiplicative group of] a field of char 2, square is linear and so it's square root. Edit: to clarify, in a field of char 2 the multiplicative group has order 2^q-1, which can't be 2^k. I'm just giving this as an example of a group where square root is fast.

gizmo686 10y ago
I also fine this confusing. From the video, it sounds like the claim is that sqrt(x) = x^(2^(k-1)), which you verify by checking that x=x^(2^k) [0]. However, since the order of the group is 2^k, it is an elementary result of group theory that x^(2^k)=1 [1] [0] That is, you square the claimed root which should be x^(2^(k-1)). EDIT: watching the video some more for clues, he does mention that he uses a particular kind of group, so the claimed property does not need to hold for any group of order 2^k. However, as I argue above, I still don't see how it is possible for any group of order 2^k. [1] This is a direct result of Lagranges theorem. https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)#Applications https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_th...
tromp 10y ago
getting the square root of x from k-1 squarings means (x^(2^(k-1))) ^ 2 = x, or x^(2^k) = x. so x has multiplicative order (2^k)-1, which is the order of GF(2^k) under multiplication.
- gizmo686 10y ago
  But the group has order 2^k. Since the powers of x (for any group element x) form a group themselves, Lagrange's theorme tells us that the order of x must divide 2^k. This should mean that it is impossible for x to have order (2^k)-1. If fact, it means that x^(2^k)=1. Further, if you are given the value y=x^2, then no power of y will give you x.
  - tromp 10y ago
    The finite field GF(2^k) has order (number of elements) 2^k, but its multiplicative group has the (2^k)-1 nonzero elements, and thus order (2^k)-1, which squares [pun intended] with the fact that x^(2^k-1) = 1.
    - deleted 10y ago
      [deleted]

by ecesena 10y ago

gizmo686 10y ago

I also fine this confusing. From the video, it sounds like the claim is that sqrt(x) = x^(2^(k-1)), which you verify by checking that x=x^(2^k) [0]. However, since the order of the group is 2^k, it is an elementary result of group theory that x^(2^k)=1 [1] [0] That is, you square the claimed root which should be x^(2^(k-1)). EDIT: watching the video some more for clues, he does mention that he uses a particular kind of group, so the claimed property does not need to hold for any group of order 2^k. However, as I argue above, I still don't see how it is possible for any group of order 2^k. [1] This is a direct result of Lagranges theorem. https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)#Applications https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_th...

tromp 10y ago

getting the square root of x from k-1 squarings means (x^(2^(k-1))) ^ 2 = x, or x^(2^k) = x. so x has multiplicative order (2^k)-1, which is the order of GF(2^k) under multiplication.

gizmo686 10y ago
But the group has order 2^k. Since the powers of x (for any group element x) form a group themselves, Lagrange's theorme tells us that the order of x must divide 2^k. This should mean that it is impossible for x to have order (2^k)-1. If fact, it means that x^(2^k)=1. Further, if you are given the value y=x^2, then no power of y will give you x.
- tromp 10y ago
  The finite field GF(2^k) has order (number of elements) 2^k, but its multiplicative group has the (2^k)-1 nonzero elements, and thus order (2^k)-1, which squares [pun intended] with the fact that x^(2^k-1) = 1.
  - deleted 10y ago
    [deleted]