(a) Find the last two decimal digits of 139139100 (b) Find the multiplicative inverse of 15...

Transcribed Image Text:

(a) Find the last two decimal digits of 139139100 (b) Find the multiplicative inverse of 15 modulo 56 using the extended Euclidean algorithm. (c) Let p be a large prime and let g be a generator of the group Zp. 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(p-1)/2 mod p. (a) Find the last two decimal digits of 139139100 (b) Find the multiplicative inverse of 15 modulo 56 using the extended Euclidean algorithm. (c) Let p be a large prime and let g be a generator of the group Zp. 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(p-1)/2 mod p.