Since x is a number in the set {0, 1, . . . , 2^ t}, we can write x in binary as: x = b0 · 2 ^0 + b1 · 2^ 1 + b2 · 2 ^2

[answerhappygod]

Since x is a number in the set {0, 1, . . . , 2^ t}, we can
write x in binary as: x = b0 · 2 ^0 + b1 · 2^ 1 + b2 · 2 ^2 + · · ·
+ bt · 2^ t , (1) where bi are bits. If b0 = 0, then x = b1 · 2 ^1
+ b2 · 2 ^2 + · · · + bt · 2 ^t = 2y, for some integer y, i.e., x
is an even number. On the other hand, if b0 = 1, then x = 1 + b1 ·
2 ^1 + b2 · 2 ^2 + · · · + bt · 2 ^t = 2y + 1, for some integer y,
i.e., x is an odd number. Let m = 2^(t −1) .
(c) Show that if b0 = 0, then (g^ x )^ m ≡ 1 (mod p).(to do)
(d) Show that if b0 = 1, then (g ^x ) ^m ≡ p − 1 (mod p).(to
do)