The relationship between the processes of forming classes of primes in the generalized Artin hypothesis based on the theory of randomized algorithms of the probabilistic method is investigated. It is proved that probabilistic methods are the basis for constructing computer models of classes of primes in accordance with the generalized Artin hypothesis. Methods for calculating the Artin constants are developed and the convergence of the estimates of the constants in probability to the limiting values is established. The foundations of a number-theoretic analysis of Artin's constants and related classes are created.
The solution of many problems in various fields of applied mathematics depends on the solution of a significant number of problems of pure mathematics, which are still not solved. Artin's hypothesis of primitive roots is one of these fundamental mathematical problems.
The solution to the Artin problem is important for investigating the relationship between the properties of natural numbers other than zero and plus or minus 1 and the properties of the classes of primes generated by recursive mappings based on Fermat’s small theorem [1 – 3].
The numerical sequences of iterative models of cyclic fixed points of dynamical systems are determined by the properties of the primes with which they are represented.
1 (s) = s n=1 n
= 1 + pP 1 p s + 1 p2s
+ ...
(
It follows that all primes lie on this line since y – takes values from a set that includes all primes P .
Moreover, for any prime number first attempt to find the law of the distribution of primes.
In 1896, independently, Hadamard and Vallee-Poussin proved that equality is true: . In essence, this was the p (1 2 + ip ) = 0 (x) = x dt + O(x e−c ln x )
2 ln t where (x) is the number of primes p x , and the first term in the form of a logarithmic smooth function determines the logarithmic law of the distribution of primes in asymptotic form.
One of the ways to deepen the logarithmic law of the distribution of primes was the formulation in 1927 by the French mathematician Artin of the hypothesis of primitive roots of primes p P and, accordingly, of primitive roots of residue groups (Z
pZ )* modulo prime p [4 – 7].
Consider the definition of the primitive root of a prime number p . The numbers a 1 , a k 2 is the primitive (antiderivative) root of the number p , if the following relations are true: a p−1 1(mod p) p−1 a n 1(mod p),
n 1 k Moreover, n is the divisor of p − 1 = pi i .
i=1
Given the definition of a primitive root, Artin’s hypothesis is:
(x, a ) = c(a, x) (x)
(
and in probability converges to c(a) , and therefore has
a probability theory interpretation: c(a) is the probability of choosing from the set
P a prime number p such that a is its primitive (primitive) root. Note that the
first relation in (
It should be noted that Artin proposed his ratings for c(a) at a = 2 . But as proved by Hooley [5], these estimates are not true. He also proved the validity of the relation: (x,2) = c(l2n)x x + O x (llnnl(nx()x)2) (x, a) = c(a, x) (x), c(a, x) → c(a), x →
at the same time c(
, and an estimate of the value
p( p − 1)
c(
It should be noted that any number a 1 and coprime to p is the basis for considering the recursive function f (x) a x(mod p) , which leads to a recursive iterative sequence.
f (x0 = 1) = 1, f (xn+1 ) = xn+1 axn (mod p)
(
a m 1(mod p) and m p − 1
(
Modeling the processes of generating dynamic information about the structure of classes of primes on a given basis Now we return to the logarithmic law of the distribution of primes [1,2] Information about the distribution of smooth primes [1] is important when solving the discrete logarithm problem and applying algorithms for solving it in the modern coding theory, modern cryptography. It is known that finding smooth large prime numbers is very difficult. This implies that it is of considerable interest to search for the laws of distribution of primes not only with respect to their primitive roots, but also to the generating elements of the subgroups of the residue group modulo prime (Z pZ )* . Artin's hypothesis does not imply such detailed studies. Such tasks were not considered at all.
The second circumstance is that simultaneously with this fact, the dynamics of is investigated. In [7,8], the entropy of function change in
− c ln x O x e 2
f (x) = (x) − Li(x) was estimated and was proved that it has a fractal character.
The first attempt was made by D. Zagier [8], but not completed. The results obtained by the author confirm the very complex fractal behavior of this component. It follows that it is necessary to significantly improve the study of the depth of classification of primes, taking into account all models for the formation of classes of primes for any given basis a 1 . Further more detailed studies of this component confirm that although the logarithmic distribution law is fulfilled, nevertheless, complete information on the dynamic properties of primes and their relationships with their primitive roots remains poorly studied. In the future we will consider any values of the base and large units.
According to Artin's hypothesis [4 – 6], the set of such primes has the distribution
law (x, a ) as an expression:
(x, a ) = c(a ) (x)
(
It should be noted that the proof of Artin's hypothesis is important both from a theoretical point of view in number theory, and from an applied rhenium point, because it’s positive solution is important in cryptography, coding theory, and the theory of dynamical systems. In [6], a generalized Artin hypothesis was formed for any a 1 , i.e. and at the same time a may not be a primitive root. According to Artin’s generalized theory, the following equality is true:
(x, a, i) = c(x, a,i) (x) x0 = 1 , P is the set of all primes.
It is not difficult to show that for any a 1 the equality: c(a, i) = 1 i=1 where a 1, i is the index of the subgroup of the group (Z pZ )* of primes in the classification of prime numbers generated by the numbers a , c(a, i) is a constant.
P (a,i) = p P | ( p −1) card a ( p) = i
where card a ( p) is the length of the dynamic recursion xn+1 axn (mod p) at
This means that primes are evenly distributed in classes P (a, i ) for any a . By
uniformity is meant that within each class of primes P (a, i ) a logarithmic law of the
distribution of primes is preserved. The constant c(a, i) determines the measure of
root of all primes P (a,1) . For an arbitrary natural number x , the equality
puncturing prime numbers, based on the value a . If i = 1 then a is the primitive
(x, a, i) = c(a, i, x) (x)
Moreover, if x → , then c(a, i, x) tends to the limit value c(a, i) . If we put
i = 1 then c(a,1) will be Artin's constant for primitive roots. In this case a 1 ,
and a k 2 for none k N . This is true according to Fermat's theorem [1,2].
Wherein, a is the primitive root of the group of residues (Z pZ )* for any p P
such that P (a,1) = p P | ( p −1) card a ( p) = 1. It is important to investigate
(
P (a,i) = p | ( p −1) card a ( p) = ind a ( p)
(
The determination of c(a, i) for any a, i using analytical methods is unlikely in the near term. However, the formation and development of experimental mathematics [13 – 15] opens up another way to solve this problem by using computer simulation of nonlinear dynamic processes for the formation of classes of prime numbers.
The process of modeling the distribution of primes in classes P (a,1), P (a,2),..., P (a, k ),... was reduced to choosing a set of consecutive primes from a set of a sufficiently large sample of these classes. The number of primes analyzed at each interval of natural numbers was chosen to be 500,000. This choice was largely due to the fact that it was previously established that reducing this value leads to more significant fluctuations in estimates, although convergence to the limit over the entire set of any intervals, even if they are not placed consistently, has the same character.
The process of statistical testing of p P primes for checking their belonging to class P (a, i) was reduced to calculating for the selected number p the recursive procedure x0 = 1 , xn+1 = axn (mod p) until the pairs axl 1(mod p) were reached at some step i . Then carda ( p) = i and according to Fermat’s theory and the cyclic group theorem the number p − 1 is divisible by i and then inda ( p) = ( p −1) carda ( p) = i , and therefore p P (a, i) and if i = 1 , then a is the primitive root of the cyclic group (Z pZ )* , and otherwise it is the primitive root of some subgroup. At i 1 , we obtain the primitive roots of the subgroups of the (Z pZ )* residue group with the index i 1 .
The study of the distribution law of prime numbers p on their belonging to P (a, i) had the character of consistent statistical tests on the set of natural numbers containing the first 500,000 primes. At the first stage, primes p were chosen from the set p1, p2 ,..., p500000. With this x = p500000 .
For each n 2,..., x , we had to solve two problems: check n for simplicity, and if n = p P , then p − 1 was decomposed into simple factors, i.e. systematically solved two non-simple problems of checking numbers for simplicity and decomposition into simple factors. An effective algorithm for solving them was created based on probabilistic methods in the theory of elliptic curves.
As a result of analyzing a 2,..., x, P (a,1),...,P (a, l ) sets were obtained for some l x and absolutely exact values of their powers were calculated, i.e. P (a,1),..., P (a, l ) , and then estimates of: c(a,1, x) = P (a,1, x) (x),..., c(a, l, x) = P (a, l, x) (x) (17) while c(a,1, x) → c(a, l ),..., c(a, l, x) → c(a, l ) with x → were obtained.
At the next stage, work was also carried out for prime numbers from the p500001,..., p1000000 interval and the values of the c(a,1),..., c(a, l ) constants were calculated using the same scheme. At the same time l increases. The p1 ,..., p5000000 and p500001,..., p1000000 sequences were combined, and the estimates of the generalized Artin constants were again calculated and the process of their refinement was studied on the basis of the theory of large numbers in probability theory. In the process of estimating the c(a, i) constants, two important theorems were proved:
Theorem 1. For any a 2,3,..., k,... that is not a square, i.e. a k 2 The number of non-empty classes of primes tends to infinity at x → .
Theorem 2. For any a 2,3,...k ,... that is not a square, i.e. a k 2 The number of prime numbers in P (a, i) tends to infinity at x → .
These theorems are the basis of the convergence of a sequence of statistical tests to
marginal values. Since for any x N it is obvious that:
i=1
P (a,i) = (x)
P (a, i) P (a, j ) =
(18)
at i j , it follows from this that:
i=1
k
c(a, i) = 1
and this is true for all values of x → . The review [5] provides an estimate of
c(
For different a 2,3,5,6,7,8,10,11,..., the behavior of the c(a, i) constants is
complex group-theoretic and number-theoretic. The study of their dynamic properties
is beyond the scope of this work. It should be noted that the results of computer
simulation of the processes of distribution of primes are calculated with an accuracy of the
eleventh decimal place for estimates of c(
Probability-theoretic interpretation of the constant:
(x, a) c(a) = (x) at x → Consider the probability space (, F , P ) based on:
= 1,..., n ,... = p1,..., pn ,... = P Obviously at x → the numbers are (x) → , (x, a) → , but: (x, a) = P (a,1, x) , (x) = P (x) , c(a,1, x) = and at x → it is obvious that:
P (a,1, x) P (x) → c(a,1) is where x P , P
→ , P (a,i, x) = p | p x & ( p −1) card a ( p) = i P (a,1, x) (20) (21) (22) (23) (24) It follows from Artin's hypothesis that with c(a,1) there is precisely the probability of a random event P (a,1) consisting of a choice of = p1 ,..., pn ,.. of a prime number p for which a is an original root of the cyclic group (Z pZ )* . To estimate this probability, the law of large numbers and the method of successive statistical tests were used. The essence of the method is that the first test group was reduced and calculated for p1, p2 ,..., p500000 for each a 2,3,...,16 evaluation of the values of c(a, i, x ) at x = p500000 for all possible values of i = 1,2,..., k ,.., that is, c~1 (a,1, x),..., c~1 (a, k , x),... was calculated on the next iteration, the same tests were performed for the second iteration on the set c~1 (a,1, x),..., c~k (a,1, x),... c~1 (a,1, x),..., c~k (a, k , x),... , provided that the first and second samples were combined and computed values and were determined by c~(a, i, x) − c~(a,1, x) for all x . The main focus was on c(a,1, x ) . As a result of some iterations, it was found that for all a the estimates obtained:
Estimates were obtained at the same time
P (x) = p | p x
P (a, i, x) = p | p x & ( p −1) card a ( p) = i the order of the cyclic group of the subgroup (Z pZ )* . If l = p − 1 , then a is an original root, and if l p − 1 is the original form of the c(a ) Artin measure, c(a, i ) is a measure of classes by P (a, i ) in P . At that c(a, i ) = P (a, i ) P and at the same time: c(a, i ) = 1 for all a 1 i=1
This applies only to classes with indexes i = 1. For i 2 it is necessary to increase the number of statistical tests. This is naturally due to the fact that the classes P (a, i, x) for i 2 from numerical theorems contain less than prime numbers. In [1] it is stated that this decrease should be of the order of 1 i 2 [15], but this is an erroneous assertion. This is clearly seen from table 1. The degree of decline essential(27) (28) (29) ly depends on the properties of a and requires a separate study. Case a 4,9,16 requires separate investigations, because these numbers cannot be primitive roots of that number p , in accordance with the Fermat theorem [3] cannot be generating elements of groups (Z pZ )* . However, they are generating elements of the subgroups of the group (Z pZ )* with even indices. All classes with odd indices are empty sets. Table 1 shows the constants for c(a,1) for all a except 4,9,16. Analysis of the bers P = p1, p2 ,..., pk ,... is given, whose elements are ordered in ascending order. All this set was split into a subset of 500,000 primes. The number of 500,000 is due to the limitations of MS Excel, as a statistical analysis tool, on a number of characteristics of the process of generating prime numbers. Only one restriction is important. We always select 500,000 consecutive primes of the set P . In the current version of Excel, this number can be increased to one million. If you use a powerful computer, you can choose a larger number instead of a million [16].
The implemented version of the study of dynamic processes for the formation of primes includes the following indicators: the number of a simple number in the p in the ordered set of P , the value of a simple number of p , the value of the recursion length of the numbers card a ( p) at the same value of a for all prime numbers P , the index ind a ( p) of the index of the class:
ind a ( p) = ( p − 1) card a ( p) the value of the residues modulo any natural module n 1 , for all classes and any other analytic properties of primes or factors of the decomposition of the number of p − 1 into simple factors. For each simple multiplier pi in the: (30) (31) n p −1 = pii
i=1 decomposition, one parameter of the dynamic process of generating primes is presented, with separate indicators that can be analyzed for any other indicators, the values for them are deducted by the modulus of the natural number n 1 . The only exception is ind a ( p). The number of controlled indicators analyzed in the Excel environment can be expanded.
The iterations process is continued until an analytically based solution of the generated hypothesis is obtained. Since the Artin generalized hypothesis is considered in the paper, we present the results of the estimation of the constant c(a, i) for the case a = 4 and i = 2 . The number a = 4 is a perfect square, and therefore it cannot be a primitive root. In terms of Artin's generalized hypothesis, this is as interesting and important as in the case when a is an original root.
Based on the data presented in [6], we obtained estimates for c(a, i) for
a 2,3,....,32,53 and i = 1,2,...,10 . It is shown that their values are stable for
class P (
The results of experimental mathematics in table 1 of the first iteration confirm that Artin's hypothesis is correct. The estimates of the constants are obtained with the accuracy of the third decimal place. For a 2,3,...,32,53 the: and for a 4,9,16,25 all c(a,2i + 1) = 0 and: i=1 c(a, i) = 1 i=1 c(a,2i) = 1 This is due to the fact that for all a = k 2 this is true because they are primitive roots of (Z pZ )* groups, but primitive roots of their subgroups with even indices [3].
The results obtained are the basis for constructing an analytical proof of Artin’s hypothesis and its general
The c(a,1) ratings given in the table for the set of primitive roots 2,3,...,16 are
obtained for the first time based on the results of computer simulation. The literature
is known estimation c(
c(
p ( p − 1) (32) (33) (34) is not true, because it includes all primes and among them those primes for which a = 2 is not a primitive root [5]. An important result is the creation of a computer model of the process of forming classes P (a,1),...,P (a,i),.... For any values of a 1 , the interactions between the classes Table 2 and Table 3 are investigated (as a continuation). The first estimates were c(a, i) for i 2 , and it was established that the statement that c(a, i) is proportional to 1 i 2 is absolutely false [1]. Obtaining the results is the basis for further deepening research on the Artin's hypothesis using analytical methods. 3
Dynamic Properties of Formation of Classes of Prime
Numbers in the Generalized Artin Hypothesis
P (a, i) classes was carried out for many In accordance with the developed mathematical model for the formation of base classes of primes on the basis of a 1 and the calculated values of the generalized constants c(a, i) for i 1 , as a result of computer simulation it was established that the generalized hypothesis is true. Table 1 shows the values of the Artin constants, the relationship between classes, the dynamics of the formation of classes and its properties on the set of all primes P . a 2,...,32,53. Numbers a 4,9,16,25 as squares of numbers according to Fermat’s theorem [2] cannot be primitive roots of p P , and, accordingly, of residue groups (Z pZ )* modulo p . Particular attention was paid to the numbers 5,13,17,29,53 due to the fact that they belong to the class of numbers of the Chebyshev type [1,2] that is, they have representations p = 4k + 1 , while p P , and the number n is a natural number. According to Chebyshev’s assumption, the behavior of these numbers in residue classes modulo a prime number should differ from other primes.
To solve the problem of modeling classes of primes on a given basis and
evaluating the generalized constants of Artin c(a, i) , an Excel-based software package was
created that allows you to extend the modeling process to any natural numbers a 1 ,
and any set of consecutive primes whose power is a multiple of 500,000. This is the
number of primes was chosen for the reason that it is statistically represented and
provides an accurate representation of the dynamic processes of the formation of
classes P (a, i) . Table 1 shows the results of the simulation process for
a 2,3,5,8,12 values, a = 2 is included in this set for the reason that it can be
verified that the estimate [5,6] is different from the exact value. The difference begins
with the third decimal place. This fact is important due to the fact that expression (
The numbers a = 8,27,32 are interesting for the reason that the dynamic
properties of the classes P (8, i) are radically different from the other classes studied. In
particular, it was established that if a = 8 is the primitive root of p P , then
a = 2 is also the primitive root of the same prime number. Conversely, if a = 2 is
the primitive root of p P , then a = 8 will be either the same primitive root of
p or p P (
In conclusion, look back at Table 1 from a different theory of vision. The essence of a fundamentally new fact is that wherever 500,000 primes p P are selected for any a 1 , the number of primes in classes ranges from no more than 500, which is no more than a thousandth of them. This means that on any set of consecutive primes we obtain an estimate of the Artin constants up to the fifth decimal place. Statistical summation of values over the entire set of the first ten million primes made it possible to obtain estimates of the constants c(a,1) accurate to the eighth decimal place. of
It follows that the methods of computer modeling the processes of forming classes primes P (a,1), P (a,2),..., P (a, i),... and estimating constants c(a,1), c(a,2),..., c(a, i),... are the basis for the development of information technologies in modern pure and applied mathematicians.
An interesting result is the equality of constants:
c(
Conclusion Based on the analysis of the processes of formation of classes of primes for any bases, fundamentally new information technologies were created for solving complex mathematical problems using methods of modern experimental mathematics. The correctness of the developed approach and computational efficiency are proved. A generalized theory of Artin's hypothesis has been developed which its classical version is a very special case. Estimates of the Artin constants for bases greater than two are obtained, and the statistical validity of the estimates obtained is proved. A detailed analysis of the classes of primes is carried out and the foundations of effective methods for the structural analysis of classes are created. It is proved that a new method for modeling the dynamics of the formation of classes of primes and a description of their properties creates the basis for constructing more advanced models of pseudo-prime number generators, the development of new methods of information protection in modern cryptography, opens up new possibilities for constructing models of nonlinear dynamic systems. 5