restart;Mod Arithmetic

This procedure tests if a given list of numbers is a permutation, i.e. all entries are different from each other. In particular, if the length of the list is m and all members are integers in the range 0, ... , m-1 (as occurs when doing arithmetic mod m), then the list is a permutation iff it is a permutation of 0, .. , m-1. permutation := proc(num_array) local i, j, perm , m : m := nops(num_array) : perm := true : for i from 1 to m-1 do for j from i+1 to m do if num_array[i]=num_array[j] then perm := false: fi od od: perm; end: Here is an example.permutation([2,3,1]); permutation([1,1,6,1,6,6]);

This procedure produces, for W = 1, ... , n-1, a list of all multiples W*r mod n.mod_mult := proc(r,n) local mult, W : for W from 1 to n-1 do mult[W]:= W*r mod n od : convert(mult, 'list'); end:Here is an example. mod_mult(3,6) ; mod_mult(5,8);permutation(mod_mult(3,6)); permutation(mod_mult(5,8));

This procedure produces, for W = 1, ... , n-1, a list of all powers W^e mod n.mod_power := proc(e,n) local power, W : for W from 1 to n-1 do power[W]:= W&^e mod n od : convert(power, 'list'); end:Here are some examples.mod_power(3,7) ; mod_power(17,33);

This procedure produces, for any list L = {a,b, ...} and exponent d, a list of the powers (a^d, b^d, ... } computed mod n.mod_power_list := proc(L,d,n) local power, i : for i from 1 to nops(L) do power[i]:= L[i]&^d mod n od : convert(power, 'list'); end:Here is an example.mod_power_list([2,5,8],3,5);

This example demonstrates a property of mod multiplication.It first checks if r and n are relatively prime. If so, it shows that for the multiplication table mod n, the numbers in the row corresponding to multiplication by r each occur exactly once. In other words, multiplication by r mod n produces a permutation (shuffle) of {1, ... , n-1}. Moreover, multiplication by the inverse s of r mod n reverse shuffles back to the original order. (Try some other examples for yourself.)n := 25; r := 6;mod_mult(1,n);gcd(r,n);mod_mult(r,n);permutation(mod_mult(r,n));s := 1/r mod n;s * mod_mult(r,n) mod n;

This is an example of Fermat's Little Theorem. (Also try some other examples of your own.)mod_power(7,7); mod_power(6,7);Here is another example.mod_power(31,31); mod_power(30,31);

This example looks at the type of powers W^e mod n that occur in RSA cryptography.We suppose that p and q are distinct primes, and let n = p*q, m = (p-1)*(q-1).The example checks if e and m are relatively prime. If they are, it then shows that taking powers W^e mod n of W produces a permutation (shuffle) of {1, ... , n-2}, and that taking powers again by the inverse d of e mod m reverse shuffles back to the original order.(Try some examples of your own.)In RSA cryptography, p and q are random primes (MUCH bigger than the following example).p:=17; isprime(p); q:=5 ; isprime(q); n := p*q; m := (p-1)*(q-1);The number e is the encoding exponent.e := 27; gcd(e,m);In RSA cryptography, and in this ``toy'' example, the secret number W is one of the following (but not too small).W = mod_power(1,n);The secret number W is raised to the power e to give the corresponding coded number C as in the following list.C = mod_power(e,n);We check that this operation does indeed "shuffle" the set of all possible numbers.permutation(mod_power(e,n));The number d is the decoding exponent.d := 1/e mod m;Raising the coded number C to the power d gives the decoded number D. This should be the same as the original secret number W, which we now see it is!D = mod_power_list(mod_power(e,n),d,n);