2.1

Pattern of exponential number

Let g^e be an exponential number, where g and e are positive integers. Let g^e = d_md_m−1…d₀ denotes the value of g^e from taking multiplication upon g with e-1 times, and it demonstrates that g^e has m+1 digits. In a base-10 numerical expression the value of the leftist digit is d_m × 10^m, the second digit is d_m−1 × 10^m−1, etc., and d_n ∈ {0, 1, …, 9}, n = 0, 1, …, m-1.

Definition The pattern of an exponential number is denoted by (g^e), where is defined as the distribution of digits in an (m + 1)-tuple vector, where d_m ≠ 0.

Let’s present two examples. The value 2⁴⁷ = 140737488355328 has 15 digits, and the pattern of 79⁵³, denoted by (79⁵³), is expressed as follows:

Equation (1) indicates that the (79⁵³) pattern consists of 101 decimal digits, which is considered a vector or sequence with 101 elements. There exists neither the explicit relationship between and two patterns, nor the relationship between g^e and (gh)^e, where h is an arbitrary positive integer, n > m, and d₀ might not equal to c₀. The only method that can derive pattern (C_nC_n−1 … C₀) from (d_md_m−1 … d₀) is through operating multiplication between(d_md_m−1 … d₀)and g^k = (e_ke_k−1 … e_o), i.e., 2⁴⁷ = 140737488355328 = 70368744177664 × 2, where 2⁴⁶ = 70368744177664.

Though addition chain algorithm might be applied for fast calculating g^e and deriving the pattern of g^e, the multiplication of two integers is not a linear operation, where the product of two decimal digits can bring overflow to the adjacent next digit, and the overflow is data dependence which can only be analyzed case by case. In other words, there exists no general expression that can describe the relationship between two patterns obtained from two different exponential numbers. More specifically, it is especially challenging to find a set of functions c_k = f_k (d_m, d_m−1, … d₀), k = 0, 1, …, n, which can be used to describe the relationship between C_nC_n−1 … C₀ and d_md_m−1 … d₀ for arbitrary {c_i} and {d_i} two sets.

The pattern of g^e is unpredictable, which is characterized with quasi-random nature. In Reference⁹ entropy was applied to evaluate the uniformity level of exponential decimal patterns. Regardless of whether the base element is a prime or a composite number, it showed that pattern with length larger than 90 can reach 99.9% uniformity level⁹.

2.2

Complexity hierarchy

As described in Reference¹⁰, those algorithms that can be performed in polynomial time are considered efficient algorithm, and those algorithms that can only be performed in exponential time are inefficient algorithms. We can present a hierarchy of increasing complexity orders as follows:

Taking the execution time of solving factorial function with input size n = 30 as an example, it is still infeasible for the current computing system, which is 8.4 × 10¹⁴ centuries¹⁰.

3.1

Construction of ideal uniform pattern

Let N = 10n + m be the number of decimal digits of an exponential pattern, where n > 0 and 0 ≤ m ≤ 9. The procedures of obtaining a pattern with the ideal uniform distribution based on arbitrary exponential pattern are summarized as follows:

(1) The first 10n digits of an exponential pattern are grouped into n blocks, where each block has ten digits, and we discard the rest m digits from this pattern.

(2) We should check the existence of repeating decimal digits from the first digit till the last one in each block, and delete all repeating digits which are appeared at the later locations in this block. We make a record the number of digits that are deleted in each block.

(3) We should insert the same number of decimal digits which are deleted in Step (2), and these decimal digits are chosen in ascending order from the rest of other ten decimal digits that are not appeared in each block. In this step, ten decimal digits appear exactly one time in a 10-tuple block throughout the entire n blocks.

(4) We can index these n blocks sequentially with subscript number {0, 1, 2, …, n-1}, respectively, to identify the actual locations when the associated block is applied for operating permutation, where the block indexed by k indicates that ten decimal numbers of this block should add 10k to denote ten locations at the interval between 10k and 10k + 9.

From these four steps we can obtain a new pattern of length 10n with the same number of ten digits {0, 1, 2, …, 8, 9} within this pattern, and this implies that new pattern can match the ideal uniform distribution requirement, where , ∀i∈{0,1,2,…,8,9}.

Let’s take the (2³¹²) pattern as an example for demonstration the procedures of creating an ideal uniform distribution pattern. In equation (2), the (2³¹²) pattern consists of 94 digits, and we would discard the last four digits 2096, which are underlined, to form a new pattern with 90 digits. New pattern can be grouped into nine blocks, and we would use the first block for demonstration the above procedures. In the first block, 3 and 9 two digits appear three times 8343699359, where the latter two 3 and two 9 digits are underlined indicating that these four repeating digits should be deleted from this block. This results in . Among ten decimal digits only six digits {8, 3, 4, 6, 9, 5} appear in this block, thus we should insert the remaining four digits {0, 1, 2, 7}, which are arranged with ascending order, to the end of 834695 to form a new 10-tuple block. We use expression to present this operation, where these four digits are overlined for identification. The operation of other eight blocks is similar to the first one, from which we derive a new pattern of length 90, denoted by [2³¹²].

To make a link between the 90 digits of an ideal uniform distribution pattern [2³¹²] and a set of ordered {0, 1, 2, …, 89} locations, here [2³¹²] is indexed by a set of subscript numbers k ∈ {0,1,2,…, 8} indicating that ten digits of each block should add the value 10k, respectively, to present the actual ten locations of the associated block, i.e.,

and

However, we would omit the subscript number from the pattern to simplify the expression of formula and to operate adequately the location permutation, and the ideal uniform pattern based on exponential number 312³¹² is expressed as follows:

Except the patterns of (2³¹²) and [2³¹²], Table 1 presents also the patterns of (79⁵³), [79⁵³], (79⁵⁴), and [79⁵⁴] for comparison.

Table 1.

Exponentiations and the associated ideal uniform patterns.

3.2

Permutation based on idea exponential pattern

Let plaintext be English message with length 9k < N ≤ 10k, where each one of English letters, comma, semicolon, period, blank space and special symbols occupies one location, and these N symbols are indexed by a set of ordered elements {0, 1, 2, …, N-1}. The first step of operating location permutation is inserting 10k - N numbers of “o” to the end of message for matching the same 10k length of an ideal uniform exponential pattern. Taking English sentence “The more you read, the more healthy and brave your spirit will be.” with length 66 as an example, we can add four oooo to the end of this message to become 70 length, which is given by “The more you read, the more healthy and brave your spirit will be.oooo”.

In the second step the contents of message are grouped into k blocks, which are indexed by {0, 1, 2, …, k-1}. Let f_k denotes the permutation function of processing the k-th message block by using the k-th block of an ideal uniform pattern. Two permutation functions taken from the first and the eight blocks of [2³¹²] are shown for demonstration, which are

and

In equation (4) all digit numbers belong eighties, we would like to delete the first digit 8 from f₈ to simplify the expression and permutation operation, which derives the following mapping results

The first step of operating location permutation is the partition of plaintext into a set of 10-digit blocks, that is, “The more y| ou read, t| he more he | althy and | brave your spirit will be.oooo”. In this expression, we would use the “,” symbol to indicate the partition instead of the semicolon symbol “,” to avoid the confusion with message, because “,” is considered the content of message. We may apply the first seventy digits of the ideal uniform pattern [79⁵³], which is given by “3751682049|2096143578|0817956324|3018245679|9042786315|0857231946|1978462035”, to operate the location permutation.

The first block “Te more y” results in “e rT emhoy” by operating permutation based on the first ten digits 3751682049, and the second block “ou read, t” becomes “ueoda,r t” based on 2096143578, etc. By operating permutation based on [79⁵³], it derives “e rT emhoy| ueoda,r t | h h eremeo| ltya andh | ruvoarye b | triwpiis | olooeo. bl”.

3.3

Local to global permutation

The permutation function f_k is a 10-by-10 mapping scheme, where each set of 10 locations within the same block operates location permutation independently, from which the initial cyphertext is derived by combining all blocks collectively. This scheme can achieve only local permutation between a pair of 10 locations from two sets, where the computing load to attack each block by brute force is 10! = 3628800. When plaintext is with 10k length, the computing load can reach only to the amount of O((10!)k).

To enable global permutation through entire domain of message, which is to operate permutation across the whole set of locations {0,1,2,…, N −1}, first the initial cyphertext can be circularly shifted to the right by m ∈ {0,1,2,…, N − 2} steps, then the second location permutation is applied by another ideal uniform pattern. In other words, plaintext is subject to one circular shift and two rounds of location permutation. When i ≥ 1 rounds of circular shift are applied, the cypher space will approach to the amount of (N – 1)(N – 2) … (N – i) ≡ O(Nⁱ), and that of i + 1 rounds of permutation will be proportional to O(Nⁱ · (10!)^(N/10)(i+1)).

The proposed “permutation + circularshift + permutation+…” encryption scheme can achieve the complexity level of a factorial function, where O(Nⁱ · (10!)^(N/10)(i+1)) → N! for some small i. As shown in Table 2, O(N · (10!)^N/5) > N! when 20 < N < 50, and O(N² · (10!)^3N/10) > N! when 60 < N < 120, where the number within the quotation mark (•) indicates the boundary where Nⁱ (10!)^(i+1)N/10 > N! on the same row.

Table 2.

Comparison of Ni (10!)(i+1)N/10, AESs and factorial function N!.

Note: The number marked by quotation mark (•) indicates the boundary where Ni (10!)(i+1)N/10, and [•] mark indicates the proposed scheme outperforms other AES on the same row.

Equation (6) presents the results of operation two rounds of permutation based on [79⁵³] and [79⁵⁴] two ideal uniform patterns and one circular shift to the right by 25 steps. It is obvious that deriving “rir w etbylooeoispi rb.eoTl eodehouamyh h, er ttloeyare mav oneadhr” from plaintext “The more you read, the more healthy and brave your spirit will be.oooo” is straightforward. However, can one restore “The more you read, the more healthy and brave your spirit will be.oooo” from cyphertext “rir w etbylooeoispi rb.eoTl eodehouamyh h, er ttloeyare mav oneadhr”? when the permutation information of [79⁵³] and [79⁵] are unavailable. It is extremely challenging!