Symmetry of numbers
Symmetry of numbers
1. Introduction
In our world, everything is interconnected, similar to each other, has the same or similar parameters. Often these properties are called symmetry. In the Brief Oxford Dictionary, symmetry is defined as "Beauty, due to the proportionality of parts of the body or any whole, balance, similarity, harmony, coherence." [1] Very often, symmetry manifests itself in mathematics and physics. In physics, the symmetry properties are clearly manifested in quantum mechanics and its mathematical apparatus, for example, the Schrödinger equation [2]. In mathematics, there is a special mathematical apparatus that operates with the concepts of similarity and symmetry. This mathematical apparatus is called group theory [3]. One of the practical applications of symmetry in mathematics is public key encryption “RSA” [4].
2. The matrix of residual primes
Consider the definition of residue and comparison modulo. Here is the definition given in the modern explanatory dictionary. The number “a“ is called the residue of the number “b“ modulo “m“, if the difference “a - b“ is divided by “m“ (a, b, m> 0 are integers). That is, “a“ is comparable to “b“ modulo “m“.
a ≡ b (mod m)
This means that if “a“ is not divisible entirely by “m”, then “b“ is the remainder of dividing “a“ by “m“. Two integers “a“ and “b“ are comparable modulo the positive integer “m“ if, when divided by “m“, they give the same residuals.
Take a prime integer and denote it by “b”. The set of integers in the interval (1,2,3, ... b-1) is denoted by “B“. If this set is written in the form of a column, in ascending order from bottom to top, we obtain a column matrix. All numbers in this column are arranged one after another, their number is “b - 1“. Denote this column by the number “1“. Each number from the set “B“ will be squared and divided by “b“ with the remainder. The residues resulting from the division are written in the column. Denote this column by the number “2“ and place it to the right of the column number “1“. It is necessary to arrange the residues so that they correspond to the numbers squared, and are on the same line with them. After that, we raise each number from the set “B“ to the third power and divide by “b“ with the remainder. From the obtained residues we form a column with the number “3“, by analogy with column number “2“. Then, by analogy, we raise to the next degree and find the remainder of the division by “b“. We perform the actions until the exponent to which we construct the numbers from the set “B“ is less than “b“. As a result, we obtain a square matrix of size (b-1) x (b-1).
An example of such a square matrix for a prime integer “b = 23“ is presented in Fig. 1.
Fig. 1 The matrix of residuals of a prime integer b = 23.
The resulting matrix has amazing properties:
- It can be clearly seen that the last column of the matrix consists of one units. This is fully consistent with Fermat's simplicity test. A n-1 ≡ 1 (mod N) [5].
- It should be noted that the column with the number (b-1) / 2 (“b“ minus 1 divided by 2) consists of only two values of the set “B“. These are values 1 and (b-1).
- The values of the numbers, the sets “B“, in the columns, are symmetrical about the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2.
- Types of symmetry for different columns are different.
- For columns with even numbers, the values are equidistant from the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2 coincide. For the matrix shown in Fig. 1, the remainder of 11 squared divided by 23 and the remainder of 12 squared divided by 23 are equal and equal to 6.
- For columns with odd numbers, values equidistant from the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2, in total, are always equal to “b“. For the matrix shown in Fig. 1, the remainder of 11 in the third degree, divided by 23, is 20, the remainder of 12 in the third degree, divided by 23, is 3. In total, these two residues are 23, i.e. equal to “b“.
All the properties described above and considered for the matrix shown in Fig. 1, are inherent in matrices constructed according to the same rules for other prime integers.
3. Matrix of residuals of a composite number
The matrix considered in Section 2 characterizes the symmetry of primes. For composite numbers, a matrix constructed by the same rules is significantly different. It inherits the properties of a prime matrix, but it also acquires new properties. Consider a compound number, which is the product of two primes “x“ and “y“. In the same way, the value of the number is denoted by “b“, and the set of all numbers, in the interval (1, b-1), is denoted by “B“. Consider the composite number “b = 35“, which is the result of multiplying the primes “x = 5“ and “y = 7“. We construct a matrix of residues of various degrees for the numerical interval (35-1). The matrix of residues is presented in Fig. 2
Fig. 2 Matrix of residues of a composite number b = 35.
Some properties are inherited from the matrix of residuals of a prime number. For example, the values of the numbers present in the columns are symmetrical about the middle of the values of the numerical interval, i.e. values of (b-1) / 2 and (b + 1) / 2.
The matrix shown in fig. 2, carries new properties:
- The values of the rows of the matrix, in which in the first column there are multiples of the divisors of a composite number, take numerical values that are multiples of the divisors of a composite number and never equal 1. For example, in the matrix of Fig. 2, row 5, in the second column, has the value 25, in the third 20, in the fourth 30 and so on. All these values are a multiple of 5.
- If we exclude rows whose values are multiples of the divisors of the number “b“, then there are sure to be two columns in which the remaining values are 1. For example, in fig. 2 are the columns with numbers 12, 24.
- Of these two selected columns, the largest column number is the product of (x-1) by (y-1). Those. if from each of the factors subtract 1 and multiply them, we get the number of the largest selected column. For the matrix in Fig. 2 factors of the number “b” are 5 and 7. If you subtract 1 from each of them and multiply, we get (5-1) x (7-1) = 24. This is exactly the number of the largest selected column. It should be noted that in this case, the column number is equal to the Euler function, whose value is (x-1) x (y-1) = = (n). [6].
- Four values equal to 1 are necessarily present in the second column. For the matrix of residuals of a prime number and values of the set “B” equal to (1, b-1), the values in the second column take the value 1. For the matrix of residuals of a composite number, there are two more numbers sets “B“, when squared and dividing by “b“, the remainder is 1. In Fig. 2 are numbers 6 and 29.
- There are always pairs of numbers, the sets “B“, following each other, the values of which are multiples of the divisors “x“ and “y“ of the number “b”. For the matrix in Fig. 2 are pairs (14, 15) and (20, 21).
All the properties described above and considered for the matrix shown in Fig. 2, are inherent in matrices constructed according to the same rules for other composite integers.
4. Factorization of numbers
If we consider the RSA public key encryption method [4], then its use is based on the existence of mutually opposite mappings in the residual matrix of a composite number. If we take the composite number “b“, in its residual matrix there are always two columns “c“ and “d“ for which the following conditions are satisfied:
(b1 ** c) ≡ c1 (mod b); (c1 ** d) ≡ d1 (mod b); b1 = d1
where b1, c1, d1 are the numerical values in columns 1, c, d.
That is, for the composite number “b“ there are always two numbers “c“, “d“ from the range (1, b-1) for which the sequence of actions is true:
- Determine the remainder of any number “b1“, from the range (1, b -1) raised to the power of “c“ and divided by “b“. Denote this remainder by “c1“.
- Raise the resulting remainder “c1“ to the power of “d“ and divide by “b“ with the remainder. Denote this remainder by “d1“.
- The resulting remainder “d1“ is always equal to “b1“.
For the RSA encryption algorithm, (c, b) is the public key, (d, b) is the secret key.
Fig. 3 The matrix of residuals of the composite number b = 33.
Consider the matrix of residuals of the number b = 33, Fig. 3. For this number, c = 3, d = 7. Take any number from the first column, for example 8 and raise it to 3 degrees, the remainder is 17. The number 17 is raised to the power of 7, the remainder is 8, i.e. this remainder is equal to the original number from the first column.
RSA is one of the common public key encryption algorithms. Along with the improvement of encryption methods, methods for decrypting secret messages are improving.
Often they try to solve the decryption task for RSA forehead, i.e. Find the divisors of the base compound number. These methods are called factorization of numbers. In addition to simple enumeration of values and verification of numbers, they use the quadratic sieve method.
The basis of this method is that part of the residuals from squaring and dividing by the number “b” are the full squares of the numbers. In fig. 2 full squares are the quadratic remainders of the numbers (11, 12, 17) from the first column. To find the divisors of the number “b“, it is necessary to extract the square root from the quadratic remainder. The result, i.e. square root, subtract from the number “b“ or add to the number “b“. Multiples of the divisors of b will be obtained. Using the Euclidean algorithm, one can find the divisors of the number “b“.
In fig. 2, for the number 11, the quadratic remainder is 16. We extract the square root from 16, it is 4. To 11 we add 4, we get 15, the number is a multiple of the divisor 5. From 11 we subtract 4, we get 7, the number is equal to the divisor 7.
One of the most modern methods of factorization of numbers, is the sieve method of a number field [7]. This method allows you to reduce the number of checked values and reduce the time of calculations. Using the sieve method of the numerical field and the properties of the matrix of residuals of a composite number, one can achieve even more significant results.
For experimental verification of the methods of factorization of numbers, one can use the so-called Mersenne numbers [8]. These numbers represent a number 2 to the power of “n“, minus 1, where “n“ is a natural number. Only a limited number of Mersenne numbers are prime; the rest are decomposed into a finite number of divisors.
As illustrative example, one of the dividers, the number 2 to the power 4099, minus 1 equals -
431654595928296534254101974033397155588925169723783332084380283993261
209600632883153055473166663136594966053411838575253500155337120152873
781979635198920643526624304319945635699208877607737201529464080041890
547345467573782661041054825447947267620282789541695832747170633177331
920343746996221855049648583763367504662477325712779883313257418325242
923223374882540094860518718525171060169694349915604794431233943848839
032331927197514745282594881581533286782002526616104836932259305133211
436643050243706215479754994805351437606942854754835739144357537526269
041212016993538655106720507482318994547865735219931202814880677303379
021540170667630675512896640229254326407201860556265718380698467494757
374722667518146123812589844575734597771351069823560862537030159862538
798769879690913001816439118925869829536250846639469310212937581855933
518710668619729641309263324784218037304674615635505157625365285797298
443305108038716358762651248086440048468372406494047491988831492829285
161751678332086837187972136968851829414833128243888620308340321378185
123642015152620056914762030047166652837911735649104226834442937368573
819974224203735488718107356908123314371578553175076071717675764345142
549580867720367836084289513946899287311856029114297
4. References
[1] R Elliott, P. Dober "Symmetry in Physics Vol. 1", MIR Publisher, 1983
[2] "Schrödinger equation", ru.wikipedia.org/wiki/Уравнение_Шредингера.
[3] P.S. Aleksandrov “Introduction to group theory”, Moscow SCIENCE, GRFML, 1980
[4] “RSA“, en.wikipedia.org/wiki/RSA.
[5] “Farm Test”, en.wikipedia.org/wiki/Test_Farm.
[6] “Euler Function”, http://ru.wikipedia.org/wiki/ Euler Function.
[7] “General Method for Sifting a Number Field”, en.wikipedia.org/wiki/General_Numeric_field_grid_method.
[8] “Mersenne Numbers," http://ru.wikipedia.org/wiki/Mersenna_Numbers.
1. Introduction
In our world, everything is interconnected, similar to each other, has the same or similar parameters. Often these properties are called symmetry. In the Brief Oxford Dictionary, symmetry is defined as "Beauty, due to the proportionality of parts of the body or any whole, balance, similarity, harmony, coherence." [1] Very often, symmetry manifests itself in mathematics and physics. In physics, the symmetry properties are clearly manifested in quantum mechanics and its mathematical apparatus, for example, the Schrödinger equation [2]. In mathematics, there is a special mathematical apparatus that operates with the concepts of similarity and symmetry. This mathematical apparatus is called group theory [3]. One of the practical applications of symmetry in mathematics is public key encryption “RSA” [4].
2. The matrix of residual primes
Consider the definition of residue and comparison modulo. Here is the definition given in the modern explanatory dictionary. The number “a“ is called the residue of the number “b“ modulo “m“, if the difference “a - b“ is divided by “m“ (a, b, m> 0 are integers). That is, “a“ is comparable to “b“ modulo “m“.
a ≡ b (mod m)
This means that if “a“ is not divisible entirely by “m”, then “b“ is the remainder of dividing “a“ by “m“. Two integers “a“ and “b“ are comparable modulo the positive integer “m“ if, when divided by “m“, they give the same residuals.
Take a prime integer and denote it by “b”. The set of integers in the interval (1,2,3, ... b-1) is denoted by “B“. If this set is written in the form of a column, in ascending order from bottom to top, we obtain a column matrix. All numbers in this column are arranged one after another, their number is “b - 1“. Denote this column by the number “1“. Each number from the set “B“ will be squared and divided by “b“ with the remainder. The residues resulting from the division are written in the column. Denote this column by the number “2“ and place it to the right of the column number “1“. It is necessary to arrange the residues so that they correspond to the numbers squared, and are on the same line with them. After that, we raise each number from the set “B“ to the third power and divide by “b“ with the remainder. From the obtained residues we form a column with the number “3“, by analogy with column number “2“. Then, by analogy, we raise to the next degree and find the remainder of the division by “b“. We perform the actions until the exponent to which we construct the numbers from the set “B“ is less than “b“. As a result, we obtain a square matrix of size (b-1) x (b-1).
An example of such a square matrix for a prime integer “b = 23“ is presented in Fig. 1.
Fig. 1 The matrix of residuals of a prime integer b = 23.
The resulting matrix has amazing properties:
- It can be clearly seen that the last column of the matrix consists of one units. This is fully consistent with Fermat's simplicity test. A n-1 ≡ 1 (mod N) [5].
- It should be noted that the column with the number (b-1) / 2 (“b“ minus 1 divided by 2) consists of only two values of the set “B“. These are values 1 and (b-1).
- The values of the numbers, the sets “B“, in the columns, are symmetrical about the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2.
- Types of symmetry for different columns are different.
- For columns with even numbers, the values are equidistant from the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2 coincide. For the matrix shown in Fig. 1, the remainder of 11 squared divided by 23 and the remainder of 12 squared divided by 23 are equal and equal to 6.
- For columns with odd numbers, values equidistant from the middle of the interval, i.e. pairs of values (b-1) / 2 and (b + 1) / 2, in total, are always equal to “b“. For the matrix shown in Fig. 1, the remainder of 11 in the third degree, divided by 23, is 20, the remainder of 12 in the third degree, divided by 23, is 3. In total, these two residues are 23, i.e. equal to “b“.
All the properties described above and considered for the matrix shown in Fig. 1, are inherent in matrices constructed according to the same rules for other prime integers.
3. Matrix of residuals of a composite number
The matrix considered in Section 2 characterizes the symmetry of primes. For composite numbers, a matrix constructed by the same rules is significantly different. It inherits the properties of a prime matrix, but it also acquires new properties. Consider a compound number, which is the product of two primes “x“ and “y“. In the same way, the value of the number is denoted by “b“, and the set of all numbers, in the interval (1, b-1), is denoted by “B“. Consider the composite number “b = 35“, which is the result of multiplying the primes “x = 5“ and “y = 7“. We construct a matrix of residues of various degrees for the numerical interval (35-1). The matrix of residues is presented in Fig. 2
Fig. 2 Matrix of residues of a composite number b = 35.
Some properties are inherited from the matrix of residuals of a prime number. For example, the values of the numbers present in the columns are symmetrical about the middle of the values of the numerical interval, i.e. values of (b-1) / 2 and (b + 1) / 2.
The matrix shown in fig. 2, carries new properties:
- The values of the rows of the matrix, in which in the first column there are multiples of the divisors of a composite number, take numerical values that are multiples of the divisors of a composite number and never equal 1. For example, in the matrix of Fig. 2, row 5, in the second column, has the value 25, in the third 20, in the fourth 30 and so on. All these values are a multiple of 5.
- If we exclude rows whose values are multiples of the divisors of the number “b“, then there are sure to be two columns in which the remaining values are 1. For example, in fig. 2 are the columns with numbers 12, 24.
- Of these two selected columns, the largest column number is the product of (x-1) by (y-1). Those. if from each of the factors subtract 1 and multiply them, we get the number of the largest selected column. For the matrix in Fig. 2 factors of the number “b” are 5 and 7. If you subtract 1 from each of them and multiply, we get (5-1) x (7-1) = 24. This is exactly the number of the largest selected column. It should be noted that in this case, the column number is equal to the Euler function, whose value is (x-1) x (y-1) = = (n). [6].
- Four values equal to 1 are necessarily present in the second column. For the matrix of residuals of a prime number and values of the set “B” equal to (1, b-1), the values in the second column take the value 1. For the matrix of residuals of a composite number, there are two more numbers sets “B“, when squared and dividing by “b“, the remainder is 1. In Fig. 2 are numbers 6 and 29.
- There are always pairs of numbers, the sets “B“, following each other, the values of which are multiples of the divisors “x“ and “y“ of the number “b”. For the matrix in Fig. 2 are pairs (14, 15) and (20, 21).
All the properties described above and considered for the matrix shown in Fig. 2, are inherent in matrices constructed according to the same rules for other composite integers.
4. Factorization of numbers
If we consider the RSA public key encryption method [4], then its use is based on the existence of mutually opposite mappings in the residual matrix of a composite number. If we take the composite number “b“, in its residual matrix there are always two columns “c“ and “d“ for which the following conditions are satisfied:
(b1 ** c) ≡ c1 (mod b); (c1 ** d) ≡ d1 (mod b); b1 = d1
where b1, c1, d1 are the numerical values in columns 1, c, d.
That is, for the composite number “b“ there are always two numbers “c“, “d“ from the range (1, b-1) for which the sequence of actions is true:
- Determine the remainder of any number “b1“, from the range (1, b -1) raised to the power of “c“ and divided by “b“. Denote this remainder by “c1“.
- Raise the resulting remainder “c1“ to the power of “d“ and divide by “b“ with the remainder. Denote this remainder by “d1“.
- The resulting remainder “d1“ is always equal to “b1“.
For the RSA encryption algorithm, (c, b) is the public key, (d, b) is the secret key.
Fig. 3 The matrix of residuals of the composite number b = 33.
Consider the matrix of residuals of the number b = 33, Fig. 3. For this number, c = 3, d = 7. Take any number from the first column, for example 8 and raise it to 3 degrees, the remainder is 17. The number 17 is raised to the power of 7, the remainder is 8, i.e. this remainder is equal to the original number from the first column.
RSA is one of the common public key encryption algorithms. Along with the improvement of encryption methods, methods for decrypting secret messages are improving.
Often they try to solve the decryption task for RSA forehead, i.e. Find the divisors of the base compound number. These methods are called factorization of numbers. In addition to simple enumeration of values and verification of numbers, they use the quadratic sieve method.
The basis of this method is that part of the residuals from squaring and dividing by the number “b” are the full squares of the numbers. In fig. 2 full squares are the quadratic remainders of the numbers (11, 12, 17) from the first column. To find the divisors of the number “b“, it is necessary to extract the square root from the quadratic remainder. The result, i.e. square root, subtract from the number “b“ or add to the number “b“. Multiples of the divisors of b will be obtained. Using the Euclidean algorithm, one can find the divisors of the number “b“.
In fig. 2, for the number 11, the quadratic remainder is 16. We extract the square root from 16, it is 4. To 11 we add 4, we get 15, the number is a multiple of the divisor 5. From 11 we subtract 4, we get 7, the number is equal to the divisor 7.
One of the most modern methods of factorization of numbers, is the sieve method of a number field [7]. This method allows you to reduce the number of checked values and reduce the time of calculations. Using the sieve method of the numerical field and the properties of the matrix of residuals of a composite number, one can achieve even more significant results.
For experimental verification of the methods of factorization of numbers, one can use the so-called Mersenne numbers [8]. These numbers represent a number 2 to the power of “n“, minus 1, where “n“ is a natural number. Only a limited number of Mersenne numbers are prime; the rest are decomposed into a finite number of divisors.
As illustrative example, one of the dividers, the number 2 to the power 4099, minus 1 equals -
431654595928296534254101974033397155588925169723783332084380283993261
209600632883153055473166663136594966053411838575253500155337120152873
781979635198920643526624304319945635699208877607737201529464080041890
547345467573782661041054825447947267620282789541695832747170633177331
920343746996221855049648583763367504662477325712779883313257418325242
923223374882540094860518718525171060169694349915604794431233943848839
032331927197514745282594881581533286782002526616104836932259305133211
436643050243706215479754994805351437606942854754835739144357537526269
041212016993538655106720507482318994547865735219931202814880677303379
021540170667630675512896640229254326407201860556265718380698467494757
374722667518146123812589844575734597771351069823560862537030159862538
798769879690913001816439118925869829536250846639469310212937581855933
518710668619729641309263324784218037304674615635505157625365285797298
443305108038716358762651248086440048468372406494047491988831492829285
161751678332086837187972136968851829414833128243888620308340321378185
123642015152620056914762030047166652837911735649104226834442937368573
819974224203735488718107356908123314371578553175076071717675764345142
549580867720367836084289513946899287311856029114297
4. References
[1] R Elliott, P. Dober "Symmetry in Physics Vol. 1", MIR Publisher, 1983
[2] "Schrödinger equation", ru.wikipedia.org/wiki/Уравнение_Шредингера.
[3] P.S. Aleksandrov “Introduction to group theory”, Moscow SCIENCE, GRFML, 1980
[4] “RSA“, en.wikipedia.org/wiki/RSA.
[5] “Farm Test”, en.wikipedia.org/wiki/Test_Farm.
[6] “Euler Function”, http://ru.wikipedia.org/wiki/ Euler Function.
[7] “General Method for Sifting a Number Field”, en.wikipedia.org/wiki/General_Numeric_field_grid_method.
[8] “Mersenne Numbers," http://ru.wikipedia.org/wiki/Mersenna_Numbers.