Paper Info
Title
Unification modulo a partial theory of exponentiation
Abstract
Modular exponentiation is a common mathematical operation in modern cryptography. This, along with modular multiplication at the base and exponent levels (to different moduli) plays an important role in a large number of key agreement protocols. In our earlier work, we gave many decidability as well as undecidability results for multiple equational theories, involving various properties of modular exponentiation. Here, we consider a partial subtheory focussing only on exponentiation and multiplication operators. Two main results are proved. The first result is positive, namely, that the unification problem for the above theory (in which no additional property is assumed of the multiplication operators) is decidable. The second result is negative: if we assume that the two multiplication operators belong to two different abelian groups, then the unification problem becomes undecidable.
Year
DOI
Venue
2010
10.4204/EPTCS.42.2
UNIF
Keywords
Field
DocType
modular multiplication,abelian group,modular exponentiation,multiplication operator,key agreement protocol,symbolic computation
Algebra,Modulo,Unification,Kochanski multiplication,Knuth's up-arrow notation,Exponentiation,Exponentiation by squaring,Mathematics,Modular exponentiation
Journal
ISSN
Citations 
PageRank 
EPTCS 42, 2010, pp. 12-23
0
0.34
References 
Authors
8
3
Name
Order
Citations
PageRank
Deepak Kapur12282235.00
Andrew M. Marshall285.07
Paliath Narendran31100114.99