Today someone asked me if I knew of a large number class in C++. Specifically they wanted to be able to hold the value 558 in a variable. I was suspicious of why they would want to do this and asked what their ultimate goal was. It turned out they wanted to calculate nx mod p for arbitrary values of n,x and p, their ultimate goal being an implementation of Diffie Hellman key exchange.

 

Now, Calculating nx then taking the modulus p of it is a valid way of solving the problem, but it has a few nagging problems. The first is that you must be able to handle large numbers in whatever environment you are doing these calculations in, and the second is that you must be able to calculate these large numbers and take them modulo some value. To begin with, I remembered back to my early days at University when we covered something called Modular Arithmetic. Consider this example: Read the rest of this entry »