Snip2Code is shutting down.
It has been quite a ride, since 2013 when we launched our first prototype: thanks to the effort of you guys we collected more than 3 million snippets!
We are very proud to help all our users to be more efficient in their jobs, and to be the central point to share programming knowledge for everyone.
Our basic service is free, so we always survived on our own resources to give you Snip2Code.
Unfortunately, we are no more in the financial position to sustain this effort, and therefore we are announcing here our permanent shut down,
which will take place on August 1st, 2020.
Please save your private snippets using our backup function in the settings, here.
IF YOU WANT TO SAVE SNIP2CODE, PLEASE CONSIDER DOING A DONATION!
This will allow us to pay for the servers and the infrastructure. If you want to donate, Contact Us!
8
6
4,789
7
Top 1% !
Famous
Nice
Easy-to-find
Specified
MultiPlatform
Popularity: 1907th place

### Published on:

 Language objectivec Language Text License MIT_X11

# `Efficient ModExp for Cryptographic purpose in C`

`How to implement an efficient routine to calculate the Modular exponentiation as stated in http://en.wikipedia.org/wiki/Modular_exponentiation.`
post this code
Copy Embed Code
``` <iframe id="embedFrame" style="width:600px; height:300px;" src="https://www.snip2code.com/Embed/81136/Efficient-ModExp-for-Cryptographic-purpo?startLine=0"></iframe> ```
Click on the embed code to copy it into your clipboard Width Height
Leave empty to retrieve all the content Start End
Using modular multiplication rules: i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C We can use this to calculate 7^256 mod 13 quickly 7^1 mod 13 = 7 7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13 We can substitute our previous result for 7^1 mod 13 into this equation. 7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10 7^2 mod 13 = 10 7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13 We can substitute our previous result for 7^2 mod 13 into this equation. 7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9 7^4 mod 13 = 9 7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13 We can substitute our previous result for 7^4 mod 13 into this equation. 7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3 7^8 mod 13 = 3 We continue in this manner, substituting previous results into our equations. ...after 5 iterations we hit: 7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13 7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9 7^256 mod 13 = 9 This has given us a method to calculate A^B mod C quickly provided that B is a power of 2. However, we also need a method for fast modular exponentiation when B is not a power of Let say.. How can we calculate A^B mod C quickly for any B ? => Step 1: Divide B into powers of 2 by writing it in binary Start at the rightmost digit, let k=0 and for each digit: If the digit is 1, we need a part for 2^k, otherwise we do not Add 1 to k, and move left to the next digit => Step 2: Calculate mod C of the powers of two ≤ B 5^1 mod 19 = 5 5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19 5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19 5^2 mod 19 = 6 5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19 5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19 5^4 mod 19 = 17 5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19 5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19 5^8 mod 19 = 4 5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19 5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19 5^16 mod 19 = 16 5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19 5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19 5^32 mod 19 = 9 5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19 5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19 5^64 mod 19 = 5 => Step 3: Use modular multiplication properties to combine the calculated mod C values 5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19 5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19 5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19 5^117 mod 19 = 61200 mod 19 = 1 5^117 mod 19 = 1 Notes: More optimization techniques exist, but are outside the scope of this snippet. It should be noted that when we perform modular exponentiation in cryptography, it is not unusual to use exponents for B > 1000 bits.