Determining the Equivalence of Algebraic Expressions by Hash Coding

Let S be the set of rational exponential expressions with complex rational coefficients, single level exponentiation, and no division or element i in the exponents. Let p be a prime integer of the form 4q ~ 1, where q is also prime. The expressions in S can be matched for algebraic equivalence by substituting random integer values for the variables, evaluating the exponents mod (p -1), and evaluating the rational expressions rood p. When this is done equivalent expressions will evaluate to the same result; while, in typical situations, two expressions selected at random will evaluate to the same result with probability about 1/q. Thus, if p is taken close to the word size of a 36-bit machine, the probability of matching equivalent expressions is 1 and the probability of random match is about 10 -9. The problems of extending this scheme to allow division in the exponents and preserve the relation e ~" ----1 are studied. No solutions to these problems were found, but a scheme which handles some cases by special case checks is presented. This scheme was implemented in a program for algebraic simplification.