[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
Viewer Hans Klein recently sent a number of updates for out Big Integers Arithmetic Unit. I had written and asked about a couple of methods, ModPow, and InvMod, which seemed rather useless to me. Here's his reply which convinced that I was mistaken.
Hi Gary, Jan 25, 2005
you asked me what the use is of the modpow and invmod functions for your BigInts unit.
First of all the modpow function.
Fermat's little theorem states: if p is prime then a^(p-1) mod p =1. (2<=a<p). So if you calculate e.g 2^6 mod 7 you will find the result will be 1. (2^6=64, 64 mod 7=1). If a^(p-1) mod p <>1 then p is not prime. You might think you have a simple prime test here. Alas the reverse of Fermat's little theorem is not always true: Calculate e.g 2^560 mod 561 and you will find 1. But 561 is not a prime because it evenly divides 3. Now is it so that for other bases than two different numbers fail this so called Fermat test. There are however pseudo-prime numbers that fail for (almost) all bases. These are the so called Carmichael numbers.
The Miller Rabin prime test is a variation on the (weak) Fermat prime test. It can detect Carmichael numbers. It too uses the modpow function as you will see when you inspect my code. Experimenting with the modpow function is, in my view, a valid reason for implementing it.
Now the invmod function.
If two numbers a and b are relatively prime (that is to say: gcd(a,b)=1) there is exactly one number c=inv(a) mod b so that c*a mod b=1. But: if p is another number and you calculate q=p*a mod b then c*q mod b gives you back a! This is used in cryptography. You can use c and a as keys two encrypt and decrypt. The RSA system is an elaboration on this system. When making the keys for RSA you use the modpow and invmod functions both. When encrypting and decrypting you use the modpow function.
So you see when you have those two functions you have all you need to make your own cryptographic system. I became interested in this subject when I taught a cryptography course at my high school and I think a calculator that has these functions could be of great help for other teachers that want to give an introductory course in number theory and cryptographic applications of number theory.
Copyright © 2000-2013, Gary Darby
All rights reserved.