Abstract

We report the first experimental demonstration of a 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 spatial light modulator 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 1492 = 22201.

© 2020 Optical Society of America under the terms of the OSA Open Access Publishing Agreement

Full Article  |  PDF Article
OSA Recommended Articles
Nanoplasmonics of prime number arrays

Carlo Forestiere, Gary F. Walsh, Giovanni Miano, and Luca Dal Negro
Opt. Express 17(26) 24288-24303 (2009)

Prime number decomposition using the Talbot effect

Karl Pelka, Jasmin Graf, Thomas Mehringer, and Joachim von Zanthier
Opt. Express 26(12) 15009-15014 (2018)

Ultra-large multi-region photon sieves

Zhifeng Chen, Chinhua Wang, Donglin Pu, Jin Hu, and Linsen Chen
Opt. Express 18(15) 16279-16288 (2010)

References

  • View by:
  • |
  • |
  • |

  1. A. E. Ingham, The distribution of prime numbers (Cambridge University, 1990).
  2. H. M. Edwards, Riemann’s Zeta Function (Dover Publications, 2001).
  3. R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
    [Crossref]
  4. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) (CRC Press, 1996).
  5. P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26(5), 1484–1509 (1997).
    [Crossref]
  6. D. Schumayer and D. A. W. Hutchinson, “Colloquium: Physics of the Riemann hypothesis,” Rev. Mod. Phys. 83(2), 307–330 (2011).
    [Crossref]
  7. C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
    [Crossref]
  8. L. A. Bunimovich and C. P. Dettmann, “Open circular billiards and the Riemann hypothesis,” Phys. Rev. Lett. 94(10), 100201 (2005).
    [Crossref]
  9. M. V. Berry and J. P. Keating, “The Riemann zeros and eigenvalue asymptotics,” SIAM Rev. 41(2), 236–266 (1999).
    [Crossref]
  10. A. A. Rangelov, “Factorizing numbers with classical interference: several implementations in optics,” J. Phys. B: At., Mol. Opt. Phys. 42(2), 021002 (2009).
    [Crossref]
  11. J. F. Clauser and J. P. Dowling, “Factoring integers with Young’s n-slit interferometer,” Phys. Rev. A 53(6), 4587–4590 (1996).
    [Crossref]
  12. A. Shamir, “Factoring large numbers with the TWINKLE device,” International Workshop on Cryptographic Hardware and Embedded Systems (Springer, 1999), pp. 2–12.
  13. 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,” Phys. Rev. Lett. 100(3), 030202 (2008).
    [Crossref]
  14. K. Pelka, J. Graf, T. Mehringer, and J. von Zanthier, “Prime number decomposition using the Talbot effect,” Opt. Express 26(12), 15009–15014 (2018).
    [Crossref]
  15. V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
    [Crossref]
  16. M. V. Berry, “Riemann zeros in radiation patterns,” J. Phys. A: Math. Theor. 45(30), 302001 (2012).
    [Crossref]
  17. M. V. Berry, “Riemann zeros in radiation patterns: II. Fourier transforms of zeta,” J. Phys. A: Math. Theor. 48(38), 385203 (2015).
    [Crossref]
  18. 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,” Phys. Rev. Lett. 122(9), 090201 (2019).
    [Crossref]
  19. R. Crandall and C. B. Pomerance, Prime numbers: a computational perspective (Springer Science & Business Media, 2006), 2nd ed.
  20. T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
    [Crossref]

2019 (1)

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

2018 (1)

2017 (1)

C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
[Crossref]

2015 (1)

M. V. Berry, “Riemann zeros in radiation patterns: II. Fourier transforms of zeta,” J. Phys. A: Math. Theor. 48(38), 385203 (2015).
[Crossref]

2012 (1)

M. V. Berry, “Riemann zeros in radiation patterns,” J. Phys. A: Math. Theor. 45(30), 302001 (2012).
[Crossref]

2011 (2)

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

D. Schumayer and D. A. W. Hutchinson, “Colloquium: Physics of the Riemann hypothesis,” Rev. Mod. Phys. 83(2), 307–330 (2011).
[Crossref]

2010 (1)

T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
[Crossref]

2009 (1)

A. A. Rangelov, “Factorizing numbers with classical interference: several implementations in optics,” J. Phys. B: At., Mol. Opt. Phys. 42(2), 021002 (2009).
[Crossref]

2008 (1)

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

2005 (1)

L. A. Bunimovich and C. P. Dettmann, “Open circular billiards and the Riemann hypothesis,” Phys. Rev. Lett. 94(10), 100201 (2005).
[Crossref]

1999 (1)

M. V. Berry and J. P. Keating, “The Riemann zeros and eigenvalue asymptotics,” SIAM Rev. 41(2), 236–266 (1999).
[Crossref]

1997 (1)

P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26(5), 1484–1509 (1997).
[Crossref]

1996 (1)

J. F. Clauser and J. P. Dowling, “Factoring integers with Young’s n-slit interferometer,” Phys. Rev. A 53(6), 4587–4590 (1996).
[Crossref]

1978 (1)

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
[Crossref]

Adleman, L.

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
[Crossref]

Bender, C. M.

C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
[Crossref]

Berry, M. V.

M. V. Berry, “Riemann zeros in radiation patterns: II. Fourier transforms of zeta,” J. Phys. A: Math. Theor. 48(38), 385203 (2015).
[Crossref]

M. V. Berry, “Riemann zeros in radiation patterns,” J. Phys. A: Math. Theor. 45(30), 302001 (2012).
[Crossref]

M. V. Berry and J. P. Keating, “The Riemann zeros and eigenvalue asymptotics,” SIAM Rev. 41(2), 236–266 (1999).
[Crossref]

Bigourd, D.

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

Bishop, A. I.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Brody, D. C.

C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
[Crossref]

Bunimovich, L. A.

L. A. Bunimovich and C. P. Dettmann, “Open circular billiards and the Riemann hypothesis,” Phys. Rev. Lett. 94(10), 100201 (2005).
[Crossref]

Ceko, M.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Chatel, B.

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

Cižmár, T.

T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
[Crossref]

Clauser, J. F.

J. F. Clauser and J. P. Dowling, “Factoring integers with Young’s n-slit interferometer,” Phys. Rev. A 53(6), 4587–4590 (1996).
[Crossref]

Crandall, R.

R. Crandall and C. B. Pomerance, Prime numbers: a computational perspective (Springer Science & Business Media, 2006), 2nd ed.

Dettmann, C. P.

L. A. Bunimovich and C. P. Dettmann, “Open circular billiards and the Riemann hypothesis,” Phys. Rev. Lett. 94(10), 100201 (2005).
[Crossref]

Dholakia, K.

T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
[Crossref]

Dowling, J. P.

J. F. Clauser and J. P. Dowling, “Factoring integers with Young’s n-slit interferometer,” Phys. Rev. A 53(6), 4587–4590 (1996).
[Crossref]

Edwards, H. M.

H. M. Edwards, Riemann’s Zeta Function (Dover Publications, 2001).

Garuccio, A.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

Girard, B.

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

Graf, J.

He, X.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

Hutchinson, D. A. W.

D. Schumayer and D. A. W. Hutchinson, “Colloquium: Physics of the Riemann hypothesis,” Rev. Mod. Phys. 83(2), 307–330 (2011).
[Crossref]

Ingham, A. E.

A. E. Ingham, The distribution of prime numbers (Cambridge University, 1990).

Keating, J. P.

M. V. Berry and J. P. Keating, “The Riemann zeros and eigenvalue asymptotics,” SIAM Rev. 41(2), 236–266 (1999).
[Crossref]

Mazilu, M.

T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
[Crossref]

Mehringer, T.

Menezes, A. J.

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) (CRC Press, 1996).

Morgan, M. J.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Müller, M. P.

C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
[Crossref]

Paganin, D. M.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Pelka, K.

Petersen, T. C.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Pomerance, C. B.

R. Crandall and C. B. Pomerance, Prime numbers: a computational perspective (Springer Science & Business Media, 2006), 2nd ed.

Rangelov, A. A.

A. A. Rangelov, “Factorizing numbers with classical interference: several implementations in optics,” J. Phys. B: At., Mol. Opt. Phys. 42(2), 021002 (2009).
[Crossref]

Rivest, R. L.

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
[Crossref]

Schleich, W. P.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

Schumayer, D.

D. Schumayer and D. A. W. Hutchinson, “Colloquium: Physics of the Riemann hypothesis,” Rev. Mod. Phys. 83(2), 307–330 (2011).
[Crossref]

Shamir, A.

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
[Crossref]

A. Shamir, “Factoring large numbers with the TWINKLE device,” International Workshop on Cryptographic Hardware and Embedded Systems (Springer, 1999), pp. 2–12.

Shih, Y.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

Shor, P.

P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26(5), 1484–1509 (1997).
[Crossref]

Svalbe, I. D.

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

Tamma, V.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

van Oorschot, P. C.

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) (CRC Press, 1996).

Vanstone, S. A.

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) (CRC Press, 1996).

von Zanthier, J.

Zhang, H.

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

Commun. ACM (1)

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21(2), 120–126 (1978).
[Crossref]

J. Phys. A: Math. Theor. (2)

M. V. Berry, “Riemann zeros in radiation patterns,” J. Phys. A: Math. Theor. 45(30), 302001 (2012).
[Crossref]

M. V. Berry, “Riemann zeros in radiation patterns: II. Fourier transforms of zeta,” J. Phys. A: Math. Theor. 48(38), 385203 (2015).
[Crossref]

J. Phys. B: At., Mol. Opt. Phys. (1)

A. A. Rangelov, “Factorizing numbers with classical interference: several implementations in optics,” J. Phys. B: At., Mol. Opt. Phys. 42(2), 021002 (2009).
[Crossref]

Nat. Photonics (1)

T. Čižmár, M. Mazilu, and K. Dholakia, “In situ wavefront correction and its application to micromanipulation,” Nat. Photonics 4(6), 388–394 (2010).
[Crossref]

Opt. Express (1)

Phys. Rev. A (2)

J. F. Clauser and J. P. Dowling, “Factoring integers with Young’s n-slit interferometer,” Phys. Rev. A 53(6), 4587–4590 (1996).
[Crossref]

V. Tamma, H. Zhang, X. He, A. Garuccio, W. P. Schleich, and Y. Shih, “Factoring numbers with a single interferogram,” Phys. Rev. A 83(2), 020304 (2011).
[Crossref]

Phys. Rev. Lett. (4)

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,” Phys. Rev. Lett. 100(3), 030202 (2008).
[Crossref]

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,” Phys. Rev. Lett. 122(9), 090201 (2019).
[Crossref]

C. M. Bender, D. C. Brody, and M. P. Müller, “Hamiltonian for the zeros of the Riemann zeta function,” Phys. Rev. Lett. 118(13), 130201 (2017).
[Crossref]

L. A. Bunimovich and C. P. Dettmann, “Open circular billiards and the Riemann hypothesis,” Phys. Rev. Lett. 94(10), 100201 (2005).
[Crossref]

Rev. Mod. Phys. (1)

D. Schumayer and D. A. W. Hutchinson, “Colloquium: Physics of the Riemann hypothesis,” Rev. Mod. Phys. 83(2), 307–330 (2011).
[Crossref]

SIAM J. Comput. (1)

P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26(5), 1484–1509 (1997).
[Crossref]

SIAM Rev. (1)

M. V. Berry and J. P. Keating, “The Riemann zeros and eigenvalue asymptotics,” SIAM Rev. 41(2), 236–266 (1999).
[Crossref]

Other (5)

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) (CRC Press, 1996).

A. E. Ingham, The distribution of prime numbers (Cambridge University, 1990).

H. M. Edwards, Riemann’s Zeta Function (Dover Publications, 2001).

R. Crandall and C. B. Pomerance, Prime numbers: a computational perspective (Springer Science & Business Media, 2006), 2nd ed.

A. Shamir, “Factoring large numbers with the TWINKLE device,” International Workshop on Cryptographic Hardware and Embedded Systems (Springer, 1999), pp. 2–12.

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (6)

Fig. 1.
Fig. 1. Light intensity profiles at near (a) and far (b) fields, for $n=5$ pinholes per unit length. Red arrows represent an infinite array of pinholes and the corresponding effect on the far field. When this array is restricted to five pinholes [which corresponds to multiplication by the blue envelope in (a)], the far field pattern (which is the result of a Fourier transformation $\mathscr {F}$ of the near field) becomes convolved with a sinc function, but the intensity at all integers except multiples of 5 remains at zero.
Fig. 2.
Fig. 2. Optical sieve diffraction mask (left) in the case of $\{n\}=\{2,3,5,7\}$. The square root of the corresponding far field intensity profile (centre) and its horizontal marginal (integral over $q_y$, right), which reveals the prime numbers in the intensity zeros, highlighted by vertical grey lines. (a) Sieving mask proposed in [18], composed of point-like apertures. (b) Sieving mask with finite-size rectangular apertures of width $w=1/42$. (c) Sieving mask superposed with displacement grating, which shifts the primes distribution by $d_x=50$.
Fig. 3.
Fig. 3. Experimental implementation of the optical prime sieve. a) Scheme of the experiment. b) Phase mask hologram as displayed on the SLM screen.
Fig. 4.
Fig. 4. Experimental results. a) Far field intensity images as acquired by the camera for different displacement grating slopes $d_x$, rescaled into the units of $q_x,q_y$. b) Integrals of the acquired intensity images along $q_y$. All minima below the intensity threshold $\epsilon$ (horizontal red line) are classified as prime numbers (vertical grey lines).
Fig. 5.
Fig. 5. Effect of the SLM’s spatial resolution on the produced far field intensity profile for $n=11$ and a displacement grating of slope $d_x=180$ (theoretical model). (a) Evenly spaced apertures (infinite resolution); (b) Discrete pixels with a total pattern width of $W=420$ pixels: the apertures are spaced by either $38$ or $39$ pixels. The integers not multiples of 11 are no longer zeros in the far field intensity profile. (c) $W=420$ with a displacement grating of slope $d^{(11)}_x=180 \mod 11 =4$: the desired structure of the far field is closely restored.
Fig. 6.
Fig. 6. Number of misclassified primes (red squares) and composites (blue dots) within the measured sieving range $139 < q_x <22201$ as a function of the intensity threshold $\epsilon$. By choosing $0.048 < \epsilon < 0.059$, the optical sieve correctly sieves all primes and discards composites.

Equations (7)

Equations on this page are rendered with MathJax. Learn more.

g n ( x ) = i = 0 n 1 δ ( x i / n ) ,
g ~ n ( q x ) = g n ( x ) e 2 π i x q x d x ,
g ~ n ( q x ) = ( n j = δ ( q x n j ) ) sinc ( q x ) ,
E n ( x ) = g n ( x ) T w ( x ) ,
g n ( x ) = g n ( x ) e i 2 π x d x .
g ~ n ( q x ) = g ~ n ( q x d x )
E ~ n ( x ) = g ~ n ( q x ) w sinc ( w q x ) .

Metrics