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.展开更多
Investigated the properties of LUCas sequence(LUC), the paper proposed a new variant of (probabilistic) public-key encryption scheme. Security analysis of the proposed encryption schemes shows that its one-wayness is ...Investigated the properties of LUCas sequence(LUC), the paper proposed a new variant of (probabilistic) public-key encryption scheme. Security analysis of the proposed encryption schemes shows that its one-wayness is equivalent to partial LUC discrete logarithm problem in ZN, and for the proposed probabilistic encryption scheme, its semantic security is equivalent to decisional LUC Diffie-Hellman problem in ZN. At last, the efficiency of the proposed schemes is briefly analyzed.展开更多
The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by...The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown thai the RSA number n = pq can be easily factored if p and q have the special form of p = as＋b, q=cs＋d, where a, b, c, d are relatively small numbers. Such prime pairs （p, q） are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs （p, q）.展开更多
Let D=pq be the product of two distinct odd primes.Assuming the parity conjecture,we construct infinitely many r≥1 such that E2rD:y2=x3-2rDx has conjectural rank one and vp(x([k]Q))≠vq(x([k]Q))for any odd integer k,...Let D=pq be the product of two distinct odd primes.Assuming the parity conjecture,we construct infinitely many r≥1 such that E2rD:y2=x3-2rDx has conjectural rank one and vp(x([k]Q))≠vq(x([k]Q))for any odd integer k,where Q is the generator of the free part of E(Q).Furthermore,under the generalized Riemann hypothesis,the minimal value of r is less than c log4 D for some absolute constant c.As a corollary,one can factor D by computing the generator Q.展开更多
Let P（x） denote the greatest prime factor of ∏<sub>x【n≤x+x<sup>1/2</sup></sub>n. In this paper, we shall prove that P（x）】x<sup>0.728</sup>holds true for sufficiently large x.
Properties of third-order recurrence sequences were investigated and a new variant of the GH public-key cryptosystem,which was further improved to be a probabil-istic public-key cryptosystem,was proposed.Then security...Properties of third-order recurrence sequences were investigated and a new variant of the GH public-key cryptosystem,which was further improved to be a probabil-istic public-key cryptosystem,was proposed.Then security analysis of the proposed scheme was provided and it was proved that the one-wayness of the proposed scheme is equivalent to partial discrete logarithm and its semantic se-curity is equivalent to decisional Diffie-Hellman problem in ring extension.Finally,efficiency analysis of the proposed scheme was provided,and that these two encryption schemes need to transfer 2log N and 4log N bits data re-spectively.展开更多
基金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.
基金Supported by the 973 State Key Project of China (No.G1999035803)the National Natural Science Foundation of China (No.69931010).
文摘Investigated the properties of LUCas sequence(LUC), the paper proposed a new variant of (probabilistic) public-key encryption scheme. Security analysis of the proposed encryption schemes shows that its one-wayness is equivalent to partial LUC discrete logarithm problem in ZN, and for the proposed probabilistic encryption scheme, its semantic security is equivalent to decisional LUC Diffie-Hellman problem in ZN. At last, the efficiency of the proposed schemes is briefly analyzed.
基金Supported by the National Natural Science Foun-dation of China (60473029)
文摘The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown thai the RSA number n = pq can be easily factored if p and q have the special form of p = as＋b, q=cs＋d, where a, b, c, d are relatively small numbers. Such prime pairs （p, q） are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs （p, q）.
基金supported by National Natural Science Foundation of China (Grant No. 11271212)
文摘Let D=pq be the product of two distinct odd primes.Assuming the parity conjecture,we construct infinitely many r≥1 such that E2rD:y2=x3-2rDx has conjectural rank one and vp(x([k]Q))≠vq(x([k]Q))for any odd integer k,where Q is the generator of the free part of E(Q).Furthermore,under the generalized Riemann hypothesis,the minimal value of r is less than c log4 D for some absolute constant c.As a corollary,one can factor D by computing the generator Q.
基金Project supported by the Tian Yuan Item in the National Natural Science Foundation of China.
文摘Let P（x） denote the greatest prime factor of ∏<sub>x【n≤x+x<sup>1/2</sup></sub>n. In this paper, we shall prove that P（x）】x<sup>0.728</sup>holds true for sufficiently large x.
基金supported by the National Natural Science Foundation of China(No.90412011)the Hi-Tech Research and Development Program of China(No.2002AA143021)。
文摘Properties of third-order recurrence sequences were investigated and a new variant of the GH public-key cryptosystem,which was further improved to be a probabil-istic public-key cryptosystem,was proposed.Then security analysis of the proposed scheme was provided and it was proved that the one-wayness of the proposed scheme is equivalent to partial discrete logarithm and its semantic se-curity is equivalent to decisional Diffie-Hellman problem in ring extension.Finally,efficiency analysis of the proposed scheme was provided,and that these two encryption schemes need to transfer 2log N and 4log N bits data re-spectively.
