unusual and physical methods for finding prime numbers
E. Goles, O. Schulz and M. Markus,
"Prime Number Selection of Cycles In a Predator-Prey Model",
Complexity, 6 No. 4 (2001)
[abstract:]"The fact that some species of cicadas appear every 7, 13, or 17 years and
that these periods are prime numbers has been regarded as a coincidence. We found a simple
evolutionary predator-prey model that yields prime-periodic preys having cycles
predominantly around the observed values. An evolutionary game on a spatial array leads to
travelling waves reminiscent of those observed in excitable systems. The model marks an
encounter of two seemingly unrelated disciplines: biology and number theory. A restriction
to the latter, provides an evolutionary generator of arbitrarily large prime numbers."
Generator of Prime Numbers" [an informal Max Planck Institute report - PDF format]
Johns Hopkins University doctoral candidate Joseph
F. Lawler Jr. was recently awarded a Paul Ehrlich Research Award for his research project "Identifying prime numbers with a
DNA computer" carried out with his sponsor Jef D. Boeke.
The actual manuscript will become available in due course.
J. Tohá and M.A. Soto, "Biochemical
identification of prime numbers", Medical Hypotheses, 53 (4) (October 1999) 361-361
[Abstract:] "A biochemical technique is proposed whereby prime numbers may be identified."
P. Dittrich, W. Banzhaf, H. Rauhe and J. Ziegler,
"Macroscopic and microscopic computation
in an artificial chemistry" (paper presented at Second German Workshops on
Artificial Life (GWAL'97) Dortmund 1997)
One of the examples included of microscopic chemical computation is a "prime number
"In this example we set up a reaction system which produces prime numbers. In addition
we will demonstrate that the population size is critical for a successful compuation. When
increasing the population size a phase transition occurs with respect to the qualitative
behaviour of the system, i.e. to the production of prime numbers."
B. Li, G. Maltese, J.I. Costa-Filho, A.A. Pushkina and A.I. Lvovsky, "An optical Eratosthenes' sieve for large prime numbers" (preprint 10/2019)
[abstract:] "We report the first experimental demonstration of prime number sieve via linear optics. The prime numbers distribution is encoded in the intensity zeros of the far field produced by a spatial light modulator hologram, which comprises a set of diffraction gratings whose periods correspond to all prime numbers below $149$. To overcome the limited far field illumination window and the discretization error introduced by the SLM finite spatial resolution, we rely on additional diffraction gratings and sequential recordings of the far field. This strategy allows us to optically sieve all prime numbers below $149^2 = 22201$."
K. Pelka, J. Graf, T. Mehringer and J. von Zanthier, "Prime number decomposition using the Talbot effect" (preprint 03/2018)
[abstract:] "We report on prime number decomposition by use of the Talbot effect, a well-known phenomenon in classical near field optics whose description is closely related to Gauss sums. The latter are a mathematical tool from number theory used to analyze the properties of prime numbers as well as to decompose composite numbers into their prime factors. We employ the well-established connection between the Talbot effect and Gauss sums to implement prime number decompositions with a novel approach, making use of the longitudinal intensity profile of the Talbot carpet. The new algorithm is experimentally verified and the limits of the approach are discussed."
T.C. Petersen, M. Ceko, I. D. Svalbe, M.J. Morgan, A.I. Bishop and D.M. Paganin, "Simple wave-optical superpositions as prime number sieves" (preprint 12/2018)
[abstract:] "We encode the sequence of prime numbers into simple superpositions of identical waves, mimicking the archetypal prime number sieve of Eratosthenes. The primes are identified as zeros accompanied by phase singularities in a physically generated wave-field for integer valued momenta. Similarly, primes are encoded in the diffraction pattern from a simple single aperture and in the harmonics of a single vibrating resonator. Further, diffraction physics connections to number theory reveal how to encode all Gaussian primes, twin-primes, and how to construct wave fields with amplitudes equal to the divisor function at integer spatial frequencies. Remarkably, all of these basic diffraction phenomena reveal that the naturally irregular sequence of primes can arise from trivially ordered wave superpositions."
Cryptologist Adi Shamir (the "S" in the groundbreaking prime-based "RSA" algorithm) has proposed a design for an opto-electronic
sieving device for finding prime numbers:
R.D. Silverman, An Analysis of Shamir's
Factoring Device", RSA Laboratories Bulletin (May 3, 1999)
[abstract:] "At a Eurocrypt rump session, Professor Adi Shamir of the Weizmann Institute announced the design for an unusual piece
of hardware. This hardware, called "TWINKLE" (which stands for The Weizmann INstitute Key Locating Engine), is an
electro-optical sieving device which will execute sieve-based factoring algorithms approximately two to three orders of
magnitude as fast as a conventional fast PC. The announcement only presented a rough design, and there a number of
practical difficulties involved with fabricating the device. It runs at a very high clock rate (10 GHz), must trigger
LEDs at precise intervals of time, and uses wafer-scale technology. However, it is my opinion that the device is practical
and could be built after some engineering effort is applied to it. Shamir estimates that the device can be fabricated
(after the design process is complete) for about $5,000."
RSA's frequently asked questions
about the TWINKLE device
Notes on D.H.
Lehmer's Photoelectric Number Sieve, built in 1932
a picture of the device
D. Bigourd, B. Chatel, W.P. Schleich and B.Girard, "Factorization of Numbers with the temporal Talbot effect:
Optical implementation by a sequence of shaped ultrashort pulses" (preprint 09/2007)
[abstract:] "We report on the successful operation of an analogue computer designed to factor numbers. Our
device relies solely on the interference of classical light and brings together the field of ultrashort laser pulses with
number theory. Indeed, the frequency component of the electric field corresponding to a sequence of appropriately
shaped femtosecond pulses is determined by a Gauss sum which allows us to find the factors of a number."
V. Tamma, H. Zhang, X. He, A. Garuccio, W.P. Schleich and Y. Shih, "Factoring numbers with a single interferogram" (preprint 06/2015)
[abstract:] "We construct an analog computer based on light interference to encode the hyperbolic function $f(\zeta) = 1/\zeta$ into a sequence of skewed curlicue functions. The resulting interferogram when scaled appropriately allows us to find the prime number decompositions of integers. We implement this idea exploiting polychromatic optical interference in a multipath interferometer and factor seven-digit numbers. We give an estimate for the largest number that can be factored by this scheme."
Wolfram explains how primes can be computed (at least theoretically) using cellular automata
M.V. Suslov, G.B. Lesovik, G. Blatter, "Quantum abacus for counting and factorizing numbers" (preprint 11/2010)
[abstract:] "We generalize the binary quantum counting algorithm of Lesovik, Suslov, and Blatter [Phys. Rev. A 82, 012316 (2010)] to higher counting bases. The algorithm makes use of qubits, qutrits, and qudits to count numbers in a base 2, base 3, or base d representation. In operating the algorithm, the number n < N = d^K is read into a K-qudit register through its interaction with a stream of n particles passing in a nearby wire; this step corresponds to a quantum Fourier transformation from the Hilbert space of particles to the Hilbert space of qudit states. An inverse quantum Fourier transformation provides the number n in the base d representation; the inverse transformation is fully quantum at the level of individual qudits, while a simpler semi-classical version can be used on the level of qudit registers. Combining registers of qubits, qutrits, and qudits, where d is a prime number, with a simpler single-shot measurement allows to find the powers of 2, 3, and other primes d in the number n. We show, that the counting task naturally leads to the shift operation and an algorithm based on the quantum Fourier transformation. We discuss possible implementations of the algorithm using quantum spin-d systems, d-well systems, and their emulation with spin-1/2 or double-well systems. We establish the analogy between our counting algorithm and the phase estimation algorithm and make use of the latter's performance analysis in stabilizing our scheme. Applications embrace a quantum metrological scheme to measure a voltage (analog to digital converter) and a simple procedure to entangle multi-particle states."
J.F. Clauser, J.P. Dowling, "Factoring integers with Young's $N$-slit
interferometer" (preprint 10/2009)
[abstract:] "We show that a Young's $N$ slit interferometer can be used to factor the integer $N$. The device could factor four-
or five-digit numbers in a practical fashion. This work shows how number theory may arise in physical problems, and may provide
some insight as to how quantum computers can carry out factoring problems by interferometric means."
H. Mack, M. Bienert, F. Haug, M. Freyberger and W.P. Schleich, "Wave packets can factorize numbers",
Phys. Stat. Sol. (B) 233, No. 3 (2002) 408-415.
"We draw attention to various aspects of number theory emerging in the time evolution of
elementary quantum systems with quadratic phases. Such model systems can be realized in actual
experiments. Our analysis paves the way to a new, promising and effective method to factorize
G. Mussardo, "The quantum mechanical potential for
the prime numbers", preprint ISAS/EP/97/153;see also R. Matthews,
New Scientist, January 10th, 1998, p.18.
"A simple criterion is derived in order that a number sequence
Sn is a permitted spectrum of a quantised system. The
sequence of prime numbers fulfils the criterion. The existence of such a
potential implies that primality testing can in principle be resolved
by the sole use of physical laws".
P.W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarihtms
on a quantum computer", SIAM J. Computing 26 (1997) 1484-1509.
P.W. Shor, "Quantum computing", Documenta Mathematica Extra Volume ICM I (1998) 467-486
"...A quantum computer is a hypothetical machine based on quantum mechanics. We explain
quantum computing, and give an algorithm for prime factorization on a quantum computer that
runs aymptotically much faster than the best known algorithm on a digital computer...
...In 1994, I showed that a quantum computer could factor large numbers in time polynomial
in the length of the numbers, a nearly exponential speed-up over classical algorithms...the
connection of quantum mechanics with number theory was itself surprising..."
K.Kuriyama, S.Sano and S. Furuichi, "A precise estimation
of the computational complexity in Shor's factoring algorithm" (preprint 06/04)
[abstract:] "A precise estimation of the computational complexity in Shor's factoring
algorithm under the condition that the large integer we want to factorize is composed by
the product of two prime numbers, is derived by the results related to number theory.
compared with Shor's original estimation, our estimation shows that one can obtain the
solution under such a condition, by less computational complexity."
quantum computation to factorise integers
M. Revzen, A. Mann and J. Zak, "Physics
of factorization" (preprint 03/05)
[abstract:] "The N distinct prime numbers that make up a composite number M
allow 2N-1 bi partioning into two relatively prime factors. Each such
pair defines a pair of conjugate representations. These pairs of conjugate representations,
each of which spans the M dimensional space are the familiar complete sets of Zak
transforms (J. Zak, Phys. Rev. Let. 19, 1385 (1967)) which are the most natural
representations for periodic systems. Here we show their relevance to factorizations.
An example is provided for the manifestation of the factorization."
C. Weiss, S. Page, and M. Holthaus, "Factorising
numbers with a Bose-Einstein condensate" (preprint 03/04)
[abstract:] "The problem to express a natural number N as a product of natural numbers without regard
to order corresponds to a thermally isolated non-interacting Bose gas in a one-dimensional potential with logarithmic
energy eigenvalues. This correspondence is used for characterising the probability distribution which governs the
number of factors in a randomly selected factorisation of an asymptotically large N. Asymptotic upper bounds on
both the skewness and the excess of this distribution, and on the total number of factorisations, are conjectured. The
asymptotic formulas are checked against exact numerical data obtained with the help of recursion relations. It is also
demonstrated that for large numbers which are the product of different primes the probability distribution approaches a
Gaussian, while identical prime factors give rise to non-Gaussian statistics."
L. Lacasa, B. Luque, O. Miramontes, "Phase transition and computational
complexity in a stochastic prime number generator" (preprint 12/2007)
[abstract:] "We introduce a prime number generator in the form of a stochastic algorithm. The character of such algorithm gives rise to a
continuous phase transition which distinguishes a phase where the algorithm is able to reduce the whole system of numbers into primes and a phase
where the system reaches a frozen state with low prime density. In this paper we firstly pretend to give a broad characterization of this phase transition,
both in terms of analytical and numerical analysis. Critical exponents are calculated, and data collapse is provided. Further on we redefine the model
as a search problem, fitting it in the hallmark of computational complexity theory. We suggest that the system belongs to the class NP. The
computational cost is maximal around the threshold, as common in many algorithmic phase transitions, revealing the presence of an easy-hard-easy
pattern. We finally relate the nature of the phase transition to an average-case classification of the problem."
excerpts from Chapter 23 of Oliver Sacks' The
Man Who Mistook His Wife for a Hat which documents the astonishing
case of a pair of autistic twins who appear to have direct psychic access
to the "landscape" of prime numbers.