Algorithms for near-rings of non-linear transformations

摘要

In this note we present some algorithms to deal with nearrings, the appropriate algebraic structure to study non-linear functions. This is similar the role of rings in the theory of linear functions or that of groups for permutations. In particular, we give efficient algorithms that deal with big nearrings that are given by a small set of generators. In this context, generating involves composition as well as point-wise addition. In the extreme case, one transformation of a group of order n can generate a set of up to nn transformations.