Abstract

We apply optical parallel processing to operations for multiplication modulo, which is one of the key components of a factorization algorithm. With this method, optical phase modulation provides the results of modulo operations. We construct a prototype system based on a Michelson interferometer with a photodetector array. Mirrors are set at both object and reference arms to generate interference fringes. A mirror in the object arm is tilted slightly, whereas the reference arm is set perpendicular to the optical axis. The tilt angle is determined by parameters for the target modulo operations. The presented system can achieve massive data processing in parallel with only simple implementation. We present our experimental results to verify the usefulness of our method.

© 2008 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |

  1. D. T. Neilson, S. M. Prince, D. A. Baillie, and F. A. P. Tooley, "Optical design of a 1024-channel free-space sorting demonstrator," Appl. Opt. 36, 9243-9252 (1997).
    [CrossRef]
  2. A. Huang, Y. Tsunoda, J. W. Goodman, and S. Ishihara, "Optical computation using residue arithmetic," Appl. Opt. 18, 149-162 (1979).
    [CrossRef] [PubMed]
  3. K. Nitta, K. Kagawa, and J. Tanida, "Design and fabrication of pipelined digital correlator for opto-electronic discrete correlation processor," IEICE Trans. Electron. E84-C, 312-317 (2001).
  4. P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proceedings of the 35th Annual Symposium on Foundations of Computer Science 1898, 124-134 (1994).
  5. V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Phys. Rev. A 54, 147-153 (1996).
    [CrossRef] [PubMed]
  6. J. Gruska, Quantum Computing (McGraw-Hill, 1999).
  7. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (MIT Press, 1990).

2001

K. Nitta, K. Kagawa, and J. Tanida, "Design and fabrication of pipelined digital correlator for opto-electronic discrete correlation processor," IEICE Trans. Electron. E84-C, 312-317 (2001).

1997

1996

V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Phys. Rev. A 54, 147-153 (1996).
[CrossRef] [PubMed]

1979

Appl. Opt.

IEICE Trans. Electron.

K. Nitta, K. Kagawa, and J. Tanida, "Design and fabrication of pipelined digital correlator for opto-electronic discrete correlation processor," IEICE Trans. Electron. E84-C, 312-317 (2001).

Phys. Rev. A

V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Phys. Rev. A 54, 147-153 (1996).
[CrossRef] [PubMed]

Other

J. Gruska, Quantum Computing (McGraw-Hill, 1999).

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (MIT Press, 1990).

P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proceedings of the 35th Annual Symposium on Foundations of Computer Science 1898, 124-134 (1994).

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

Brief procedure of an algorithm for prime factorization utilizing an exponentiation modulo.

Fig. 2
Fig. 2

Schematic diagram of a method for multiplier modulo operations by use of optical interference.

Fig. 3
Fig. 3

(Color online) Schematic diagram of an optical interferometer for parallel multiplier modulo operations.

Fig. 4
Fig. 4

Photograph of the prototype system.

Fig. 5
Fig. 5

Relation between time step and pixel positions to measure the desired results of exponentiation modulo operations.

Fig. 6
Fig. 6

Example of the experimental results: (a) parts of an experimental result obtained by the constructed system at N and a set to 55 and 3, respectively, and (b) two times power spectrum of the profile shown in (a).

Tables (1)

Tables Icon

Table 1 Relation between I ( x ) and Pixel Positions

Equations (21)

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

N = p q .
0 < a < N ,
gcd ( a , N ) = 1 .
f ( x ) = a x   mod   N .
p = gcd ( a r / 2 1 , N ) ,
q = gcd ( a r / 2 + 1 , N ) .
a x = a 2 n 1 × x n 1 × a 2 n 2 × x n 2 × × a 2 1 × x 1 × a 2 0 × x 0 .
f ( x ) = ( a 2 n 1 × x n 1 × a 2 n 2 × x n 2 × × a 2 1 × x 1 × a 2 0 × x 0 ) × mod   N = ( a 2 n 1 × x n 1   mod   N ) × × ( a 2 1 × x 1   mod   N ) × ( a 2 0 × x 0   mod   N ) mod   N = ( { [ l ( n 1 ) × l ( n 2 ) mod   N ] × × l ( 1 ) × mod   N } × l ( 0 ) ) mod   N .
l ( i ) = a 2 i   mod   N .
s = t u + v .
v = s   mod   u .
U ( ϕ ) = exp ( i 2 π λ ϕ ) ,
U ( s ) = exp ( i 2 π λ s λ u ) = exp [ i 2 π ( t + v u ) ] = exp ( i 2 π v u ) .
g ( x ) = a x   mod   N .
U o [ r + Δ r ( θ , p ) ] = A   exp ( ( { i 2 π λ [ r + Δ r ( θ , p ) ] } ) ) ,
U r ( r ) = A   exp ( i 2 π λ r ) .
Δ r ( θ , p ) = p D   sin   θ .
I ( p , θ ) = 2 A 2 [ 1 + cos ( 2 π λ p D   sin   θ ) ] .
D   sin   2 α = a N λ ,
g ( p ) = a p   mod   N .
α ( i ) = 1 2 sin 1 [ l ( i ) λ N ] .

Metrics