The hardness of the integer factoring problem(IFP)plays a core role in the security of RSA-like cryptosystems that are widely used today.Besides Shor’s quantum algorithm that can solve IFP within polynomial time,quan...The hardness of the integer factoring problem(IFP)plays a core role in the security of RSA-like cryptosystems that are widely used today.Besides Shor’s quantum algorithm that can solve IFP within polynomial time,quantum annealing algorithms(QAA)also manifest certain advantages in factoring integers.In experimental aspects,the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms.In this paper,we report some interesting observations about the effects of QAA for solving IFP.More specifically,we introduce a metric,called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave.We find that T-factor has obvious effects on annealing times for IFP:The larger of T-factor,the quicker of annealing speed.The explanation of this phenomenon is also given.展开更多
In this paper,we have proved that if one of the following conditions is satisfed,then the equations in title has no positive integer solution:①D=∏si=1P i or D=2∏si=1P i and \{ P i≡3 (mod 4)\} (1≤i≤s) or P i≡5 (...In this paper,we have proved that if one of the following conditions is satisfed,then the equations in title has no positive integer solution:①D=∏si=1P i or D=2∏si=1P i and \{ P i≡3 (mod 4)\} (1≤i≤s) or P i≡5 (mod 8) (i≤i≤s); ② D=∏si=1P i-1 (mod 12), 1≤s≤7 and \{D≠3·5·7·11·17·577,7·19·29·41·59·577;\} ③ D=2∏si=1P i,1≤s≤6 and \{D ≠2·17,2·3·5·7·11·17,2·17·113·239·337·577·665857;\} ④ D=∏si=1P i≡-1 (mod 12), 1≤s≤3 and D≠ 5·7,29·41·239.展开更多
基金the National Natural Science Foundation of China(NSFC)(Grant No.61972050)the Open Foundation of StateKey Laboratory ofNetworking and Switching Technology(Beijing University of Posts and Telecommunications)(SKLNST-2020-2-16).
文摘The hardness of the integer factoring problem(IFP)plays a core role in the security of RSA-like cryptosystems that are widely used today.Besides Shor’s quantum algorithm that can solve IFP within polynomial time,quantum annealing algorithms(QAA)also manifest certain advantages in factoring integers.In experimental aspects,the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms.In this paper,we report some interesting observations about the effects of QAA for solving IFP.More specifically,we introduce a metric,called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave.We find that T-factor has obvious effects on annealing times for IFP:The larger of T-factor,the quicker of annealing speed.The explanation of this phenomenon is also given.
文摘In this paper,we have proved that if one of the following conditions is satisfed,then the equations in title has no positive integer solution:①D=∏si=1P i or D=2∏si=1P i and \{ P i≡3 (mod 4)\} (1≤i≤s) or P i≡5 (mod 8) (i≤i≤s); ② D=∏si=1P i-1 (mod 12), 1≤s≤7 and \{D≠3·5·7·11·17·577,7·19·29·41·59·577;\} ③ D=2∏si=1P i,1≤s≤6 and \{D ≠2·17,2·3·5·7·11·17,2·17·113·239·337·577·665857;\} ④ D=∏si=1P i≡-1 (mod 12), 1≤s≤3 and D≠ 5·7,29·41·239.
