Файл: QCAlgorithmsFastCalculationofPrimeNumbers52.pdf

used in QC. We go from physics to mathematics, as in a “wormhole”! Thanks mainly to Charles Benett.

With the objective wave model, we provide the tools (and some are used here) to answer the second question of this work, see

Introduction: (2) what may QC reveal?

We can use localized, objective oscillations in a DFTM, quantifying both the behavior of chords in terms of physical waves (and frequencies) and of objective numbers -- in a 1:1 model. See footnote 5.

4. THE GCD

The GCD plays a fundamental role in our QC technique. The GCD allows one to use an efficient method for computing the greatest common divisor (GCD) of two integers, to be used here. The GCD is the largest number that divides them both exactly. But it operates with each digit at a time -- although it can be parallelized (see Section 8), it remains non quantum.

Prime numbers can be found by a well-known method, with slow convergence, dating back to Euclid; the Euclidean algorithm -- a way to find the GCD -- named after the ancient Greek mathematician Euclid, who first described it in his Elements (circa 300 BC).

It may be useful to note, in considering the DFTM, that the

Euclidean algorithm itself is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of

14

numbers until the two numbers can become equal. When that occurs, this is the GCD of the original two numbers4.

Generally, the GCD in this case only requires one step per even number, and there are 5 trials per decimal digit. For 617 decimal digits of an RSA-2048) key, this means that breaking RSA-2048 should require less than about 600 steps in hardware when processed in parallel, with just 5 concurrent threads per decimal digit.

The GCD does not even require five times the number of decimal digits of the smaller integer. A special-purpose FPGA can reduce that number to 1 or close.

This contradicts a famous result due to Gabriel Lamé [26], who in 1844 analyzed the complexity of the Euclidean algorithm. Lamé thought that when looking for the GCD of two integers a and b, b being the smaller, the algorithm finishes in at most 5k steps, where k is the number of digits (decimal) of b, also called the b decimal-length. But Lamé did not consider FPGAs, and that a RSA key must include exactly two primes. Finding one, finds the other – immediately.

5. PERIODICITY AND QC

In finding prime numbers by exploring classical periodicity, one can use the GCD with the modular exponential (i.e., mod) function, and it reveals a periodicity on numbers.

This works numerically as follows, which is well-known (and often confused in mathematics; as no one is taking a “bad guess” here).

4 In the field of number theory, one can easily visualize the Euclidean algorithm for the GCD of two natural numbers.

15

Assume that N is positive and has only two distinct prime factors: N = p1p2.

First, one needs to pick an integer a between 2 and N-1, as is well-known. One needs, also, to compute the GCD of (N,a), to the effect that a and N should be coprime.

Second, one has only to choose r to be the known number 2, which is consistent with chord oscillations in round-trips.

At this point, given some number N, knowingly the product of two primes, we are just considering that r is the number 2 (as the least possible number for round-trips).

If the decision on a is reached digit-by-digit, ranging from 2 to N-1, one has a classical (and unbearably slow) method, which is also subject to many errors (see footnote 5). By using QC, one hopes to have a collaborative approach on the decision which best a to use, where all numbers are tried in the same operation (much faster and promising less errors). But, whatever method one uses, one is measuring the same objective quantity: periodicity in a, such that a2 = 1 (mod N).

Just one final number is needed: a.

QC starts with an objective wave model using (e.g.,) the DFTM

-- propagation of waves back and forth in the chord. Following Section 3 and [18-19] for optical applications, where the equation is usually transformed into a large (e.g., 100x100) matrix equation. With these large matrices, matrix evaluation will needlessly calculate 100 modes of the 100x100 matrix, while we want only the first dominant mode. This means that computer time will be used to calculate typically less than 10 actual modes and 90 random-looking collections of points, due

16

to non convergence of the process5 [18-19]. Besides, we have to store large amounts of data in random access memory, [18-19]. We can use the eigenvalue translation method [18], the revisited Prony method [19], the DFT, or other, to achieve a higher efficiency in calculating only the highest mode of the eigenequation modeling the problem. This can now be applied to the problem at hand, estimating the dominant mode of the chord oscillations (see footnote 5) -- and a.

Starting with an arbitrary function ao decomposable through the scalar product in the fp basis:

ao(s) = Σ αi.fi(s), summed over all i, where αi are in the set Q,

(e.g., taking ao(s) = 1, which is valid for any a) we construct the sequence,

ar(s) = Σ αi.αir.fi(s), summed over all i,

where the equation represents either a single-trip for the symmetric modes, or a round-trip for the asymmetric modes, exhausting all possibilities. We unroll the multiplications for faster speed, doing only additions.

We look for r=2 as the smallest integer where (a2 -1) is a multiple of N, i.e, where a2 is 1 (mod N) (e.g., following the efficient code snippet for the mod function in Fig.(3)), thus repeating ao, with a chosen propagation function [e.g.,

5 On selecting a propagation function to use in QC, like the DFT, one is affected by the Nyquist theorem on aliasing, where the propagation analysis suffers from period sub-multiple errors, due to the harmonics that are intrinsic to an interpretation of periodicity applied to the numerical mappings of periodic signals by means of sinusoids. More suitable in terms of estimating periodicity, a frequency spacing method used here, algorithmically, is the DFTM (obeying the empirical conjecture #2), which may or not use [18-19].

17

18-19,21,27] (see footnote 5) -- finding the desired periodicity, e.g., by repeated subtraction6. In the lossless case, the propagation equation represents the usual DFT [21] (see warning in footnote 5). Then, since r=2, one uses the algebra identity in Eq.(1) below:

for the asymmetric modes (round-trip) to split a2 -1. Test that

is not a multiple of N, change a if needed (or, it could be left as a multiple of N and that be taken out trivially with the GCD). In that case, neither is:

a -1 (3)

a multiple of N, although their product is (in the case where the product of N is included, it can be taken out trivially with the GCD).

This is possible only if p1 and p2 are prime factors of N.

We have split a2 - 1 in Eq.(1), non-trivially, and without necessarily using one trial number at each time -- we used a collaborative effect of all possible modes, to find the period --

6 Repeated subtraction is the process of subtracting a number continuously from the large number until the remainder is found -- as zero or lesser than the actual number.

18

through a7. This contradicts [26], and all known references -- we find with the DFTM that only a is needed in QC.

We have objectively considered the contribution of multiple numbers at the same time in QC. Therein lies most of the power of QC -- and avoiding costly matrix algebra, using [18-19] or the DFT [21].

The directive 'all states at once' in QC then becomes quantifiable and causal8, with no mysterious QM, ghostly superpositions, change of r, or non-causal entanglements.

As noted by Spiros Konstantogiannis [23], it is worth noting that when the modulus N is the product of two distinct primes p1,p2, there exist exactly four different solutions for the pair of integers

(ar\2-1,ar\2+1), as it can be seen by setting x= ar\2 and solving the congruence x2=1 (mod N), where N=p1p2. The existence of the previous four solutions is ensured by a well-known theorem in cybersecurity, called the Chinese Remainder Theorem, which is a basic result also in elementary number theory. Two of the four solutions are the trivial ones x=1, N-1, which are present in any case N>1.

The two trivial solutions are excluded in the analysis, since then x-1=0, which is a trivial multiple of the product of two primes, or x+1=N, which is again a multiple of the product of two primes.

7 We targeted in Eq.(1-3) an objective periodicity in the exponential function a, as a collective property of a group of numbers, considered in our QC, to find a better estimate for a – given by the period. In the lossless case, the propagation equation represents the usual DFT -- connecting both techniques of QC. Note that our technique of QC, however, does not use “imaginary numbers” or cryogenics.

8 The numbers 1 or 0 can, e.g., result from 0 + 0, depending on the carry signal.

19

The other two solutions are non-trivial and include pairs (ar\2-1, ar\2+1) of integers where one integer has one of the primes and the other integer has the other prime.

In the special case where the modulus N is the product of two twin primes, i.e. of two primes that differ by 2, for instance, 3 and 5, 5 and 7, 11 and 13, 17 and 19, and so on, one of the two non-trivial solutions can be exactly the pair of the two twin primes, since then the two primes differ by 2, which is equal to the difference of the two integers ar\2+1, ar\2-1 and for this reason such a solution is possible.

The use of twin primes is to be avoided in cryptography. This is well-known to have been exploited recently, to break the encryption algorithm RSA. Therefore, one should sufficiently randomize the two prime numbers, when used to generate stronger RSA keys.

One can also create a plane9. Without assigning any numerical meaning to √-1, one can visualize √-1 as a simple 180 degree rotation, not as an imaginary number or as an irrational number, and use it effectively in mathematics and QM, without contradictions [cf. 1] such as i = -i. This creates the set Q* and deprecates the sets C and G (to be published elsewhere).

6. QC

In viewing prime numbers as not about their effectiveness on factoring (they must, as a theorem of arithmetic), but as two

9 This leads us to consider the famous phrase "a negative times a negative equals a positive" as an easily accessible truth, explored in ResearchGate online discussions. We did this by considering a negative number as a 180 rotation, so their product is a 360 degree rotation, back to positive. One cannot achieve the same ease of visualization by considering a negative number as a "loss", as done in the major movie "Stand and Deliver".

20

types of partition, one of them objective, we can more easily bring in QM and QC in objective and useful (to everyone) terms.

Here, one can use an analogy between primality testing and the resonant condition in physics, so that solving the latter solves the first.

This is similar to the well-known Schor's algorithm for quantum factoring, although less laborious, and not using complex numbers (that we consider fictional in the set Q, cf. [1]). This can provide primality testing in mathematics, by the sole use of objective, physical laws [1]. The resonant condition for two prime numbers leads to N = p1p2 = p.q, where multiples of p and q are avoided naturally, and is in the same form as a RSA public key.

QC becomes one consequence of opening up the "black box" of QM, described in previous results published by the author

[cf. 1, 22]. QM is shown numerically to be exact to more than 101000 decimal digits [16]. QM, therefore, is our most rigorous model of nature!

To be able to use the resonant condition in physics, we need to not consider infinitesimal or irrational differences in frequencies.

This means that we consider the material conjecture #2, and no Problem of Closure [1].

We consider only rational numbers and can differentiate discontinuous functions (not just distributions) -- deprecating most textbooks in analysis [cf. 1]. A new era in mathematics can start.

21

Furthermore, taking advantage of the well-known 1:1 relationship between rational numbers and positive natural numbers (set N), we are led to consider the set N.

In that, similar to computers, we work only with the Boolean set

B={0,1}, and build Bn as is well-known. Thus, imaginary numbers, infinitesimal numbers, and p-adic numbers are not included (i.e., our empirical conjecture #2).

Now, in the Boolean set:

offering instant calculations.

Thus, QC can work fast with 'all states at once', which follows non-Boolean algebra, with even a googol of states. We note that, just considering three logical states, one has many more combinations than with Boolean algebra [22]; for example,

19,683 compared with 16 for binary operators. With any number of logical states, we call that simultaneous multiple-states logic (following ‘all states at once’), the basis of

QC, together with collaborative calculations.

By following a careful 1:1 path from the sets R and C, to N+ and then to the set B={0,1}, where there is no actual calculation by software for any expression, one can easily implement QC. The negative values are handled as explained in Section 8.

Thus, a difficult problem in the set R (or C) is transformed into a trivial problem in the set B, considering QC.

The equivalence of the techniques has been hidden for about 2,500 years – since Pythagoras. One considered illusions, fictional entities, as to “exist”, with imaginary numbers, irrational

22

numbers and infinitesimal numbers appearing in set Q. Instead, we considered our empirical conjecture #2.

We take the position of a digital computer and interpret “to exist” to mean that in a practical sense -- to exist is “it can be constructed from the set B = {0,1}”.

To “exist”, then, is to be calculable numerically by digital hardware. This can happen in a digital computer, or a Field Programmable Array (FPGA), using binary logic with B={0,1} and QC, or three-state logic with A={0,1,X} classically. See Section 2.

Our empirical conjecture #5 is that nature is solving problems only numerically, by finite difference schemes using the set N.

The basis of this conjecture #5 is nature itself. We proposed such solutions to calculate bound states using the Schrödinger equation using the set Q [27] (that we have later re-cast as a difference equation for the curvature [cf. 27]), discovering QC in 1982 [27] -- heralded by an observation 40 years before [27].

This has been used by A. Gerck and E. Gerck in 2023 [29] to confirm most results in Newton’s and Leibiniz’s calculus, while invalidating some. We adopted the calculus by Mādhava, discovered 250 years before Newton -- and so far ignored, even though Newton’s and Leibiniz’s calculus produce no results in the case of discontinuous functions [1]. Mādhava calculus allows discontinuous functions [1], satisfies the Schrödinger equation [cf. 27], opens new results in QM [27], and creates the conditions for discovering QC and using it in calculus [1, 27-28].

23