CN115514488A - Big integer decomposition problem mapping method and system based on Itanium model - Google Patents

Abstract

The invention provides a big integer decomposition problem mapping method and a system based on an Exin model, comprising the following steps: carrying out formal equivalent replacement on the loss function obtained by each block to meet the formal requirements of the Esinon model, and obtaining a Hamiltonian expression of the Esinon model; according to the values of Hamiltonian under different spinning states and the distribution characteristics of the range of the Hamiltonian, the Hamiltonian can jump out of a local optimal solution until an Esino model reaches a spinning ground state; the method comprises the steps of obtaining two prime factor information, realizing large integer decomposition, further obtaining a private key in an RSA encryption algorithm through an Euler formula and an open public key in a cryptosystem, converting ciphertext information into original plaintext information by using the private key, and realizing the cracking of the RSA cryptosystem. The invention completely expresses a general flow for mapping a large integer decomposition problem into an Esinon model solving problem.

Description

Mapping Method and System for Large Integer Decomposition Problem Based on Ising Model

technical field

The present invention relates to the technical field of password cracking, in particular, to the technical field of RSA password cracking based on large integer decomposition, and more specifically, to a large integer decomposition problem mapping method and system based on the Ising model.

Background technique

Although the computing power of the current computer can easily calculate the product of any two finite large integers, its reverse process is still extremely difficult, and it is difficult to accurately calculate the factor of a large integer within a limited time. Therefore, the difficulty of large integer decomposition is widely used in the field of encryption, especially an asymmetric encryption algorithm jointly proposed by Ron Rivest, Adi Shamir and Leonard Adleman in 1977, referred to as the RSA algorithm, the security of this encryption algorithm It is realized by relying on the difficulty of decomposing the product of two large prime numbers. Although it is extremely difficult to crack the RSA algorithm in theory, many researchers have been exploring ways to effectively realize the decomposition of large integers, which is related to the improvement and update of today's cryptographic systems and even information security. Trial division is the earliest recorded integer decomposition method, but for large integers used in cryptographic systems, the time required for trial division far exceeds the validity period of general ciphers. Number field sieve method (NFS) is currently the best method for decomposing larger integers, but its process is cumbersome, including five steps of polynomial selection, number pair screening, matrix generation, matrix solution, and square root solution, and has certain randomness . In addition, quantum algorithms have appeared in recent years to decompose integers. However, due to the current inability to achieve stable control of a large number of qubits, the practical application of quantum algorithms still has a long way to go.

The Ising model was originally a physical model describing the ferromagnetism of matter. Now it has developed into a mathematical calculation model with many application scenarios. It contains many spin nodes with spin states of "+1" or "-1". In this model, there are two-body interactions between spin nodes and the action of an external magnetic field, thereby changing the spin state of the spin nodes. Based on this characteristic, the Hamiltonian of the Ising model system will gradually decrease until it reaches the ground state . The Ising model is an effective method to solve combinatorial optimization problems. It can transform the problem parameters into interaction strength and external magnetic field strength, and then use the Ising model to obtain the optimal solution. At present, many Ising models that represent spin nodes by physical signals (such as electrical signals or optical signals) have been proposed, which have the characteristics of fast calculation speed and low energy consumption. Although there have been reports of converting large integer factorization problems into Ising models, the existing methods only have mathematical derivations and have not formed a general program flow, and it is necessary to convert many-body interactions into two-body interactions. At the same time, for the conversion of larger integers, there are also problems such as excessive model coefficients and high precision requirements. In addition, after transforming the large integer decomposition problem into the Ising model, the characteristics of the model were not further analyzed, and no targeted improvement was made to the iterative process.

Patent document CN101814109A (application number: CN200910078286.4) discloses a method for decomposing large integers based on DNA self-assembly calculations. The method includes the following steps: constructing a logical operation framework for decomposing integers based on DNA self-assembly technology; forming an initial Calculation of TILE, including initial TILE, calculation of TILE and data transfer TILE; under the pre-set experimental conditions, control the temperature and concentration of the solution to ensure the smooth completion of DNA self-assembly; solution detection, to find out the complete self-assembly structure, separate and extract the reporting chain within it, and read the results according to the coding principles. However, this invention does not introduce a specific calculation model, and does not construct a loss function that only contains quadratic terms, primary terms, and constant terms.

Contents of the invention

In view of the defects in the prior art, the object of the present invention is to provide a large integer decomposition problem mapping method and system based on the Ising model.

According to a kind of Ising model-based large integer decomposition problem mapping method provided by the present invention, comprising:

Step S1: Introduce auxiliary variables to each intermediate term in the binary multiplication vertical formula, construct auxiliary blocks, and perform formal equivalent replacement on the loss function obtained by each block to make it meet the formal requirements of the Ising model. The loss function of the block is added and replaced by variables, and the Hamiltonian expression of the Ising model is obtained by simplification;

Step S2: According to the distribution characteristics of the value of the Hamiltonian in different spin states and its range, adopt a technical solution to update the spin state from less to more, and change the discriminant conditions under certain circumstances so that it can jump out of the local Optimal solution until the Ising model reaches the spin ground state;

Step S3: Obtain two prime factor information, realize large integer decomposition, and further obtain the private key in the RSA encryption algorithm from the Euler formula and the open public key in the cryptographic system, and use the private key to convert the ciphertext information into the original plaintext information, Realize the cracking of the RSA cryptosystem.

Preferably, in the step S1:

A loss function of a specific form is generated for each auxiliary block, substituted into the boundary conditions, and a formal equivalent replacement is performed for each loss function so that it does not contain high-order terms above the quadratic term, which meets the formal requirements of the Ising model , and then add all the loss functions, replace variables, and simplify to obtain the Hamiltonian expression of the Ising model, extract the interaction matrix J and the external magnetic field vector h, and transform the large integer decomposition problem into finding the Ising model The problem of solving the spin ground state of the symplectic model;

The conversion process is realized through a fixed process, applicable to any large integer, programmed in the computer, for a specific large integer, no separate analysis or derivation of the intermediate process is required, and the corresponding Ising model can be directly obtained;

The auxiliary variables are introduced one by one according to each intermediate term a _i b _j in the vertical formula of binary multiplication of two factors, namely y _i,j and z _i,j , wherein y _i,j is the The lowest bit result obtained by adding the binary variables of , z _i,j is the carry obtained by adding the binary variables in the right auxiliary block, a _i b _j , y _i,j , z _i,j constitute an auxiliary block , generating a loss function;

The form of the loss function is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , the equivalent replacement The latter form is

The loss function after the equivalent replacement described above does not contain more than two terms, and does not need to reduce the order, and in the Hamiltonian expression obtained after adding all of them, simplifying, and variable substitution, the coefficient of the variable is determined by Restricted within the preset range, the obtained Ising model interaction matrix J and the element size of the external magnetic field vector h are also within a limited range.

Preferably, step S1.1: express the target large integer to be decomposed in binary form, and record the number of digits as w;

Step S1.2: Assume that the binary digits of the two factors of the target large integer are k and h respectively, and the binary forms from high to low are a ₁ , a ₂ ,..., a _k and b ₁ , b ₂ ,..., b _h ;

Step S1.3: For each intermediate term a _i b _j in the binary multiplication vertical formula of two factors, introduce auxiliary variables y _i,j and z _i,j one by one, and set a _i b _j , y _i,j , z _{i, j} three items as an auxiliary block;

Step S1.4: Generate a loss function for each auxiliary block. For the auxiliary block on the boundary, introduce additional auxiliary variables according to the form of the loss function and substitute them into the boundary conditions;

Step S1.5: Perform a formal equivalent replacement on the loss function obtained for each block, so that it only contains quadratic terms;

Step S1.6: Add the replaced loss functions and perform variable substitution, and then simplify to obtain the Hamiltonian expression of the Ising model;

Step S1.7: Each variable in the expression is used as a spin node, and the binary quadratic coefficient and the first-order coefficient are respectively extracted to form the interaction matrix J and the external magnetic field vector h of the Ising model, and the remaining invariant parts are The sum is denoted as C.

Preferably, in the step S2:

Step S2.1: Randomly generate the initial spin state, and calculate the Hamiltonian according to the obtained Ising model;

Step S2.2: change x spins each time, the initial value of x is 1, and gradually increase x as the number of changes of the same spin state increases;

Step S2.3: If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change;

Step S2.4: If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset;

Step S2.5: Repeat step S2.2-step S2.4 of the process until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two primes of the target large integer If factor information is used, large integer decomposition is realized.

Preferably, the lowering criterion for accepting the change of the spin state, by setting a discrimination energy E_jump required to jump out of the local optimal solution, the Hamiltonian corresponding to the current spin state is no longer calculated, and It is to directly set it as E_jump, and then repeat the iterative process until the Hamiltonian is updated again.

Preferably, module M1: introduce auxiliary variables for each intermediate term in the binary multiplication vertical formula, construct auxiliary blocks, and perform a formal equivalent replacement of the loss function obtained by each block, so that it meets the formal requirements of the Ising model , add the loss function of each block to get the Hamiltonian expression of the Ising model;

Module M2: According to the distribution characteristics of the value of the Hamiltonian in different spin states and its range, adopt a technical solution to update the spin state from less to more, and change the judgment conditions so that it can jump out of the local optimal solution, Until the Ising model reaches the spin ground state;

Module M3: Obtain two prime factor information, realize large integer decomposition, and further obtain the private key in the RSA encryption algorithm from the Euler formula and the open public key in the cryptographic system, and use the private key to convert the ciphertext information into the original plaintext information, Realize the cracking of the RSA cryptosystem.

Preferably, in said module M1:

A loss function of a specific form is generated for each auxiliary block, substituted into the boundary conditions, and a formal equivalent replacement is performed for each loss function so that it does not contain high-order terms above the quadratic term, which meets the formal requirements of the Ising model , and then add all the loss functions, replace variables, and simplify to obtain the Hamiltonian expression of the Ising model, extract the interaction matrix J and the external magnetic field vector h, and transform the large integer decomposition problem into finding the Ising model The problem of solving the spin ground state of the symplectic model;

The conversion process is realized through a fixed process, applicable to any large integer, programmed in the computer, for a specific large integer, no separate analysis or derivation of the intermediate process is required, and the corresponding Ising model can be directly obtained;

The auxiliary variables are introduced one by one according to each intermediate term a _i b _j in the vertical formula of binary multiplication of two factors, namely y _i,j and z _i,j , wherein y _i,j is the The lowest bit result obtained by adding the binary variables of , z _i,j is the carry obtained by adding the binary variables in the right auxiliary block, a _i b _j , y _i,j , z _i,j constitute an auxiliary block , generating a loss function;

The form of the loss function is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , the equivalent replacement The latter form is

The loss function after the equivalent replacement described above does not contain more than two terms, and does not need to reduce the order, and in the Hamiltonian expression obtained after adding all of them, simplifying, and variable substitution, the coefficient of the variable is determined by Restricted within the preset range, the obtained Ising model interaction matrix J and the element size of the external magnetic field vector h are also within a limited range.

Preferably, module M1.1: express the target large integer to be decomposed in binary form, and record the number of digits as w;

Module M1.2: Assume that the binary digits of the two factors of the target large integer are k and h respectively, and the binary forms from high to low are a ₁ , a ₂ ,…,a _k and b ₁ ,b ₂ ,…, b _h ;

Module M1.3: For each intermediate term a _i b _j in the vertical form of binary multiplication of two factors, introduce auxiliary variables y _i,j and z _i,j one by one, and set a _i b _j , y _i,j , z _{i, j} three items as an auxiliary block;

Module M1.4: Each auxiliary block generates a loss function. For auxiliary blocks on the boundary, additional auxiliary variables are introduced according to the form of the loss function and substituted into the boundary conditions;

Module M1.5: Perform a formal equivalent replacement of the loss function obtained by each block so that it only contains quadratic terms;

Module M1.6: Add the replaced loss functions and perform variable substitution, and then simplify to obtain the Hamiltonian expression of the Ising model;

Module M1.7: Each variable in the expression is used as a spin node, and the binary quadratic coefficient and the first-order coefficient are respectively extracted to form the interaction matrix J and the external magnetic field vector h of the Ising model, and the remaining invariant parts are The sum is denoted as C.

Preferably, in said module M2:

Module M2.1: Randomly generate the initial spin state, and calculate the Hamiltonian according to the obtained Ising model;

Module M2.2: Each time x spins are changed, the initial value of x is 1, and as the number of changes of the same spin state increases, x gradually increases;

Module M2.3: If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change;

Module M2.4: If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset;

Module M2.5: Repeat the process module M2.2-module M2.4 until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two primes of the target large integer If factor information is used, large integer decomposition is realized.

Preferably, the lowering criterion for accepting the change of the spin state, by setting a discrimination energy E_jump required to jump out of the local optimal solution, the Hamiltonian corresponding to the current spin state is no longer calculated, and It is to directly set it as E_jump, and then repeat the iterative process until the Hamiltonian is updated again.

Compared with the prior art, the present invention has the following beneficial effects:

1. The present invention completely represents a general process for mapping the large integer decomposition problem to the Ising model solution problem;

2. Compared with other large integer decomposition methods, the present invention introduces a specific calculation model. The decomposition process only includes the above two main parts, which is generally simpler and more intuitive. The conversion process of the first part is directly applicable to any target large integer. Versatility, can be directly programmed in the computer, the calculation and iteration process of the second part can be completed on the general computing equipment, and can also be realized on the special computing platform, with a wider hardware implementation scenario;

3. Compared with other examples of using the Ising model to solve the decomposition problem of large integers, the present invention directly constructs a loss function containing only quadratic terms, primary terms and constant terms, avoiding the order reduction operation, and for any large integer, The value of the interaction between the converted Ising model and the external magnetic field is limited within a limited range, making its physical realization and operation easier;

3. The present invention further improves the general iterative process for the obtained Ising model, can find or approach the optimal solution faster, avoid falling into the local optimal solution, and improve the efficiency of large integer decomposition;

4. At present, with the development of special computing equipment related to the Ising model, it is expected to use the method of the present invention to achieve a breakthrough in the decomposition and recording of large integers, thereby promoting the development of cryptography, information security and other fields.

Description of drawings

Other characteristics, objects and advantages of the present invention will become more apparent by reading the detailed description of non-limiting embodiments made with reference to the following drawings:

Fig. 1 is the overall flowchart of the large integer decomposition problem mapping method provided by the present invention;

Fig. 2 is the method flowchart that large integer decomposition problem is converted into Ising model solving problem among the present invention;

Fig. 3 is the schematic diagram of the principle of constructing auxiliary blocks in the binary multiplication vertical formula of the embodiment of the present invention;

Fig. 4 is the flow chart of the method for iteratively finding the spin ground state to the Ising model in the present invention;

FIG. 5 is an example diagram of an iteration result of an embodiment of the present invention.

detailed description

The present invention will be described in detail below in conjunction with specific embodiments. The following examples will help those skilled in the art to further understand the present invention, but do not limit the present invention in any form. It should be noted that those skilled in the art can make several changes and improvements without departing from the concept of the present invention. These all belong to the protection scope of the present invention.

Example 1:

The present invention introduces a new calculation model to realize the mapping of large integer decomposition problems. The overall process is simple and intuitive, and the iterative process can be realized on general-purpose computing equipment or on a dedicated computing platform for the Ising model, which enriches the problem of solving large integers. Method ideas and implementation scenarios for decomposing problems.

A large integer decomposition problem mapping method based on the Ising model, as shown in Figure 1-Figure 5, introduces auxiliary variables into the vertical formula of binary multiplication of prime factors, and constructs auxiliary blocks one by one with intermediate terms, for each The auxiliary block generates a loss function of a specific form, substitutes it into the boundary conditions, and performs a formal equivalent replacement for each loss function, so that it does not contain high-order terms above the quadratic term and meets the formal requirements of the Ising model. Adding all loss functions, variable substitution, and simplification, the Hamiltonian expression of the Ising model is obtained, and the interaction matrix J and the external magnetic field vector h are extracted. The problem of large integer decomposition is transformed into finding the spin of the Ising model The problem of solving the ground state; then iteratively finds the spin ground state of the Ising model, adopts an iterative strategy of changing the current spin state from less to more, and updates the spin state if the changed Hamiltonian decreases, and at the same time Under certain conditions, the discriminant conditions are changed so that it can jump out of the local optimal solution until the Ising model reaches the spin ground state.

The conversion process described above is realized through a fixed process, which is applicable to any large integer and can be programmed in the computer. For a specific large integer, the corresponding Ising model can be directly obtained without separate analysis or derivation of the intermediate process .

The auxiliary variables are introduced one by one according to each intermediate term a _i b _j in the vertical formula of binary multiplication of two factors, namely y _i,j and z _i,j , wherein y _i,j is the The lowest bit result obtained by adding the binary variables of , z _i,j is the carry obtained by adding the binary variables in the right auxiliary block, a _i b _j , y _i,j , z _i,j constitute an auxiliary block , resulting in a loss function.

The form of the loss function is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , the equivalent replacement The latter form is

The loss function after the equivalent replacement described above does not contain more than two terms, and does not need to reduce the order, and in the Hamiltonian expression obtained after adding all of them, simplifying, and variable substitution, the coefficient of the variable is determined by It is limited in a certain range, so the element sizes of the interaction matrix J and the external magnetic field vector h of the obtained Ising model are also limited in range.

The Ising model described above is suitable for a specific iteration strategy, which can reach the ground state faster and avoid falling into a local optimal solution than a completely random iteration.

The specific process of the iterative strategy is:

1) The initial spin state is randomly generated, and the Hamiltonian is calculated according to the Ising model obtained in the first part;

2) Each time x spins are changed, the initial value of x is 1, and as the number of changes of the same spin state increases, x gradually increases;

3) If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change;

4) If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset;

5) Repeat process 2) to 4) until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two prime factor information of the target large integer, and the large integer break down.

The described criteria for reducing the acceptance of spin state changes, by setting a discriminant energy E_jump required to jump out of the local optimal solution, the Hamiltonian corresponding to the current spin state is no longer calculated, but its Set directly to E_jump, and then repeat the iterative process until the Hamiltonian is updated again.

Further, the private key in the RSA encryption algorithm is obtained from the Euler formula and the open public key in the cryptographic system, and the private key is used to convert the ciphertext information into the original plaintext information to realize the cracking of the RSA cryptographic system.

Example 2:

Embodiment 2 is a preferred example of Embodiment 1 to describe the present invention more specifically.

The purpose of the present invention is to propose a new technical scheme that decomposes a large integer into two prime factors, realizes the mapping of the large integer decomposition problem to the Ising model solving problem, and forms a relatively simple but complete solution process, thereby enabling general-purpose computing equipment (such as Electronic computer, etc.) and various special computing devices for the Ising model (such as optical Ising machines, etc.) can be directly applied to solve the problem of large integer decomposition, and then realize the cracking of the RSA encryption algorithm.

The present invention can be divided into two parts according to the sequence, wherein the first part is the conversion process from the large integer decomposition problem to the target Ising model. block, and replace the loss function obtained by each block with a formal equivalent to make it meet the formal requirements of the Ising model, and finally add the loss functions of each block and make a variable substitution, and simplify to obtain the Hamiltonian expression. The second part is to design a suitable iterative process for the obtained Ising model, according to the distribution characteristics of the value and range of the Hamiltonian in different spin states, adopt the technique of updating the spin state from less to more The above iterative process can make the Ising model find or approach the spin ground state faster.

The conversion of the large integer decomposition problem to the target Ising model, the implementation process is as follows:

1) Express the target large integer to be decomposed in binary form, and record the number of digits as w;

2) Assume that the binary digits of the two factors of the target large integer are k and h respectively, and the binary forms from high to low are a ₁ , a ₂ ,..., a _k and b ₁ , b ₂ ,..., b _h ;

3) For each intermediate term a _i b _j in the binary multiplication vertical formula of two factors, introduce auxiliary variables y _i,j and z _i,j one by one, and a _i b _j , y _i,j , z _{i , three items of j} are used as an auxiliary block;

4) Each auxiliary block generates a loss function. For auxiliary blocks on the boundary, additional auxiliary variables are introduced according to the form of the loss function and substituted into the boundary conditions;

5) Perform a formal equivalent replacement of the loss function obtained for each block so that it only contains quadratic terms;

6) Add the loss functions after each replacement and perform variable substitution, and then simplify to obtain the Hamiltonian expression of the Ising model;

7) Each variable in the expression is used as a spin node, and the binary quadratic coefficient and the first-order coefficient are respectively extracted to form the interaction matrix J and the external magnetic field vector h of the Ising model, and the sum of the remaining invariant parts is recorded as for C.

The implementation process of the iterative process designed for the obtained Ising model is:

1) The initial spin state is randomly generated, and the Hamiltonian is calculated according to the Ising model obtained in the first part;

2) Each time x spins are changed, the initial value of x is 1, and as the number of changes of the same spin state increases, x gradually increases;

3) If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change;

4) If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset;

5) Repeat process 2) to 4) until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two prime factor information of the target large integer, and the large integer break down.

The present invention proposes a new technical solution for decomposing a large integer into two prime factors. After obtaining the two prime factors, the two prime factors can be further substituted into Euler's formula, and combined with the open public key to obtain the private key in the RSA encryption algorithm. Key information, and then use the private key to convert the transmitted ciphertext information into plaintext information, which is the encrypted original data, so far to realize the cracking of the RSA cryptosystem.

Example 3:

Embodiment 3 is a preferred example of Embodiment 1 to describe the present invention more specifically.

As shown in Figure 1, the present invention realizes the mapping from the large integer decomposition problem to the Ising model solution problem, and provides a complete set of solution process, the main idea is to obtain the corresponding Ising model through the determined program steps The model, and then iteratively obtain the spin ground state of the model through the computing platform, and obtain the two prime factors of the target large integer. In the first part, the interaction matrix J and the external magnetic field vector h are obtained from the target large integer, which is mainly based on the loss function determined by the multiplication vertical formula. If the loss function reaches 0, it means that the value of the variable at this time is exactly two After the prime factors to be sought are transformed into the Ising model, this state is also the ground state of the model. The second part is the further optimization of the present invention after the Ising model is obtained in the first part, and an iterative strategy for finding the spin ground state of the Ising model is designed. The Ising model can approach or find the spin ground state faster and avoid falling into the local Optimal solution. It should be noted that the above-mentioned first part is a deterministic program flow, which can be programmed in the computer, and the Ising model obtained by converting the same large integer is fixed; while the process of the second part has certain randomness, but the model The optimal solution of is determined. The implementation of each part is described in detail below, assuming that the public modulus N in the RSA encryption algorithm is 143, so the decomposition of 143 is used as a specific example to supplement the explanation. It should be understood that the public modulus in the RSA algorithm of actual application is relatively large Larger, 143 is used as the public modulus here to facilitate the explanation of the method principle of the present invention. For integers with larger magnitudes, the principle and implementation steps are the same.

As shown in Figure 2, in the first part, first, the large integer to be decomposed is expressed in binary form, and its binary digit is recorded as w, and the binary digits of the two prime factors are determined to be k and h respectively, and the high digit to the low digit is set to a ₁ ,a ₂ ,…,a _k and b ₁ ,b ₂ ,…,b _h , where a ₁ ,a _k ,b ₁ ,b _h can be determined as a constant 1; in the binary multiplication vertical form of two prime factors Introduce auxiliary variables y _i,j and z _i,j , and use them together with the corresponding a _i b _j in the multiplication vertical formula as an auxiliary block; for each auxiliary block, a loss function F _i,j can be determined, whose The form is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , for the auxiliary block on the multiplicative vertical boundary , it is necessary to additionally generate the auxiliary variables required in the loss function but not introduced, and substitute the auxiliary variables in the loss function with non-auxiliary variables or known constants, that is, into the boundary conditions; for each loss function, formally Equivalent replacement, without changing the function variables, to get a new form of F _i,j , which does not include items higher than the second; add the various loss functions after replacement and perform variable substitution, so that the value of the variable is changed from binary The "1" and "0" of the spin state are changed to "+1" and "-1" representing the spin state, and then simplified to obtain the Hamiltonian expression that satisfies the conditions of the Ising model; finally, the variables in the expression are expressed as The spin state of the Ising model extracts the coefficients, in which the quadratic coefficients between different spins form the interaction matrix J, and each first-order coefficient forms the external magnetic field vector h, and the parts other than J and h in the expression are In the invariant part, the value has nothing to do with the spin state, and its value is recorded as C, which is used to judge whether the Ising model has reached the spin ground state in the second part.

Said determination of the binary digits of two prime factors, k and h satisfy k+h=w or k+h=w+1, and in general, the difference between the two prime factors of large integers that are actually applied is relatively small Small, the possibility of the same binary number is high, so the initial number of bits can be set as k=h=w/2 or k=h=(w+1)/2, if the correct result cannot be obtained, then the two prime The digits of the factors are adjusted; if there is additional digit information in the large integer decomposition problem, the binary digits of the two prime factors can be determined according to the additional information.

As shown in Figure 3, in the multiplication vertical formula of the described embodiment, an auxiliary block is constructed, for each intermediate term a _i b _j , auxiliary variables y _i,j and z _i,j are introduced, and a _i b _j , y _i,j , z _i,j are used as an auxiliary block, where y _i,j is the lowest bit result obtained by adding the binary variables in the upper auxiliary block, z _i,j is the binary variable in the right auxiliary block Carry from addition of variables. It should be noted that the multiplication vertical formula is listed here only to illustrate the principle of the present invention more clearly. When actually solving the problem of large integer decomposition, the large integer to be decomposed is directly substituted into the program flow shown in Figure 2. The converted Ising model can be obtained without listing the multiplicative vertical formula.

For the boundary conditions described above, if k+h=w is satisfied, it is assumed that the binary form of the target large integer is t ₁ , t ₂ ,...,t _w from the high bit to the low bit; if k+h=w+1 is satisfied, the target The highest bit t ₁ of a large integer is 0, and its actual binary form is respectively t ₂ ,…,t _w+1 from high bit to low bit, then there are the following boundary conditions: y _i,0 =t _i ; y _{k+1 ,j-1} =t _k+j ; y _i,h =0; z _i,h =0; z _k,j =0; y _1,h-1 =0; z _0,j =y _{1,j- 1} ; y _k+1,h =0.

The formal equivalent replacement of the loss function is carried out, and the form after the equivalent replacement is

As shown in Figure 4, in the second part, first set a discriminant energy E_jump required to jump out of the local optimal solution. The range of E_jump is determined by C, which is greater than -C but close to -C; the initial spin state is randomly generated, according to The Ising model obtained in the first part calculates the Hamiltonian in the initial spin state; set the number of spin state changes in each iteration as x, and the initial value as 1, and then start iteration; change x randomly in each iteration spin state, judge whether the Hamiltonian of the model is reduced after the change, if it is reduced, accept this change, update the spin state and the corresponding Hamiltonian, and reset x to 1, if not, then Enter the following judgment process:

Determine whether the value of x has not been reset after a certain number of iterations K(x), if not, proceed to the next iteration, if so, increase the value of x by 1, and then judge whether it is currently in a local optimal solution according to the value of x , set the judgment standard of the local optimal solution as a positive integer P, if x<P, it means that it is not in the local optimal solution, and proceed to the next iteration, if x≥P, it means that the current state is already in the local optimal solution, set x Decrease 1, and lower the criterion for updating the current spin state, so that the Hamiltonian corresponding to the current spin state is no longer calculated, but directly set it as E_jump, and then proceed to the next iteration.

Repeat the above iterative process until the Hamiltonian value of the current spin state is -C, indicating that the Ising model has reached the spin ground state at this time, and two prime factor information can be obtained to complete the large integer decomposition.

Said judgment whether to increase the number of iterations K(x) of x, K(x) is an exponential function with x as a variable, and its coefficient should be positively correlated with the number of spins of the Ising model.

The judgment standard P of the local optimal solution should keep a small value, specifically, take the logarithm with base 2 of the binary digits of the decomposed large integer, and the obtained value is the approximate value of P.

For functions or parameters such as E_jump, K(x), and P in the second part, the present invention only provides the standards and references for its definition or value, and its specific formula or value changes with the target large integer are different, and need to be fine-tuned according to the iteration results, but should not deviate from the definition or value range given by the present invention.

As shown in Figure 5, the number of spins of the Ising model obtained in the embodiment of the present invention is 24, and the C value is 44. It can be seen from the figure that after about 47893 iterations, the Hamiltonian is -44, and the Ising The model reaches the spin ground state, from which two prime factor information can be obtained, and the number of iterations 47893 is much smaller than the total number of spin states 2 ²⁴ , which shows that the iteration strategy is effective.

RSA加密算法中的私钥指数d与开放的公钥指数e满足

代入求出私钥指数d，再使用私钥将传输的密文信息S转换为明文信息M，转换公式为M≡S^dmod N，M即为被加密的原始数据，至此已完成对RSA密码系统的破解。The two prime factor information mentioned above can be obtained by looking at the spin state after the Ising model reaches the ground state. The first four ground state spin states in this embodiment are "+1, -1, -1, +1" or "-1, +1, +1, -1", from which it can be determined that the two prime factors are 11 and 13 respectively, and the spin after the fourth digit represents an auxiliary variable, which has no direct relationship with the value of the prime factor , after getting two prime factors, substitute them into Euler's formula to get

The private key exponent d in the RSA encryption algorithm and the open public key exponent e satisfy

Substitute into the private key index d, and then use the private key to convert the transmitted ciphertext information S into plaintext information M. The conversion formula is M≡S ^d mod N, and M is the encrypted original data. So far, the RSA encryption has been completed. System cracking.

Those skilled in the art know that, in addition to realizing the system, device and each module thereof provided by the present invention in a purely computer-readable program code mode, the system, device and each module thereof provided by the present invention can be completely programmed by logically programming the method steps. The same program is implemented in the form of logic gates, switches, application specific integrated circuits, programmable logic controllers, and embedded microcontrollers, among others. Therefore, the system, device and each module provided by the present invention can be regarded as a hardware component, and the modules included in it for realizing various programs can also be regarded as the structure in the hardware component; A module for realizing various functions can be regarded as either a software program realizing a method or a structure within a hardware component.

Specific embodiments of the present invention have been described above. It should be understood that the present invention is not limited to the specific embodiments described above, and those skilled in the art may make various changes or modifications within the scope of the claims, which do not affect the essence of the present invention. In the case of no conflict, the embodiments of the present application and the features in the embodiments can be combined with each other arbitrarily.

Claims (10)

1. A large integer decomposition problem mapping method based on the Ising model, characterized in that, comprising: Step S1: Introduce auxiliary variables to each intermediate term in the binary multiplication vertical formula, construct auxiliary blocks, and perform formal equivalent replacement on the loss function obtained by each block to make it meet the formal requirements of the Ising model. The loss function of the block is added and replaced by variables, and the Hamiltonian expression of the Ising model is obtained by simplification; Step S2: According to the distribution characteristics of the value of the Hamiltonian in different spin states and its range, adopt a technical solution to update the spin state from less to more, and change the discriminant conditions under certain circumstances so that it can jump out of the local Optimal solution until the Ising model reaches the spin ground state; Step S3: Obtain two prime factor information, realize large integer decomposition, and further obtain the private key in the RSA encryption algorithm from the Euler formula and the open public key in the cryptographic system, and use the private key to convert the ciphertext information into the original plaintext information, Realize the cracking of the RSA cryptosystem. 2. the large integer decomposition problem mapping method based on Ising model according to claim 1, is characterized in that, in described step S1: A loss function of a specific form is generated for each auxiliary block, substituted into the boundary conditions, and a formal equivalent replacement is performed for each loss function so that it does not contain high-order terms above the quadratic term, which meets the formal requirements of the Ising model , and then add all the loss functions, replace variables, and simplify to obtain the Hamiltonian expression of the Ising model, extract the interaction matrix J and the external magnetic field vector h, and transform the large integer decomposition problem into finding the Ising model The problem of solving the spin ground state of the symplectic model; The conversion process is realized through a fixed process, applicable to any large integer, programmed in the computer, for a specific large integer, no separate analysis or derivation of the intermediate process is required, and the corresponding Ising model can be directly obtained; The auxiliary variables are introduced one by one according to each intermediate term a _i b _j in the vertical formula of binary multiplication of two factors, namely y _i,j and z _i,j , wherein y _i,j is the The lowest bit result obtained by adding the binary variables of , z _i,j is the carry obtained by adding the binary variables in the right auxiliary block, a _i b _j , y _i,j , z _i,j constitute an auxiliary block , generating a loss function; The form of the loss function is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , the equivalent replacement The latter form is

The loss function after the equivalent replacement described above does not contain more than two terms, and does not need to reduce the order, and in the Hamiltonian expression obtained after adding all of them, simplifying, and variable substitution, the coefficient of the variable is determined by Restricted within the preset range, the obtained Ising model interaction matrix J and the element size of the external magnetic field vector h are also within a limited range. 3. the large integer decomposition problem mapping method based on Ising model according to claim 2, is characterized in that: Step S1.1: express the target large integer to be decomposed in binary form, and record the number of digits as w; Step S1.2: Assume that the binary digits of the two factors of the target large integer are k and h respectively, and the binary forms from high to low are a ₁ , a ₂ ,..., a _k and b ₁ , b ₂ ,..., b _h ; Step S1.3: For each intermediate term a _i b _j in the binary multiplication vertical formula of two factors, introduce auxiliary variables y _i,j and z _i,j one by one, and set a _i b _j , y _i,j , z _{i, j} three items as an auxiliary block; Step S1.4: Generate a loss function for each auxiliary block. For the auxiliary block on the boundary, introduce additional auxiliary variables according to the form of the loss function and substitute them into the boundary conditions; Step S1.5: Perform a formal equivalent replacement on the loss function obtained for each block, so that it only contains quadratic terms; Step S1.6: Add the replaced loss functions and perform variable substitution, and then simplify to obtain the Hamiltonian expression of the Ising model; Step S1.7: Each variable in the expression is used as a spin node, and the binary quadratic coefficient and the first-order coefficient are respectively extracted to form the interaction matrix J and the external magnetic field vector h of the Ising model, and the remaining invariant parts are The sum is denoted as C. 4. the large integer decomposition problem mapping method based on Ising model according to claim 1, is characterized in that, in described step S2: Step S2.1: Randomly generate the initial spin state, and calculate the Hamiltonian according to the obtained Ising model; Step S2.2: change x spins each time, the initial value of x is 1, and gradually increase x as the number of changes of the same spin state increases; Step S2.3: If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change; Step S2.4: If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset; Step S2.5: Repeat step S2.2-step S2.4 of the process until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two primes of the target large integer If factor information is used, large integer decomposition is realized. 5. the large integer decomposition problem mapping method based on Ising model according to claim 4, is characterized in that: The described criteria for reducing the acceptance of spin state changes, by setting a discriminant energy E_jump required to jump out of the local optimal solution, the Hamiltonian corresponding to the current spin state is no longer calculated, but its Set directly to E_jump, and then repeat the iterative process until the Hamiltonian is updated again. 6. A large integer decomposition problem mapping system based on the Ising model, characterized in that it comprises: Module M1: Introduce auxiliary variables to each intermediate item in the binary multiplication vertical formula, construct auxiliary blocks, and replace the loss function obtained by each block with a formal equivalent to make it meet the formal requirements of the Ising model. The loss function of the block is added and replaced by variables, and the Hamiltonian expression of the Ising model is obtained by simplification; Module M2: According to the distribution characteristics of the value of the Hamiltonian in different spin states and its range, adopt a technical solution to update the spin state from less to more, and change the discriminant conditions under certain circumstances so that it can jump out of the local Optimal solution until the Ising model reaches the spin ground state; Module M3: Obtain two prime factor information, realize large integer decomposition, and further obtain the private key in the RSA encryption algorithm from the Euler formula and the open public key in the cryptographic system, and use the private key to convert the ciphertext information into the original plaintext information, Realize the cracking of the RSA cryptosystem. 7. the large integer decomposition problem mapping system based on Ising model according to claim 6, is characterized in that, in described module M1: A loss function of a specific form is generated for each auxiliary block, substituted into the boundary conditions, and a formal equivalent replacement is performed for each loss function so that it does not contain high-order terms above the quadratic term, which meets the formal requirements of the Ising model , and then add all the loss functions, replace variables, and simplify to obtain the Hamiltonian expression of the Ising model, extract the interaction matrix J and the external magnetic field vector h, and transform the large integer decomposition problem into finding the Ising model The problem of solving the spin ground state of the symplectic model; The conversion process is realized through a fixed process, applicable to any large integer, programmed in the computer, for a specific large integer, no separate analysis or derivation of the intermediate process is required, and the corresponding Ising model can be directly obtained; The auxiliary variables are introduced one by one according to each intermediate term a _i b _j in the vertical formula of binary multiplication of two factors, namely y _i,j and z _i,j , wherein y _i,j is the The lowest bit result obtained by adding the binary variables of , z _i,j is the carry obtained by adding the binary variables in the right auxiliary block, a _i b _j , y _i,j , z _i,j constitute an auxiliary block , generating a loss function; The form of the loss function is F _i,j =(a _i b _j +y _i,j +z _i,j -y _i+1,j-1 -2z _i-1,j ) ² , the equivalent replacement The latter form is

The loss function after the equivalent replacement described above does not contain more than two terms, and does not need to reduce the order, and in the Hamiltonian expression obtained after adding all of them, simplifying, and variable substitution, the coefficient of the variable is determined by Restricted within the preset range, the obtained Ising model interaction matrix J and the element size of the external magnetic field vector h are also within a limited range. 8. the large integer decomposition problem mapping system based on Ising model according to claim 7, is characterized in that: Module M1.1: express the target large integer to be decomposed in binary form, and record the number of digits as w; Module M1.2: Assume that the binary digits of the two factors of the target large integer are k and h respectively, and the binary forms from high to low are a ₁ , a ₂ ,…,a _k and b ₁ ,b ₂ ,…, b _h ; Module M1.3: For each intermediate term a _i b _j in the vertical form of binary multiplication of two factors, introduce auxiliary variables y _i,j and z _i,j one by one, and set a _i b _j , y _i,j , z _{i, j} three items as an auxiliary block; Module M1.4: Each auxiliary block generates a loss function. For auxiliary blocks on the boundary, additional auxiliary variables are introduced according to the form of the loss function and substituted into the boundary conditions; Module M1.5: Perform a formal equivalent replacement of the loss function obtained by each block so that it only contains quadratic terms; Module M1.6: Add the replaced loss functions and perform variable substitution, and then simplify to obtain the Hamiltonian expression of the Ising model; Module M1.7: Each variable in the expression is used as a spin node, and the binary quadratic coefficient and the first-order coefficient are respectively extracted to form the interaction matrix J and the external magnetic field vector h of the Ising model, and the remaining invariant parts are The sum is denoted as C. 9. the large integer decomposition problem mapping system based on Ising model according to claim 6, is characterized in that, in described module M2: Module M2.1: Randomly generate the initial spin state, and calculate the Hamiltonian according to the obtained Ising model; Module M2.2: Each time x spins are changed, the initial value of x is 1, and as the number of changes of the same spin state increases, x gradually increases; Module M2.3: If the changed Hamiltonian decreases, then accept this change to the spin state and reset x to 1, otherwise continue to maintain the spin state before the change; Module M2.4: If x reaches a certain value and has not been reset, lower the criterion for accepting spin state changes until x is reset; Module M2.5: Repeat the process module M2.2-module M2.4 until the Hamiltonian corresponding to the spin state is -C, indicating that the Ising model has reached the spin ground state at this time, including two primes of the target large integer If factor information is used, large integer decomposition is realized. 10. the large integer decomposition problem mapping system based on Ising model according to claim 9, is characterized in that: The described criteria for reducing the acceptance of spin state changes, by setting a discriminant energy E_jump required to jump out of the local optimal solution, the Hamiltonian corresponding to the current spin state is no longer calculated, but its Set directly to E_jump, and then repeat the iterative process until the Hamiltonian is updated again.

Images