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.展开更多
As social networks and related data processes have grown exponentially in complexity,the efficient resolution of combinatorial optimization problems has become increasingly crucial.Recent advancements in probabilistic...As social networks and related data processes have grown exponentially in complexity,the efficient resolution of combinatorial optimization problems has become increasingly crucial.Recent advancements in probabilistic computing approaches have demonstrated significant potential for addressing these problems more efficiently than conventional deterministic computing methods.In this study,we demonstrate a highly durable probabilistic bit(pbit)device utilizing two-dimensional materials,specifically hexagonal boron nitride(h-BN)and tin disulfide(SnS2)nanosheets.By leveraging the inherently stochastic nature of electron trapping and detrapping at the h-BN/SnS2 interface,the device achieves durable probabilistic fluctuations over 108 cycles with minimal energy consumption.To mitigate the static power consumption,we integrated an active switch in series with a p-bit device,replacing conventional resistors.Furthermore,employing the pulse width as the control variable for probabilistic switching significantly enhances noise immunity.We demonstrate the practical application of the proposed p-bit device in implementing invertible Boolean logic gates and subsequent integer factorization,highlighting its potential for solving complex combinatorial optimization problems and extending its applicability to real-world scenarios such as cryptographic systems.展开更多
Integer factorization,the core of the Rivest−Shamir−Adleman(RSA)attack,is an exciting but formidable challenge.As of this year,a group of researchers’latest quantum supremacy chip remains unavailable for cryptanalysi...Integer factorization,the core of the Rivest−Shamir−Adleman(RSA)attack,is an exciting but formidable challenge.As of this year,a group of researchers’latest quantum supremacy chip remains unavailable for cryptanalysis.Quantum annealing(QA)has a unique quantum tunneling advantage,which can escape local extremum in the exponential solution space,finding the global optimal solution with a higher probability.Consequently,we consider it an effective method for attacking cryptography.According to Origin Quantum Computing,QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers.We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer,and attack RSA-2048 which is composed of a class of special integers.The experiment factored this class of integers of size 22048,N=p×q.As an example,the article gives the results of 10 RSA-2048 attacks in the appendix.This marks the first successful factorization of RSA-2048 by D-Wave quantum computer,regardless of employing mathematical or quantum techniques,despite dealing with special integers,exceeding 21061−1 of California State University.This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.展开更多
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.展开更多
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 F_q be a finite field with q = p^m, where p is an odd prime. In this paper, we study the repeated-root self-dual negacyclic codes over Fq. The enumeration of such codes is investigated. We obtain all the self-dual...Let F_q be a finite field with q = p^m, where p is an odd prime. In this paper, we study the repeated-root self-dual negacyclic codes over Fq. The enumeration of such codes is investigated. We obtain all the self-dual negacyclic codes of length 2~ap^r over F_q, a ≥ 1.The construction of self-dual negacyclic codes of length 2~abp^r over F_q is also provided, where gcd（2, b） = gcd（b, p） = 1 and a ≥ 1.展开更多
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.
基金National Research Foundation of Korea,Grant/Award Numbers:RS-2024-00334953,RS-2024-00449412Institute of Information&communications Technology Planning&Evaluation,Grant/Award Number:RS-2024-00466640。
文摘As social networks and related data processes have grown exponentially in complexity,the efficient resolution of combinatorial optimization problems has become increasingly crucial.Recent advancements in probabilistic computing approaches have demonstrated significant potential for addressing these problems more efficiently than conventional deterministic computing methods.In this study,we demonstrate a highly durable probabilistic bit(pbit)device utilizing two-dimensional materials,specifically hexagonal boron nitride(h-BN)and tin disulfide(SnS2)nanosheets.By leveraging the inherently stochastic nature of electron trapping and detrapping at the h-BN/SnS2 interface,the device achieves durable probabilistic fluctuations over 108 cycles with minimal energy consumption.To mitigate the static power consumption,we integrated an active switch in series with a p-bit device,replacing conventional resistors.Furthermore,employing the pulse width as the control variable for probabilistic switching significantly enhances noise immunity.We demonstrate the practical application of the proposed p-bit device in implementing invertible Boolean logic gates and subsequent integer factorization,highlighting its potential for solving complex combinatorial optimization problems and extending its applicability to real-world scenarios such as cryptographic systems.
文摘Integer factorization,the core of the Rivest−Shamir−Adleman(RSA)attack,is an exciting but formidable challenge.As of this year,a group of researchers’latest quantum supremacy chip remains unavailable for cryptanalysis.Quantum annealing(QA)has a unique quantum tunneling advantage,which can escape local extremum in the exponential solution space,finding the global optimal solution with a higher probability.Consequently,we consider it an effective method for attacking cryptography.According to Origin Quantum Computing,QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers.We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer,and attack RSA-2048 which is composed of a class of special integers.The experiment factored this class of integers of size 22048,N=p×q.As an example,the article gives the results of 10 RSA-2048 attacks in the appendix.This marks the first successful factorization of RSA-2048 by D-Wave quantum computer,regardless of employing mathematical or quantum techniques,despite dealing with special integers,exceeding 21061−1 of California State University.This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.
基金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.
基金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 Reward Fund for Outstanding Young and Middle-Aged Scientists of Shandong Province(Grant No.BS2011DX011)Qingdao Postdoctoral Fund(Grant No.861605040007)
文摘Let F_q be a finite field with q = p^m, where p is an odd prime. In this paper, we study the repeated-root self-dual negacyclic codes over Fq. The enumeration of such codes is investigated. We obtain all the self-dual negacyclic codes of length 2~ap^r over F_q, a ≥ 1.The construction of self-dual negacyclic codes of length 2~abp^r over F_q is also provided, where gcd（2, b） = gcd（b, p） = 1 and a ≥ 1.
基金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.
