APPENDIX AA.1. Efficient Computation of Powers Modulo mWe illustrate an efficient method of computing powers modulo mwith an example. Assume that we want to compute 3547mod 10.First write 547 in base 2: 1000100011, hence 547 = 29+ 25+ 2 + 1 =((24+1) 24+1) 2+1, so: 3547= ((324·3)24·3)2·3. Next we compute theexpression beginning with the inner parenthesis, and reducing modulo10 at each step: 32= 9 (mod 10), 322= 92= 81 = 1 (mod 10),323= 12= 1 (mod 10), 324= 12= 1 (mod 10), 324· 3 = 1 · 3 = 3(mod 10), etc. At the end we find 3547= 7 (mod 10).The algorithm in pseudocode would be like this:1: procedure pow mod(a,x,m) {computes a^x mod m}2: p := 13: bx := binary array(x) {x as a binary array}4: t := a mod m5: for k := 1 tolength(bx)6: begin7: p := (p * p) mod m8: if bx[k] = 1 then{if k-th binary digit of x is 1}9: p := (p* t) mod m10: end11: return p12: end pow mod150A.1. EFFICIENT COMPUTATION OF POWERS MODULO M 151The following is a program in C implementing the algorithm:int pow(int a, int x, int m) {intp = 1;int y = (1 << (8 * size of(int) - 2));a %= m;while (!(y & x)) y >>= 1;while (y) {p *= p;p %= m;if (x & y) {p *= a;p %= m;}y >>= 1;}return p;}The followingis an alternative algorithm equivalent to runningthroughthe binary representation of the exponent from right to leftinstead of left to right:1: procedure pow mod(a,x,m) {computes a^x mod m}2: p :=13: t := a mod m4: while x> 05: begin6: if x is odd then7: p := (p * t) mod m8: t:= (t * t) mod m9: x := floor(x/2)10: end11: return p12: end powmodA.2. MACHINES AND LANGUAGES 152A.2. Machines and LanguagesA.2.1. Turing Machines. A Turing machine is a theoretical de-vice intended to define rigorously the concept of algorithm. It consistsof1. An infinite tape made of a sequence of cells. Each cell may beempty or may contain a symbol from a given alphabet.2. A control unit containing a finite set of instructions.3. A tape head able to read and write (or delete) symbols from thetape.Tape headTapecontrolunitFigure A.1. Turing Machine.Each machine instruction contains the following five parts:1. The current machine state.2. A tape symbol read from the current tape cell.3. A tape symbol to write into the current tape cell.4. A direction for the tape head to move: L = ’move one cell tothe left’, R = ’move one cell to the right’, S = ’stay in thecurrent cell’.5. The next machine state.Turing machines are generalizations of finite-state automata. Afinite-state automaton is just a Turing machine whose tape head movesalways from left to right and never writes to the tape. The input ofthe finite-stateautomaton is presented as symbols written in the tape.In general we make the followingassumptions:1. An input is represented on the tapeby placing the letters ofthe strings in contiguous tape cells. All other cells contain theblank symbol, which we may denote λ.A.2. MACHINES AND LANGUAGES 1532. The tape is initially positioned at the leftmost cell of the inputstring unless specified otherwise.3.There is one starting state.4. There is one halt state, which we denote by “Halt”.The execution of a Turing machine stops when it enters the Halt stateor when it enters a statefor which there is no valid move. The outputof the Turing machine is the contents of the tape when the machinestops.We say that an input string is accepted by a Turing machine ifthemachine enters the Halt state. Otherwise the string is rejected.This can happen in two ways: by entering a state other than the Haltstate from which there is nomove, or by running forever (for instanceexecuting an infinite loop).If a Turing machine has at least two instructions with the same stateand input letter, then the machine is nondeterministic. Otherwise it isdeterministic.Finite-State Automata. A finite-state automata canbe interpretedas a Turing machine whose tape head moves only from left to right andnever writes to the tape.Pushdown Automata. A pushdown automaton is finite-state au-tomaton with a stack, i.e., a storage structure in which symbols can beput and extracted from it by two operations: push (place on the top ofthe stack) and pop (take from the top of the stack)—consequently thelast symbol put into the stack is the first symbol taken out. Addition-ally there is a third operation, nop, that leaves the stack intact. Thenext state function takes into account not only the current state andthe symbol read fromthe input, but also the symbol at the top of thestack. After reading the next input symbol and the symbol at the topof the stack, the automaton executes a stack operation and goes to thenext state. Initially there is a singlesymbol in the stack.Linearly BoundedAutomata. A linearly bounded automaton is aTuring machine whose tape is limited to the size of its input stringplus two boundary cells that may not be changed.Computable Functions. Consider a Turing machine T working onsymbols from an alphabet of only one symbol A = {|} (“stroke”). Letf : N→ N the function defined so that f(n) = m means that if theA.2. MACHINES AND LANGUAGES 154initial input of T consists of a string of n + 1 strokes, the output of Tis a stringof m + 1 strokes. We say that f is computed by the Turingmachine T . A computable function is a function computed by someTuring machine. A computable function f(n) halts for a given valueof its argument n if T with input n + 1 strokes halts. A computablefunction f is total if f(n) halts for every n.An effective enumeration of a set is a listing of its elements by analgorithm.A.2.2. Hierarchy of Languages. Here we mention a hierarchyof languages that includes (and extends) Chomsky’s classification, inincreasing order ofinclusion.1. Regular languages. They are recognized by finite-state automata.Example: {ambn| m, n = 1, 2, 3 . . . }.2. Deterministic context-free languages, recognized by determinis-tic pushdown automata. Example:{anbn| n = 1, 2, 3 . . . }.3. Context-free languages, recognized by nondeterministic push-down automata. Example: palindromes over {a, b}.4. Context-sensitive languages, languages without λ recognized bylinearly bounded automata. Example: {anbncn| n = 1, 2, 3 . . . }5. Unrestricted or phrase-structure grammars, recognized by Tur-ing machines.6.Recursively enumerable languages. A language is recursivelyenumerable if there is a Turing machine that outputs all thestrings of the language. Example: {an| fn(n) halts}, wheref0, f1, f2, . . . is an effective enumeration of all computable func-tions.7. Nongramatical languages,