Файл: QCAlgorithmsFastCalculationofPrimeNumbers52.pdf

QC Algorithms: Faster Calculation of Prime

Numbers

This version: Oct/30/2023 First version: August/4/2023 By Ed Gerck* and Ann Gerck, © egerck@gmail.com PlanaltoResearch

781 Washington St. #3423

Sonora, CA 95370

ORCID: 0000-0002-0128-5875

ABSTRACT

(If interested, please request a copy) We factored numbers with more than 101000 decimal digits, and the capital cost was less than $1,000. The quantum computing (QC)) version used here has simultaneous multiple-states logic (following ‘all states at once’), with more than a googol of possible states. We show that the equivalence of QC techniques (with IBM, Google and others compared with our version of QC) has been hidden for about 2,500 years – since Pythagoras. All our computations were done in a commercial cellphone, or a commercial Linux desktop, as our QC devices -- opening the user market to many industries. No cryogenics or special materials were used. A post-quantum, HIPAA compliant, end-to-end, patent-free, export-free, secure online solution, is being created, based on ZSentry as used from 2004 to 2014, to replace RSA. One needs a quantum-resistant algorithm, because all existing public-key encryption can be broken. We further present 8 empirical conjectures, all supported by experiments, that should be helpful in the further development of QC, and applications to other areas. Applications to healthcare and cosmology are suggested.

______________________________________

* https://www.researchgate.net/profile/Ed_Gerck

One must be patient in order to achieve effective change and implement a forward-looking vision -- because both must be long-term.

1. INTRODUCTION

This work deals with algorithms for calculating prime numbers, taking into account quantum computing (QC) and quantum mechanics (QM) as described in [1-15]. A more detailed numerical version with disclosed keys will be published elsewhere, and here noted.

Notwithstanding our empirical conjecture #1 on the ontological question (as discussed in Section 3), it may seem strange at first sight to use QM in mathematical computations, such as factorizations, and number properties. This seems to confound different topics -- what has QM (in physics) to do with numbers

(in mathematics)?

Of course, QM offers theoretical support for QC, but it seems that nothing more! So, the answer has been surprising.

The theoretical and experimental factorization using QM have been reported in different fashions in QC by using Gerck’s algorithm [1], Shor's algorithm [2-4], adiabatic QC [5-10], quantum annealing principles [10-11], and others [12-14]. The largest prime number factored so far by the techniques [2-15] is 4088459 [15], which is very small for cybersecurity applications. We extend this, using QC as described in [1], to

101000 decimal digits, pathologically breaking RSA-2048 [16] of just 617 decimal digits. The pathology is described in Section 8.

Using QM to partition a large number into its prime numbers seems to be a hard, laborious problem in QC according to

[2-15] but not in QC according to [1]. Cybersecurity itself depends on rigorous results for very large prime numbers, with arbitrary-length extent, such as with 2048 binary digits or more. So, resolving this inconsistency is important.

2

This leads us to two questions explored here:

(1)Why use QM in mathematical computations? or, What role can QM possibly have in QC?; and

(2)What may QC reveal?

The first question is easily answered by this work. To the second question, e.g., an objection can be commonly stated non-technically as, “an infinite sum of numbers cannot be rational by the definition of rational numbers because infinite is a keyword.” So, maybe some mathematical conjectures will end up being refuted or confirmed in the domain of theory of numbers by a computing power as high as QC.

Rational numbers in the form m/n (m and n are integer numbers, n not 0) using arbitrary-length integer numbers, called bignum in coding, are routinely used in CS. This can be extended to negative rational numbers, as is well-known. One can readily calculate with them, using e.g., the free program bc in Unix-like systems with Gnome, or in coding libraries for almost any language.

Numerically, our QC can show that irrational numbers are an illusion since Pythagoras – more than 2,500 years ago -- they do not exist. The illusions that can be disproved numerically by

QC include complex numbers, infinitesimal numbers, p-adic numbers, and more -- we suggest here, as an empirical conjecture #2, signaling an end to “imagined mathematics”.

Mathematics, in our view, is a deductive, experimental science, where the final arbiter is empirical evidence.

Another possible objection is cybersecurity itself, such as preventing “Store Now, Decrypt Later” as a well-known threat

(this works, because QC is expected to exist in 10 to 20 years,

3

which will reveal passwords, industrial and pharmaceutical research, and top secret U.S. intelligence. This work shows that this future has arrived today.) When enemies can use this work to break security, they can become privy of what large countries … already known by using large resources. We are, thus, just leveling the "playing field". No more "security by obscurity", where only large governments can have access to the data -- and without our knowledge compromise the U.S.

The principle we use was pioneered with ZSentry [17]: any encryption method should not have a target. A target can always be attacked; what is hard today may become easy tomorrow – as it is about to happen, with QC. The RSA encryption algorithm should be deprecated immediately, offering users to choose better security. ZSentry [17] is being updated post-quantum, to follow this manuscript. This will be soon pursued publicly as an IETF RFC, and as a NIST submission.

1.1. Definitions

The need for aircraft control in 1910 might not have been noted, but existed nonetheless. 1

The definition of a prime number in the set of natural numbers (set N) leads to the well-known answer that a prime number, except 1, has no other divisors other than itself.

1 At the beginning of 1909 the number of airplanes in the world's armies was zero. By 1910 it was fifty. An exponential growth has been common in microbiology, and cannot be entirely predicted at the start.

4

That definition is now a standard, dating to circa 300 BC by Euclid, but the Discrete Fourier Transform Method (DFTM) is proposed -- leading to an alternative definition.

By the standard definition, factorization of an integer uses a multiplication partition. It is an expression of that integer as a product of other integers; prime factorization of a positive integer >1 is the expression of that integer as a product of primes and it is unique by the fundamental theorem of arithmetic. See Section 4.

Albeit, one can see multiplication arithmetically, as repeated addition.

This opens the possibility of finding prime numbers by exploring objective periodicity, which can be done classically or by using QC -- both of which are considered in the Sections ahead.

A second model to the Euclidean algorithm is, therefore, offered by the proposed repeated addition partition. This seems to contradict 2,500 years of mathematical history.

Albeit, as well-known, a partition of a set induces an equivalence relation on that set. Here, the induced equivalence relation is the factorization of the number N. This is not a new congruence relation, however, but the same concept from Euclid, circa 300 BC.

However, using addition, the element "0" is the identity element -- as it does not change any addition. The number "1" is not a prime (see Section 1.2), whatever

5

model is used. The addition model is also physically intuitive, directly connecting to localized waves in a chord, and periodicity appears naturally and objectively -- even visually or acoustically.

In using the model of repeated addition for partition, the terms "factorization", "composite number", and "prime number" have to be defined accordingly.

To wit, one defines the factorization result for any prime number by either method, although a different method is used to calculate it.

Example: the expression 2x3 can be represented by 3+3 and by 2+2+2, in the equivalence class of the sets {2,3} and {2+2+2, 3+3}. Thus, 6 admits the prime numbers 2 and 3 -- in both models the answer is the same congruence relation.

This is assured by the laws of arithmetic, as multiplication is repeated addition.

This also makes “factorization” and “prime numbers” unchanged, as a result -- although using different algorithms. This allows one to connect to all existing theorems on both terms.

Another reason to use the repeated addition model is to avoid the operation of division, whereas prime numbers are usually defined by division, which is a difficult integer operation — e.g., a time-expensive procedure, may

6

include fractional numbers to infinite extent, and may have no finite limit in the set Q.

The division of two integer numbers is also not always an integer number. The integer numbers do not form a complete mathematical field under the operation of division.

However, the sum of two finite integer numbers is always a finite integer number. Under the operation of addition, the finite integer numbers form a complete field.

Basing factorization on finite integer addition, thus, not only makes it trivial, and faster, but also makes it use finite integer numbers, which is a complete field. No longer has one a need to cope with fractional results, or expressions that do not end. An automatic "best base representation" ensues.

Take the number 6. The well-known factorization 2x3 is a product, 2+2+2 or 3+3 uses repeated addition. But both forms express the same factorization in prime numbers, as a common congruence relation: 2 and 3.

However, new insights and less difficulties can be recognized by using the second form, as discussed in the following. Particularly, periodicity is objective and, as shown in the following, easier to account for when addition is used to define a prime number. Thus, the motivation of this work is finding prime numbers by exploring objective periodicity, and QC is an accessory.

7

To fit with the QM and the following, hereafter, QC is only considered in the formulation of [1], not of [2-15], although we show in Section 6 that they are equivalent.

.

1.2. On The Exclusion Of The Number 1

The number 1 does not satisfy the defining property of a prime number, for some reasons.

First, because if it were counted a prime, then one could write the prime factorization of any integer in many ways, since 1 is the multiplicative identity and thus it could be added to any factorization expression as many times as one wishes. This would not work for the second partition either, using repeated addition.

But that is not the main reason why, as recently as 50 years ago, the number 1 is no longer counted as a prime number anymore.

It is not only for the prime factorization to be unique, which is fundamental to number theory. There is an even higher reason: the number 1 is not a prime number because we would have to exclude it in many theorems valid for prime numbers, and include it in none. Thus, a fundamental set argument emerges, using mereology: 1 is not of the same class as the set of prime numbers.

One cannot partition 6 as "3+2+1" either. The number 1 should not be used -- 1 is not a prime number. So, one cannot write 6 as "1+1+1+1+1+1". This becomes useful when considering the repeated addition model of the formation of prime numbers, where we can use a physical model of waves in a chord.

8

1.3. Arithmetic Rules

In the arithmetic of positive integers, multiplication is simply repeated addition.

So, the two factorization models can refer to the same concept. The same is obtained if fractions of signed integers representing real numbers are used.

We suggest here, as an empirical conjecture #3, that the addition partition allows one to calculate primes more effectively versus the multiplication partition.

1.4. The Physical Wave Method -- The DFTM

For example, take 2047, a number with prime factors

(multiplication) equal to 23 and 89, i.e., 2047 = 23 × 89.

This means that an oscillating chord may be split in 23 oscillations of a single 89 block, or 89 oscillations of a 23 block.

A chord would not physically carry any other mix, or 89 oscillations AND 23 oscillations. This can be verified objectively, experimentally, both visually and acoustically. The best experimental model, thus, must use repeated sums with different factors, not multiplication. This must have an influence in music too, to be pursued elsewhere.

Another way to see it, is that the reality of chord oscillations, when held between two fixed points, can be fragmented into two different views.

In the first, there are infinite frequencies separated by infinitesimal andirrational differences. This is the well-known Fourier Transform view, where the model frequencies are

9

independent of the chord modes, so they do not depend on the chord.

In a physical application, we have to satisfy a physical resonance condition in physics, where we need to not consider infinitesimal differences, irrational frequencies, or infinite frequencies. This means no Problem of Closure [1] happens in reality.

Albeit, one expects to see 2+2+2 more easily than 3+3, as one expects the oscillation mode with higher losses to fade first.

Thus, we see the lower modes more easily, with less losses.

This has been useful to calculate the modes of an interferometer for a laser [18-19]. This is not important if a physical application is not considered.

The second view, which we called DFTM in Section 1.1, is determined mathematically by applying the first, even though the first is fictional, but integrates everything as input to an

Euler-Lagrange Equation [20], whose output follows natural laws -- eliminating infinities, infinitesimals, and irrational numbers.

To every element of the wire, no matter how physically small (albeit not infinitesimal), one can assign natural laws of motion, differentially, by the Euler-Lagrange Equation. This second view is calculated mathematically step-by-step in the Appendix of [20].

Then, the second view (i.e., the DFT) emerges as the physical reality we are supposed to see, even out of a fictional reality (i.e., as modeled by the FT). The first reality still is of two infinite types, which are both obviously physically incorrect: of frequencies going to infinity, and as something infinite. Though, nothing is infinite (and infinity is not a number). We can correct

10

that by a physical realization into natural numbers (the set N) using the Euler-Lagrange equation [20].

Only physical frequencies (in the set N) do exist. We see that visually, in a continued fraction expansion, in a harmonic composition using the DFT [20], or as well-known in music.

These physical frequencies are seen, also experimentally, following an extended sum partition (as a linear combination of independent oscillators [20]), but not as a product.

In the case of 6, one can see oscillations in 3 sets of 2, or 2 sets of 3. There is no physical space for any other combination.

2. NON-BOOLEAN LOGIC

QC has been instrumental in the realization of Section 1 and its sub-sections, using non-Boolean logic and allowing us to consider the sets R=C=Q in numerical calculations, but

Boolean logic can be used to an even greater effect and faster calculations, with no confounding factors. This will be published elsewhere, deprecating tri-state™ as necessary in hardware, as considered by Intel and others.

QC uses simultaneous multiple-states logic (following ‘all states at once’), not only Boolean logic. To those who question that

QC, offering many more states of logic would be somehow “illogical” to consider, one notes that, in unpublished notes, before 1910, Charles Sanders Pierce is well-known to have soundly rejected the idea that all propositions must be either

True or False, as in Boolean logic, the same as Frege is well-known to have proposed in mathematical semantics.

11

Pierce developed well-understood rules where the LEM2 is not valid, including some truth tables.

The three logical states are: 1 (true), 0 (false), and X (undefined), as well-known. This avoids the Gödel uncertainties

(to be published elsewhere). In QC, one can be more precise and include more states than physical QM (e.g., quantum annealing) as one makes the model as the behavior be more inclusive, viewed internally, even though externally one should be limited to use the LEM3. Hence, QC using software promises to be easier to delve deeper (e.g., one googol) than

QM using hardware in the number of states, while it can use available hardware -- as we report (e.g., cellphone, desktop PC).

This is an important result for the digital industry, which uses Boolean logic in hardware, and for the future of QC.

Our empirical conjecture #4 is that: “We can achieve freedom from the LEM in the behavior while the implementation can obey the LEM.”

2 This can be further understood, by noting that the LEM says [22] that “For every proposition ‘p’, either ‘p’ or ‘not p’ holds”. To many this is a “self-evident” truth, but only works in a binary logical system, such as Boolean logic. For example, it does not apply to ’p’ and ’not p’, a valid case in logic, but not in binary logic.

3 Other researchers may at first diverge from this interpretation. The LEM has been an inescapable bedrock of logical reasoning in binary logic. But any digital circuit supporting 3 or more logical states, naturally breaks the LEM. Thus, LEM or even tri-state™ can always be obeyed externally, by a physical constraint on the digital circuits, such as a FPGA or a 74LS241 octal buffer. Albeit, it can be designed with multiple states ( e.g., tri-state™, ‘all states at once’ in QC) in mind. A medical doctor can use QC in his mind while treating classically for a pathology, using available means.

12

Thus, tri-state™ can be abandoned by Intel and others, favoring Field Programmable Gate Arrays (FPGA) [cf. 21].

A software breaking the LEM can run on LEM hardware [22].

The (multiple) existing states are in different dimensions, and a continuous path in a higher dimension (e.g., isolated three states in tri-state™, simultaneous multiple-states in QC) must necessarily map into a discontinuous path in a lower dimension (digital hardware, binary).This happens due to a well-known theorem in topology and projection, that [22] calls Topological

Relationship (TR). See footnote 2.

3. THE OBJECTIVE WAVE MODEL

The DFTM proposes an objective wave model for vibrations, as in subsection 1.4, linking objective periodicity with the factoring of integers, to find prime numbers -- using, e.g., the DFT.

Here, interference makes it easier to measure periodicity objectively, and this should not come as a big surprise. See footnote 5.

Physicists routinely use scattering of physical waves and interference measurements to determine periodicity of physical objects such as crystal lattices.

In an important well-known work, Bennett (the physicist Charles

Bennett, 1973) showed that any classical computation can be transformed into a reversible form, which allows quantum mechanics (QM) to be used in computation, creating quantum computation QC!

This answers the first question of this work, see Introduction:

(1) what role can QM have in QC? The answer is: QM can be

13