Procedural Programming

We give  a few examples of programming in Mathematica.  These programs illustrate
 the features of Mathematica discussed in the tutorial  and section on lists. In addition,
 we also use some of Mathematica's string processing  functions. These functions are
 introduced as needed.

Base b Representation

We write a program to find the  digits in the  base b representation of a positive
 integer.  The problem is easy,  because the lowest digit when n is represented in
 base b is the remainder when n is divided by b, and the higher order digits form the
 quotient.  Hence we can write the following procedure that returns a list of the base b
 digits.

basebdigits[n_,b_]:= Module[ { m=n, l={}},
                         l= { Mod[ m,b]};
                         m=Quotient[n,b];
                         While[m>0,
                             PrependTo[ l, Mod[m,b]];
                             m=Quotient[m,b];
                              ];
                         Return[l]];

basebdigits[ 137,10]

basebdigits[ 137,2]

The first argument of Module is a list of variables used in the procedure. In this case, we use
 m and l (for the list of digits). The variables can be initialized in the first argument of Module, i.e.
 within the braces.  The program can also be written recursively because we are 
 computing the basebdigits  of the quotient in the While loop. Here is another program that
 computes the base b digit expansion, this time, by calling itself with a smaller argument.

newbasebdigits[n_,b_]:= Module[ {m=n, res= { Mod[n,b]}},
                   m= Quotient[ m,b];
                   If[ m>0,
                      res=Join[newbasebdigits[m,b],res]];
                   Return[res]]

newbasebdigits[137,2]

Instead of having the output as a list of  digits, we may prefer to have it in the standard
 representation as a string, that is, 10001001 instead of { 1,0,0,0,1,0,0,1}. This can
 be done using the ToString command of Mathematica that will give the string form of
 an object, in this case, a string.  We convert each digit to a String form and then join
 them using the StringJoin command. A list of String related commands is given in the next
 section.

basebform[n_,b_]:= StringJoin[ 
                       Map[ ToString[ #] &,
                            basebdigits[n,b]]]

basebform[ 137,2]

Exercise:  Write a program to take the string form of a number and return its value
 The Mathematica function Characters will return a list of characters and the command
 ToExpression will give the value of the string form of a digit.

String Manipulation

We develop some functions for manipulating  strings. A string in Mathematica is
 a collection of characters in double quotes ". For example,

 s= "abced01234567" 

 is a string. There are many functions for manipulating strings. Here is a brief list
 of the most useful functions.

Characters[string] gives a list of characters in a string and
StringJoin[ list]     returns a string from the specified set of characters.

Characters[ "abcdefg"]

StringJoin[ %]

The ASCII character codes for each character can be obtained from
ToCharacterCode[ string]
 and the string form of a list of character codes is obtained using
FromCharacterCode. These functions are useful is manipulating strings
 to perform arithmetic operations on them.

 Additional functions that are useful for String manipulation are the following.

StringLength[ s]     Gives the number of characters in s.

StringTake[ s,k]    Gives the first  k characters of s.

StringTake[ s, {k,l}]  Gives the characters from positions k through l.

StringPosition[ s, t]   Gives a list of position where string t occurs in  string s.

StringDrop[ s, {k,l}] Returns a string with the characters from positions k through l of  
                                  s removed.

 Strings can be joined  using StringJoin[ s1,s2] or s1<>s2.

StringReplace[ s, { s1->t1,....}] will replace all occurrences of s1 by t1 in s.

 We illustrate these with the following examples.

Shift Cipher:

In the shift cipher, each character is represented by 
 a number and then a fixed number (the key) is added to all the characters to form
 the cipher text. For simplicity, we remove all   spaces and punctuation from
 the  text and assume that every character is a lower case letter.  This can be accomplished 
 by the ToLowerCase command.  

 We will convert a string to its  character code and then add the constant number to
 it and then convert is back to the character code.

ToCharacterCode[ "abcdefghijklmnopqrstuvwxyz"]

We see  that the codes are consecutive. This will make the computation simpler. 
 If we subtract 97 from the code, and then  add  number modulo 26, then add 97 to the number
 and convert it back to a string, then we will have the cipher text. This is done in the
 following procedure.

shiftcipher[ s_, k_]:= Module[ {s1},
                         s1=StringReplace[
                             ToLowerCase[s], { " "->""}];
                         l=ToCharacterCode[ s1]-97;
                          l=Mod[ l+k,26];
                          s1=FromCharacterCode[l+97];
                          Return[s1]]

shiftcipher[ "abc",3]

shiftcipher[ "I came I saw I conquered", 7]

The string should have no punctuation other than spaces. If you want to allow punctuation, then
 the  StringReplace command in the procedure needs to modified appropriately. Since
 conversion of a string to numeric form is common, we will write a separate function for this.

ToNumericForm[m_String]:= Module[ {text},
              text=ToLowerCase[m];
              If[Length[StringPosition[text," "]]>=1,
              text= StringReplace[text," "->""]];
              text=ToCharacterCode[text]-97;
              Return[text]]

ToNumericForm[ "GHIJKLM "]

We also need the inverse of this operation, to convert a list of numbers modulo 26 to 
 the string form.

ToTextForm[ plain_List]:=FromCharacterCode[plain+97]

Frequency Analysis:

Many  simple ciphers can be cryptanalyzed by frequency analysis, that is, counting
 the frequency of  occurrence of each character and then  comparing this to  the known
 frequencies of the characters in English text. The same analysis can be performed 
in language or character set if Mathematica supports that character set.

 For the function, we use the String Position command to find the places that each
 character occurs in the string and then find the length of this list. Since we have to apply this
 to 26 letters of the alphabet, it is convenient to use Map and other list 
manipulation functions. The result will be a list  with elements of the form
 { character,frequency}.

freq[str_]:= Transpose[ {  Characters["abcdefghijklmnopqrstuvwxyz"],
 Map[ Length[StringPosition[str,ToString[#]]] &,
              Characters["abcdefghijklmnopqrstuvwxyz"]]
             }]

freq[ "ghi djksiwlabc dksoabcndjdksueos"]

Exercise:  Use this function to determine the frequency of occurrence of 
letters in the English language.  You should eliminate punctuation in the frequency analysis.

Exercise: Write a function to Plot the frequency distribution. For this, you can
 modify the previous function to return a list of elements of the form
 { character code, frequency} where character code is a number between 0 and 25.

Vigenere Cipher

The Vigenere Cipher is similar to the  shift cipher but instead of adding  a number
 to each character, it operates on blocks of characters. A secret key word of length k
 is added to blocks of k letters. To implement this cipher, we need a function that
 will break a list into sublists  with k elements each. To implement this, we must ensure that
 the length is a multiple of k. This can be done by appending the necessary number of
 characters to the end of list  when the string length is  not a multiple of k.  A function to
 break a text into blocks of k letters is given below.  The built -in function Partition can also
 be used but we must ensure that the length is a multiple of k.

breaktext[m_String,  key_]:= Module[ {k=StringLength[key] },
             text=ToNumericForm[m];
              n=Length[text];
              plaintext={};
              While[ n>=k,
                 AppendTo[plaintext,Take[text,k]];
                 text=Drop[text,k];
                 n=n-k;];
              If[ 0<n<k, AppendTo[plaintext,
                          Flatten[AppendTo[text,Table[Random[Integer,26],
                                   {i,1,k-n}]]]]];
               Return[plaintext]]

breaktext[ " abc def ghijklmop", "abcd"]

In the Vigenere cipher, we take a plaintext M and add a key word  K  as in the
 following example.

 Suppose M= I came I saw Iconquered and the key is Egypt,

 the we add the two strings

 IcameIsawIconquenred
EgyptEgyptEgyptEgypt

by doing arithmetic modulo 26. For this we generate the character codes of the two strings
 and then add them using the Map command.

vigenere[M_String, K_String]:= 
              Module[ { l},
                
                l=breaktext[M,K];

                l=Mod[Map[ #+ToNumericForm[K] &,l],26];
                l=Flatten[l]+97;
                Return[FromCharacterCode[l]]]

vigenere[ "I came Isaw I conquered", "Egypt"]

The  cryptanalysis of the Vigenere cipher also requires a frequency analysis of
 digrams and trigrams, two and three letter  strings of the English alphabet. The program is
 similar to the frequency analysis of the letters of the alphabet that was given above.

The program finds all the two letter sequences in the text and counts their frequency. The second
 argument is an integer  a that can be set to return only those  digrams that occur  at least
 a times.

digrams[cipher_,a_]:= Module[ {k=1,str,l,i,p, s={}},
                    i=1;
                   l=StringLength[cipher];  
                   While[i< l-4  ,
                   str=StringTake[cipher,{i,i+1}];
                   p=Length[StringPosition[cipher,str]];
                   If[p>a, 
                     AppendTo[s, {str,p}]];
                   i++];
                   Return[Union[s]]]

Exercise:  Rewrite the program without using a While statement.

Exercise: Modify the program to count the frequency of trigrams. Trigrams are sequences
 of three letters. The frequency analysis of trigrams is very useful because "THE" is the
 most common trigram in the English language.

Sieve of Eratosthenes

The sieve of Eratosthenes is the classical method of generating prime numbers. The 
 procedure is very easy to implement in Mathematica. We make a list of integers
 and remove the multiples of two, of three, and so on, until all we are left with are
 primes. If we generate a table of primes up to n, then it is necessary to eliminate
 the  multiples of the primes up to square root of n.

SieveOfEratosthenes[n_]:= 
         Module[ {t,P,i=1,x},
         t=N[Sqrt[n]];
         P=Range[2,n];
         While[ P[[i]] <= t,
           
          x=Table[k P[[i]],
                     {k,P[[i]], Floor[n/P[[i]]]}];
                      
          P=Complement[P,x];
           i++];
          Return[P]]

SieveOfEratosthenes[100]

Remarks: Do not use this sieve  to generate primes  for n more than 10^5 as it is
 likely to be very slow. For larger n, it is better to  modify the sieve to generate 
  primes between n1 and n2, by reading in a list of primes  up to square root of n2.

 Also, it is better to save the result in a file rather than display it on a screen. This
 can be done by the >> operator and the file can be read in using << or the
  ReadList command.

SieveOfEratosthenes[ 1000]>> primes;

primes= ReadList[ "primes", Expression];

primes

Notice  the extra set of braces around the expression. These can be removed
using the Flatten command.

primes=Flatten[primes];
primes[[50]]

Exercise: Write a function Sieve[n,m]  to create a list of primes between n and m. To start
 the sieve you will need a list of primes up to square root of m.