Encoding and classification of permutations b? special conversion with estimates of class power

Savchuk, M. M., Burlaka, M. K. (2019). Encoding and classification of permutations b? special conversion with estimates of class power. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics(2), 36–43. https://doi.org/10.17721/1812-5409.2019/2.3

Scientific articles investigating properties and estimates of the number of so-called complete permutations are surveyed and analyzed. The paper introduces a special S-transform on the set of permutations and determines the permutation properties according to this transform. Classification and coding of permutations by equivalence classes according to their properties with respect to S-transformation is proposed. This classification and permutation properties, in particular, generalize known results for complete permutations regarding determining certain cryptographic properties of substitutions that affect the cryptographic transformations security. The exact values of the number of permutations in equivalence classes for certain permutation sizes are calculated and the estimates of the cardinality of classes with various properties are constructed by statistical modeling. The complete list of permutation classes with the exact values of their sizes for permutations of order n = 11 is presented. The interval estimates for the size of classes with various characteristics for permutations of order n = 11, 26, 30, 31, 32, 33, 45, 55 are obtained. Monte Carlo estimates and bounds of confidence intervals used the approximation of the binomial distribution by the normal and Poisson distributions, as well as the Python programming language package Scipy. Statistical tables have been calculated that can be used for further conclusions and estimates. The classification of permutations by their properties with respect to the introduced transform can be used in constructing high-quality cryptographic transformations and transformations with special features. The classes of complete permutations with their properties are selected as the best for rotary cryptosystems applications. The obtained results can be used, in particular, to search for permutations with certain characteristics and properties, to find the probability that the characteristic of the generated permutation belongs to a collection of given characteristics, to estimate the complexity of finding permutations with certain properties. A statistical criterion of consent, which uses the characteristics of permutations by S-transformation to test the generators of random permutations and substitutions is proposed.Key words: permutations, substitutions, classification, statistical modeling.Pages of the article in the issue: 36 - 43Language of the article: Ukrainian