Final answer:
a) The last two decimal digits of (139^139^100) are 39. b) The multiplicative inverse of 15 modulo 56 is 23. c) By computing r^((p-1)/2) modulo p in the equation r=g^x mod p, we can find the least significant bit of the binary representation of x.
Step-by-step explanation:
(a) Find the last two decimal digits of (139139100).
To find the last two decimal digits of a number, we need to use the concept of modular arithmetic. We can find the remainder when the number is divided by 100. Let's start by simplifying the exponent.
139139100 ≡ 1391390 mod 100
Since any number raised to the power of 0 is 1, the expression becomes:
1391 mod 100 ≡ 139 mod 100 ≡ 39
Therefore, the last two decimal digits of (139139100) are 39.
(b) Find the multiplicative inverse of 15 modulo 56 using the extended Euclidean algorithm.
The extended Euclidean algorithm is used to find the multiplicative inverse of a number modulo another number. For this problem, we need to find the value of x in the equation 15x ≡ 1 (mod 56). By using the extended Euclidean algorithm, we can find that the multiplicative inverse of 15 modulo 56 is 23.
(c) Let p be a large prime and let g be a generator of the group Zₚ*. Let r=gˣ mod p for integer x. Show that it is possible to find the least significant bit of the binary representation of x by computing r⁽ᵖ−¹⁾/² mod p.
Let's assume that p = 2^k + 1 for some integer k. By Fermat's Little Theorem, we know that g^(p-1) ≡ 1 (mod p). Let's consider r^((p-1)/2).
Case 1: r^((p-1)/2) ≡ 1 (mod p)
In this case, the least significant bit is 0.
Case 2: r^((p-1)/2) ≡ -1 (mod p)
In this case, the least significant bit is 1.
By computing r^((p-1)/2) modulo p, we can determine the least significant bit of the binary representation of x.