Experimental Study of the Hypothesis on the Order of a Random Element of the Matrix Modular Group

Abstract

The hypothesis on the order of a random element of the matrix modular group is formulated as follows: a random element of a matrix group over the ring of residues modulo n with high probability has order greater than or equal to the value of the Euler function of n. If this hypothesis is correct, then it will be possible to significantly speed up the generation of the keys in the matrix modular cryptosystems, which will improve both efficiency and security of these cryptosystems. Experiments were carried out in five matrix modular groups by the scheme of the same type: first, a large sample of random elements of the group was formed, and then the orders of the elements of the sample were computed. Experimental results show that for all considered groups the orders of random elements satisfy the same probability distribution. Moreover, the probability that a random element of the group has “large order” (i.e., the order is greater than or equal to the value of the Euler function of n) was approximately the same in all considered groups, namely, about 0.85.