A program that reads three numbers and returns the value
a^b mod n.
There is two parts to this
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).
Devise a program that reads in three numbers, a, b , and n. It returns the value a^b mod n. (Recall that the modulo function gives the remainder of a ^b when divided by n). The program needs to multiplay a by itself b times and perform modulo arithmetic after each multiplication. You may assume that a and n are 16-bit values. Note that when a and b are large, the size of a^b may exceed 32-bit. Since n is a 16-bit value, the value of a^b mod n will be within 16-bit.
The mathematics behind: Note that
(c*d)mod n=[(c mod n) *(d mod n)] mod n. To compute a^b mod n, we can use the formula to first compute a^b-1 mod n, and then multiply the result with a, and then perform the modulo n operations to get the answer. A simple for loop should be enough.
Test the program with the following inputs:
1. A=1000, B=99999, N=1001
2. A=2, B=10000, N=10001
3. A= -10, B=19, N=37
Can you give the asymptotic of this procedure in terms of b?
Example: The bit pattern of the # b=41 is 101001. To compute, we write it as [(a mod n)*(a^8 mod n)*(a^32 mod n)] mod n ( using the formula discussed above). Notice that the ones in the binary representation of 41 occurs in the 1-bit, the 8-bit and the 32-bit. It remains to find a^8 mod n, and a^32 mod n. This can be accomplished by repeated squaring. It is easy to find a mod n. Now a^2 mod n = [(a mod n) *(a mod n)]mod n
a^4 mod n = [(a^2 mod n)*(a^2 mod n)]mod n
a^8 mod n = [(a^4 mod n)*(a^4 mod n)]mod n
a^16 mod n = [(a^8 mod n)*(a^8 mod n)]mod n
a^32 mod n = [(a^16 mod n)*(a^16 mod n)]mod n
only seven multipliacations are needed with this approach, compared to 31 in the procedure in part A.
Implement this strategy, and perform the same testing as in partA and Give asymptotic of this procedure in terms of b.
Mircosoft Visual C++ 6.0