In cryptography, it is important to be able to find bn mod m efficiently, where b, n, and m are large integers. It is impractical to first compute bn and then find its remainder when divided by m because bn will be a huge number. Instead, we can use an algorithm that employs the binary expansion of the exponent n. In this assignment, you will implement the following Algorithm 5 using C/C++. The pseudocode of the Algorithm 5 is given below. Write a program using C/C++ to implement Algorithm 5. For this purpose, define a function called modExp() which calculates modular exponentiation and returns the result. int modExp(int b, int e, int m); //Prototype for modExp Write a test code to check the functionality of function modExp(). The user must provide three inputs to the program (3, 644 and 645) as in the following form: 3644 mod 645 = 36 Hint. The second argument in modExp() function must be converted to binary form before the function call. For this aim, you may define the subroutine decToBin() which converts decimal exponent into binary formed decimal (i.e., If the exponent is 7, you may utilize decimal 111 instead) int decToBin(int num); Assignment Rules: Be sure that your outputs are the same as the sample screens. Pay attention to programming conventions such as indentation, comment lines etc. which may affect your grades. Always try to do yourself and ask instructors when you have questions. Put your projects in a folder with your name and upload using CATS system in compressed form; (e.g. stdNumber_NameSurname.rar which includes your project with source code and sample screenshots) Cheating and similarity in assignments will not be tolerated. This assignment is worth 7% of the overall course grade
CSE3013 - DISCRETE STRUCTURES
Due Date: 06.01.2021, 23:55 In cryptography, it is important to be able to find bn mod m efficiently, where b, n, and m are large integers. It is impractical to first compute bn and then find its remainder when divided by m because b will be a huge number. Instead, we can use an algorithm that employs the binary expansion of the exponent n. In this assignment, you will implement the following Algorithm 5 using C/C++. The pseudocode of the Algorithm 5 is given below. ALGORITHM 5 Modular Exponentiation. procedure modular exponentiation(b: integer, n = (ak-12k-2 ...ajao)2, m: positive integers) X:= 1 power := b mod m for i := 0 to k 1 if a; = 1 then x := (x power) mod m power := (power power) mod m return x{x equals bn mod m} power :=b mod m for i:= 0 to k - 1 if a; = 1 then x := (x power) mod m power := (power power) mod m return x{x equals b" mod m} Write a program using C/C++ to implement Algorithm 5. For this purpose, define a function called modExp () which calculates modular exponentiation and returns the result. int modExp (int b, int e, int m); //Prototype for modExp Write a test code to check the functionality of function modExp (). The user must provide three inputs to the program (3, 644 and 645) as in the following form: 3644 mod 645 = 36 Hint. The second argument in modExp() function must be converted to binary form before the function call. For this aim, you may define the subroutine decToBin() which converts decimal exponent into binary formed decimal (i.e., If the exponent is 7, you may utilize decimal 111 instead) int decToBin (int num); Assignment Rules: Be sure that your outputs are the same as the sample screens. Pay attention to programming conventions such as indentation, comment lines etc. which may affect your grades. Always try to do yourself and ask instructors when you have questions. Put your projects in a folder with your name and upload using CATS system in compressed form; (e.g. stdNumber_NameSurname.rar which includes your project with source code and sample screenshots) Cheating and similarity in assignments will not be tolerated. This assignment is worth 7% of the overall course grade. Sample Outputs Screens: MODULAR EXPONENTIATION CALCULATOR (a^b mod m solver) Enter Base (a): 3 Enter Exponent (b): 644 Enter Modulus (m): 645 644 is equivalent to (1010000100) as binary number... Sample Outputs Screens: MODULAR EXPONENTIATION CALCULATOR (a^b mod m solver) Enter Base (a): 3 Enter Exponent (b): 644 Enter Modulus (m): 645 644 is equivalent to (1010000100) as binary number... Because bo is 0, we have x = 1 and power = 3^ 2 mod 645 9 Because bi is 0, we have x = 1 and power = 9 ^ 2 mod 645 = 81 Because b2 is 1, we have x = (1 * 81) and power = 81 ^ 2 mod 645 = 111 Because b3 is 0, we have x = 81 and power = 111 * 2 mod 645 = 66 Because b4 is 0, we have x = 81 and power = 66 ^ 2 mod 645 = 486 Because b5 is 0, we have x = 81 and power = 486 ^ 2 mod 645 = 126 Because b6 is 0, we have x = 81 and power = 126 ^ 2 mod 645 = 396 Because b7 is 1, we have x = (81 * 396) and power = 396 ^ 2 mod 645 = 81 Because b8 is 0, we have x = 471 and power = 81 ^ 2 mod 645 = 111 Because b9 is 1, we have x = (471 * 111) mod 645 ==> Modular Exponentiation of 134644) mod (645) = 36 MODULAR EXPONENTIATION CALCULATOR (a^b mod m solver) Enter Base (a): 3 Enter Exponent (b): 128 Enter Modulus (m): 7 128 is equivalent to (10000000) as binary number... = Because bo is 0, we have x = 1 and power = 3 ^ 2 mod 7 = 2 Because bi is 0, we have x = 1 and power 2 A 2 mod 7 = 4 Because b2 is 0, we have x = 1 and power 4. ^ 2 mod 7 = 2 Because b3 is 0, we have x = 1 and power 2 ^ 2 mod = 4 Because b4 is 0, we have x = 1 and power 4 A 2 mod = 2 Because b5 is 0, we have x = 1 and power = 2^ 2 mod 7 = 4 Because b6 is 0, we have x = 1 and power = 4 2 mod 7 = 2 Because b7 is 1, we have x = (1 * 2) 7 ==> mod Modular Exponentiation of (3^128) mod (7) = 2 MODULAR EXPONENTIATION CALCULATOR (a^b mod m solver) MODULAR EXPONENTIATION CALCULATOR (a^b mod m solver) Enter Base (a): 27 Enter Exponent (b): 17 Enter Modulus (m): 15 17 is equivalent to (10001) as binary number... Because bo is 1, we have x = (1 * 12) and power = 12 ^ 2 mod 15 = 9 Because bi is 0, we have x = 12 and power = 9 ^ 2 mod 15 = 6 Because b2 is 0, we have x = 12 and power = 6 ^ 2 mod 15 = 6 Because b3 is 0, we have x = 12 and power = 6 2 mod 15 = 6 Because b4 is 1, we have x = (12 * 6) mod 15 ==> Modular Exponentiation of (27^17) mod (15) = 12
