Estimating the number of good permutations by a modified fast simulation method
- PDF / 106,199 Bytes
- 8 Pages / 595.276 x 793.7 pts Page_size
- 70 Downloads / 197 Views
ESTIMATING THE NUMBER OF GOOD PERMUTATIONS BY A MODIFIED FAST SIMULATION METHOD
UDC 519.21
N. Yu. Kuznetsov
A permutation ( s0 , s1 , ... , s N -1 ) of symbols 0, 1, ... , N - 1 is called good if the set ( t 0 , t 1 , ... , t N -1 ) formed according to the rule t i = i + si (mod N ), i = 0, 1, ... , N - 1, is a permutation too. A modified fast simulation method is proposed to evaluate the number of good permutations for N = 205 with a 5% relative error. Empirical upper and lower bounds for the number of good permutations are also given. Keywords: good permutation, modified fast simulation method, unbiased estimate, sample variance, relative error. The problem of enumeration of all complete mappings on an algebraic structure (G , + ) is one of the most difficult problems of discrete mathematics [1, 2]. A mapping f : G ® G is called complete if f (× ) is a bijection and the mapping h( x ) = x + f ( x ) is also a bijection. Hsiang et al. analyzed in [3] the complexity of finding the number of all complete mappings for various structures (G , + ) . In particular, they showed that this is an NP-complete problem for closed structures. In the present paper, we will dwell on strong complete mappings [4], where x + f ( x ) is a permutation too. In other words, let ( s0 , s1 , K , s N - 1 ) be an arbitrary permutation of symbols ( 0, 1, K , N - 1). Let us generate a new set ( t 0 , t 1 , K , t N - 1 ) according to the rule t i = i + si ( mod N ) , i = 0, 1, ... , N - 1 . If this set is also a permutation, then the original permutation ( s0 , s1 , K , s N - 1 ) is called good. The purpose of our study is to develop a method to estimate the number of good permutations for as large as possible values of N. The term “good” permutation was introduced in [5], where the application of good permutations in cryptography is detailed (see also [6], where the principles of using good permutations in rotor encryption systems are described). Computing the exact number M N of good permutations requires huge computational costs, which exponentially increase with N (note that M N = 0 for even N). The values of M N are presented in [5] for N £ 19, in [7] for N £ 23, and in [8] for N £ 25. Computing M N if N increases at least by two is a fundamental problem and is first dependent on computer development. Therefore, the analysis of M N is focused on approximate computations, in particular, on asymptotical and statistical methods. The total number of permutations is N !, therefore, the deterministic problem of finding M N formulated above is equivalent to the probabilistic problem of estimating the probability PN that an arbitrarily chosen permutation is good, M N = N ! PN . Since PN = 0 for even N, in what follows, we will consider only odd values of N. Cooper and Kovalenko proved in [9] that PN £ ae - cN for large N, with c ³ 0.0885. Kovalenko improved this ln 2 estimate in [10]: ñ ³ » 0.3466. Cooper et al. hypothesized in [5] that 2 PN ~ ae - cN
(1)
as N ® ¥, and c Î[ 0. 5, 1]. They also proposed an approximation in [5] to estimate PN f
Data Loading...
