Файл: QCAlgorithmsFastCalculationofPrimeNumbers52.pdf

The Big Bang, which may not have been the first, is our empirical conjecture #6, that “There are multiple Big Bangs”. A Big Bang is revealed then as an expression of calculus.

Furthermore, we consider that calculus, SR, QM, GR+QM, and

QC already existed in nature in multiple Big Bangs! These things have existed since time immemorial, and support our empirical conjecture #5. Galaxies were then created based on calculus. Nature is exact, rigorous in spacetime. We reject the QM interpretation by Heisenberg. We explain that by difference equations using the set Q, as done in [28] without infinitesimals, or approximations.

Calculus optimizes understanding, as the tool that allows one (i.e. also particles) to prevent trial and error in finding the exact result of optimization problems [28].

Some may claim, without proof, that "a completely rigorous definition of infinitesimals can be used to derive most (if not all) of and calculus and modern atoms) analysis" (but no one can name an infinitesimal numerically). Calculus should use no infinitesimals or irrational numbers, as a consequence of QM and QC. This was our empirical conjecture #2.

7. GCD OPTIMIZATION

In the GCD of a and b, one takes b to be smaller than a, and both belong to the set N.

The Pascal code segment in

Fig.(2) on the right exemplifies a well-known way to calculate the GCD as done usually.

24

The code snippet in Fig. 3 below is much faster to implement, with no mod calculation. The faster speed is explained by the well-known theory of computational complexity, which gives the time required as a function of N.

The code for the GCD can be optimized, but note that there is no such thing as subtraction in the realms of Boolean mathematics and digital hardware (e.g., using bignum).

To subtract in bignum in Figs.(3) (and any other arithmetic operation in bignum, such as multiplication, exponentiation, logarithm, module, and division) one uses encoding and addition -- which can be done natively (fast) in digital hardware and uses Boolean mathematics.

In the commercial cellphone used by us in 2023, bignum was supported in more than 101000 decimal digits, more than sufficient for 2048 binary digits (using approximately 617 decimal digits).

Particularly in subtraction as in Fjg.(3), one first finds the 2's complement of the subtrahend. In step-2, one adds the first number and 2's complement of the subtrahend. In step-3, if a carry is produced, one discards the carry and outputs the

25

result. If there is no carry then one takes the 2's complement of the result to output.

Subtraction as an operation would imply the existence of negative numbers: 5 - 3 is the same thing as 5 + (-3), and in the

Boolean set (the set B), negative quantities are forbidden. This is similar to forbidding imaginary numbers, infinitesimal numbers, irrational numbers, and p-adic numbers in set Q [1], and they are also forbidden in set B.

The actual calculation of Fig.(3) is implemented as a binary calculation, which is done using only digital hardware -- one number at a time, although it can be done concurrently – albeit not using QC.

A binary number such as using N values of the set {1,2,3, …,N-1} is 1:1 equivalent to using only the B set {0,1} also with N values in BN. Further, we can calculate subtraction using addition (with 2-complements) using digital hardware operations. Also, 0n = 0 and 1n = 1, with immediate results.

Other techniques, such as the General Number Field Sieve, are well-known to be used to crack numbers approaching 800 bits in practical terms today.

The potential influence of radiation sources (e.g., cosmic rays) were accounted for by running the results several times, with zero spread. The results are exact, which can be easily verified by third-parties. All results shown were measured in Sonora, Calif., U.S., near Yosemite.

We do not provide the source code, for the aforementioned cybersecurity reason, but relate the numerical results in Section 9, with QC as well.

26

8. ASYMPTOTIC APPROXIMATIONS

The prime number theorem states that the prime numbers become less common as their length increases.

This makes no hypothesis on an objective model.

How primes are distributed among positive integers is described asymptotically by various approximations -- without any hypothesis on the behavior. It is also known10 that if p1 > p2, then p1 = (2m+2) + p2, for some m≥0 in the set Z, just not if p2 =

2.

Our empirical conjecture #7 is that “The larger p1 or p2 as prime numbers, except 2, the further apart are p1 = (2m+2) + p2, for any m≥0 in the set Z”.

This confirms the well-knowntwin prime conjecture, which states that there are infinitely many primes p such that p + 2 is also prime, but also we conjecture them to be more rarified when p is increased.

Then, as a consequence of the prime number theorem, one gets various asymptotic approximations for the nth prime number, beginning with pn n log n [24], which can be written as e(pn)/n = n.

A better approximation is given in [25]. In 1999, P. Dusart proved that, for k in the set N, the kth prime is greater than k(\ln k + \ln\ln k-1) for k ≥ 2.

Not as an approximation but exactly, we make an empirical conjecture #8, without proof here, that an exact formula

10 All prime numbers except 2, are odd numbers.

27

describing how prime numbers are distributed among positive integers can be described rigorously to any such number.

We do not provide the expression for empirical conjecture #8, for cybersecurity reasons.

9. QC NUMERICAL RESULTS

RSA 2048 refers to the key size used in RSA encryption. The key size supposedly determines the strength of the encryption and the level of security it provides. RSA 2048 uses a 2048-bit key, making it supposedly significantly more secure than smaller key sizes like RSA 1024.

We contradict this speculation numerically with QC, using a

2048 key given by RSA and yet unbroken. This challenge dates to at least 2007 [30]. The page [30] serves as an archive for the factoring challenges conducted by RSA Laboratories through 2007. The key numbers will be published elsewhere, with a delay, for security reasons.

RSA-2048 has been particularly sought after, to break the encryption -- and RSA declared at time: “The RSA Challenge numbers are the kind we believe to be the hardest to factor; these numbers should be particularly challenging. These are the kind of numbers used in devising secure RSA cryptosystems.”

The numerical results, which third parties can use to verify, in simple multiplication to break RSA-2048, are given elsewhere.

This confirms QC; many applications of QC in other areas are being pursued, including in healthcare [31].

28

Periodicity estimates, as the heart of any QC, may be improved. Biological sequences , e.g, are rarely exactly periodic and the estimated period returned by exploratory analysis may be anywhere from very weakly to very strongly dominant with respect to the remaining sequence components

(which may contain other periods or be essentially non-periodic) [32].

10. CONCLUSION

RSA is pathologically broken. Increasing the key size is no help, and may make it easier to decrypt.

The U.S. NIST has speculated that 2048 bit keys will be valid up to about the year 2030. It just now (2023) has been broken in seconds, using a commercial cellphone and QC.

A post-quantum, HIPAA compliant, end-to-end, patent-free, export-free, secure online solution, is being created based on ZSentry used from 2004 to 2014, to replace RSA. One needs a quantum-resistant algorithm, because all existing public-key encryption can be broken. This will be pursued publicly soon as an IETF RFC, and as a NIST submission.

We further presented 8 empirical conjectures, all supported by experiments, that should be helpful in the further development of QC and QM.

This work may kindle other applications of QC and QM, which are confirmed based on this study.

A medical doctor, e.g., can use QC in his mind while treating classically for a pathology, using available means. GR is to be unified with QM following QC. Cosmology can consider that

29

calculus, SR, QM, GR+QM, and QC already exist ontologically, in nature.

Additional work is suggested on periodicity estimation (see footnote 5).

FUNDING

This research received external funding from Network Manifold Associates, Inc. (NMA), Safevote, Inc, and PlanaltoResearch. The authors declare no conflict of interest.

ACKNOWLEDGMENTS

The authors are indebted to Spiros Konstantogiannis, the late Mādhava of Sangamagrāma, and six anonymous reviewers. ZSentry development from 2004 to 2014, had the benefit of dozens of contributions, including by the many angel investors in NMA, principally with the late Einar Stefferud, Graham Tanaka, Kurt Neumann, Michael Norden, and Vernon Neppe. The results shown in this manuscript, include the contribution of several individuals -- some of which the author does not know personally, and some of which may come spontaneously online. Repeated updates are suggested, so as not to use any outdated terms. Any suggestions are always welcome! This is a new model for an online manuscript, where anyone may collaborate, much like a question. We answer two questions: what role can QC have, and what it may reveal. To participate send me a private or public message, by ResearchGate or email (see address above). ResearchGate discussions and private messages were also used, for “live” feedback, important due to the physical isolation caused by COVID.

30

REFERENCES

[1]Gerck, E. “Algorithms for Quantum Computation: Derivatives of Discontinuous Functions.” Mathematics 2023, 11, 68. https://doi.org/10.3390/math1101006.

[2]Vandersypen, L. M. K. et al. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 883–887 (2001).

[3]Martín-López, E. et al. Experimental realization of Shor’s quantum factoring algorithm using qubit recycling. Nat. Photon.

6, 773–776 (2012).

[4]Bocharov, A., Roetteler, M., & Svore, K. M. Factoring with qutrits: Shor’s algorithm on ternary and metaplectic quantum architectures. Phys. Rev. A 96, 012306

(2017).

[5]Smolin, J. A., Smith, G. & Vargo, A. Oversimplifying quantum factoring. Nature 499, 163–165 (2013).

[6]Dattani, Nikesh S., & Bryans, Nathaniel. Quantum factorization of 56153 with only 4 qubits. arXiv preprint arXiv:1411.6758v3 (2014).

[7]Yan, S. Y. Quantum Algorithms for Integer Factorization. In:

Quantum Computational Number Theory. Springer, Cham

59–119 (2015).

[8]Peng, X. et al. Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation. Phys. Rev. Lett. 101, 220405 (2008).

31

[9]Burges, C. J. C. Factoring as Optimization. Microsoft Research MSR-TR-200 (2002).

[10]Wang, B., Yang, X. & Zhang, D. Research on Quantum Annealing Integer Factorization Based on Different

Columns. Front. Phys. 10:914578 (2022).

[11]Dridi, R. & Alghassi, H. Prime Factorization using Quantum Annealing and Computational Algebraic Geometry.

Sci. Rep. 7, 43048 (2017).

[12]Xu, N. et al. Quantum Factorization of 143 on a Dipolar-

Coupling Nuclear Magnetic Resonance System. Phys.

Rev. Lett. 108, 130501 (2012).

[13]Li, Zhaokai et al. High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311. arXiv preprint arXiv:1706.08061 (2017).

[14]Xu, K. et al. Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State

Single Spin System. Phys. Rev. Lett. 118, 130504 (2017).

[15]Dhaulakhandi, R., Bikashi, K. B., Seo, F. J. Factorization of large tetra and penta prime numbers on IBM quantum processor. Published in arxiv.2304.04999. 2023.

[16]Gerck, E. “Pathologically breaking RSA by quantum computation”. Published in https://www.researchgate.net/publication/374155658/, 2023.

Accessed October 12, 2023.

[17]Gerck, E. “SECURE EMAIL TECHNOLOGIES X.509 / PKI,

PGP, IBE, AND ZSENTRY/ZMAIL: A Usability & Security

32

Comparison”. Published in book: “Corporate Email Management”, Chapter: 12, Publisher: ICFAI University Press. 2008. Also at “https://www.researchgate.net/publication/286458410/”. Accessed October 12, 2023.

[18]Gerck, E, and Cruz, C.H.B.. “Eigenvalue translation method for mode calculations”. Published in Applied Optics 18(9):1341. 1979. Also at “https://www.researchgate.net/publication/294090734/”. Accessed October 12, 2023.

[19]Gerck,E. “Prony method revised” 1979. Published in Applied Optics 18(18):3075. Accessed October 12, 2023.

[20]Gerck, E. and Gerck, E. V. “New Physics with the

Euler-Lagrange Equation: Going Beyond Newton”. Published in https://www.researchgate.net/publication/333677283/, 2019. Accessed October 12, 2023.

[21]Oppenheim, A.V. , Schafer, R. W., Yuen, C. K. “Digital Signal Processing”. 1978. Published in IEEE Transactions on

Systems, Man, and Cybernetics.

[22]Gerck, E. “Tri-State+ communication symmetry using the algebraic approach”. Published in https://www.researchgate.net/publication/350950693/ , 2019.

Accessed October 12, 2023.

[23]Konstantogiannis, S.

https://www.researchgate.net/profile/Spiros-Konstantogiannis, accessed June 8, 2023.

33

[24]Cesàro, E. (1894). "Sur une formule empirique de M. Pervouchine". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. 119: 848–849.

[25]Dusart, P. “The k^{th} prime is greater than k(\ln k + \ln\ln k-1) for k ≥ 2”. 1999, Mathematics of Computation 68(225): 411-416. Also at DOI: 10.1090/S0025-5718-99-01037-6. Accessed June 8, 2023.

[26]Lamé, G. 1884 "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes rendus des séances de l'Académie des Sciences. 19: 867–870. 1884.

[27]Gerck, E., Gallas, J. A. C., and d'Oliveira, A.B. “Solution of the Schrödinger equation for bound states in closed form”.

1982. Published in Phys. Rev. A 26, 662. Also at https://doi.org/10.1103/PhysRevA.26.662. Accessed October 12, 2023.

[28]Gerck, E., and d'Oliveira, A.B.”Continued fraction calculation of the eigenvalues of tridiagonal matrices arising from the Schroedinger equation”. Published by Elsevier in

Journal of Computational and Applied Mathematics

Volume 6, Issue 1, 1980, Pages 81-82. Also available at https://www.sciencedirect.com/science/article/pii/0771050X809

00200. See as “Matrix-Variational Method: An Efficient

Approach to Bound State Eigenproblems”, Report number:

EAV-12/78. Affiliation: Laboratorio de Estudos Avancados, IAE,

CTA, S. J. Campos, SP, Brazil; available online at https://www.researchgate.net/publication/286625459/. Accessed October 12, 2023. In unpublished work, in 1977, cited as [3] in Report number: EAV-12/78, Gerck notes his observations on the “exponential difference”, that the method is based on a new piecewise representation of the second-derivative operator on

34