Fast Modular Exponentiation

This project is a C# program for calculating fast modular exponentiation, i.e. the result of raising a base number to an exponent and then taking the modulus, as in $a^b \mod n$. The algorithm is efficient and widely used in cryptographic applications.

Technologies

Features

• User Input: Prompts the user to enter the base, exponent, and modulus.
• Efficient Algorithm: Implements exponentiation by squaring.
• Detailed Output: Displays intermediate steps and final result.
• Unit Tests: Includes comprehensive unit tests to ensure correctness.

Formula

The formula for modular exponentiation is:

$a^b \mod n$

where:

• a is the base number,
• b is the exponent,
• n is the modulus.

How to Run

1. Clone the repository.
2. Open a terminal or command prompt.
3. Navigate to the project directory (FastModularExponentiation)
4. Compile the program using the following command

dotnet build

5. Run the program using the following command:

dotnet run

Example Usage

Enter a: 2
Enter exponent: 10
Enter modulo: 1000

 i |        x |        a | t_i
 0 |        1 |        2 | 0
 1 |        1 |        4 | 1
 2 |        4 |       16 | 0
 3 |        4 |      256 | 1
 4 |       24 |      536 | -

Result: 24

Unit tests

Unit tests are included to validate the correctness of the algorithm. These tests cover various scenarios to ensure accurate results for different inputs. Follow these steps to execute the unit tests:

1. Open a terminal or command prompt.
2. Navigate to the directory containing the solution file (FastModularExponentiation).
3. Run the command dotnet test.

License

This project is licensed under the The MIT License. See the LICENSE file for more details.