© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Applied Optics

Design and implementation of a parallel Stein algorithm based on a ternary optical computer

Kai Song, Jingyang Wei, Huanyu Hu, Xinjun Hou, Liping Yan, Sulan Zang

Published Jul 21, 2025• 1 citation

Abstract

The Stein algorithm is used to solve the problem that the Euclidean algorithm is inefficient when dealing with large integers, and it is widely used in mathematics, physics, and cryptography. When the algorithm is implemented on a traditional electronic computer, the problems of slow computation speed, low computational efficiency, and large space occupation become more evident with the increase in the number of integer bits and the improvement of precision demands. The ternary optical computer (TOC), with low power consumption, abundant data bits, ease of expansion, and bitwise reconstruction, can solve these problems. In this study, a parallel Stein algorithm based on TOC is proposed by analyzing the Stein algorithm and identifying the parts of the algorithm that can be computed in parallel. The algorithm employs the parity judge to determine the parity of the data and calculates the intra-group greatest common divisor of each group of data in parallel by reconstructing the composite arithmetic and MSD multiplier, with the final value being the greatest common divisor of all the data. By analyzing the energy consumption and clock cycles of the parallel algorithm and through experimental verification, it is concluded that the parallel Stein algorithm based on TOC exhibits good time performance and operational efficiency, fully leveraging the advantages of TOC in computing.

DOI: 10.1364/ao.545874

Related papers

Algorithm of Walsh-Hadamard Transform with Optical Approach

Yunfu Shen

In this paper, the fast algorithm to Walsh-Hadamard transform (WHT) is studied from the point of view of the optical computation. Firstly, MSD addition and butterfly calculation in discrete WHT are presented in detail. Then the design and implementation scheme of fast algorithm of WHT is proposed and the software simulations to fast WHT are carried out optically. Meanwhile, the computational complexity of the algorithms in time and space are analyzed. The analysis shows that the problem of WHT with large-scale data can be solved in a few of clock cycles with optical computational method. The scheme also provides a good way for the design of fast optical Walsh-Hadamard transformer and an application in ternary optical computer.

Journal of Information and Computational Science•Sep 20, 2013•3 citations

Experimental Implementation of Shor's Quantum Algorithm to Break RSA

Aminah Albuainain, Jana Alansari, Samiyah Alrashidi +3 more

Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.

International Conference on Computational Intelligence and Communication Networks (CICN)•Dec 4, 2022•12 citations

An Optical Parallel System for Prime Factorization

Kouichi Nitta, Nobuto Katsuta, Osamu Matoba

A system for prime factorization with optical modulo operations is developed and demonstrated. In the system, two-dimensional parallel processing is employed to achieve large-scale information processing for modulo multiplication, which is one of the important elements in an algorithm for prime factorization. This optical component is implemented on a Michelson interferometer. Electronic signal processing for pre-processing, postprocessing, and control of optical hardware is prepared as graphic user interface (GUI) software. With the constructed system, effective results can be obtained using the proposed method.

Japanese Journal of Applied Physics•Sep 24, 2009•4 citations

Speed improvement of the quantum factorization algorithm of P. Shor by upgrade its classical part

Larissa V. Cherckesova, Olga Alexandrovna Safaryan, Разумов Павел Владимирович +3 more

This report discusses Shor’s quantum factorization algorithm and ρ–Pollard’s factorization algorithm. Shor’s quantum factorization algorithm consists of classical and quantum parts. In the classical part, it is proposed to use Euclidean algorithm, to find the greatest common divisor (GCD), but now exist large number of modern algorithms for finding GCD. Results of calculations of 8 algorithms were considered, among which algorithm with lowest execution rate of task was identified, which allowed the quantum algorithm as whole to work faster, which in turn provides greater potential for practical application of Shor’s quantum algorithm. Standard quantum Shor’s algorithm was upgraded by replacing the binary algorithm with iterative shift algorithm, canceling random number generation operation, using additive chain algorithm for raising to power. Both Shor’s algorithms (standard and upgraded) are distinguished by their high performance, which proves much faster and insignificant increase in time in implementation of data processing. In addition, it was possible to modernize Shor’s quantum algorithm in such way that its efficiency turned out to be higher than standard algorithm because classical part received an improvement, which allows an increase in speed by 12%.

E3S Web of Conferences•Jan 1, 2020•1 citation

Optical quantum computing

Dongyang Wang, Junjie Wu, Xun Yi

Quantum computing offers a much more efficient way of computation than its classical counterpart, due to the specific characters in quantum mechanics. To realize quantum computers, one must find a specific physical system as a platform. Available systems include atoms, electrons, ions, photons and so on. Photons are easier to manipulate and have a better coherence. This article studies on the basic concepts of optical quantum computing, and then introduces the optical implementation of Shor's quantum factoring algorithm, along with some other present applications, to show the promising future of optical quantum computing.

International Conference on Natural Computation (ICNC)•Aug 1, 2015•11 citations

Implementation of 5-Qubit approach-based Shor's Algorithm in IBM Qiskit

G. R. Mounica, G. Manimaran, Lauret Jerome +1 more

RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.

IEEE Pune Section International Conference (PuneCon)•Dec 16, 2021•17 citations

The Stein algorithm is used to solve the problem that the Euclidean algorithm is inefficient when dealing with large integers, and it is widely used in mathematics, physics, and cryptography. When the algorithm is implemented on a traditional electronic computer, the problems of slow computation speed, low computational efficiency, and large space occupation become more evident with the increase in the number of integer bits and the improvement of precision demands. The ternary optical computer (TOC), with low power consumption, abundant data bits, ease of expansion, and bitwise reconstruction, can solve these problems. In this study, a parallel Stein algorithm based on TOC is proposed by analyzing the Stein algorithm and identifying the parts of the algorithm that can be computed in parallel. The algorithm employs the parity judge to determine the parity of the data and calculates the intra-group greatest common divisor of each group of data in parallel by reconstructing the composite arithmetic and MSD multiplier, with the final value being the greatest common divisor of all the data. By analyzing the energy consumption and clock cycles of the parallel algorithm and through experimental verification, it is concluded that the parallel Stein algorithm based on TOC exhibits good time performance and operational efficiency, fully leveraging the advantages of TOC in computing.

In this paper, the fast algorithm to Walsh-Hadamard transform (WHT) is studied from the point of view of the optical computation. Firstly, MSD addition and butterfly calculation in discrete WHT are presented in detail. Then the design and implementation scheme of fast algorithm of WHT is proposed and the software simulations to fast WHT are carried out optically. Meanwhile, the computational complexity of the algorithms in time and space are analyzed. The analysis shows that the problem of WHT with large-scale data can be solved in a few of clock cycles with optical computational method. The scheme also provides a good way for the design of fast optical Walsh-Hadamard transformer and an application in ternary optical computer.

Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.

A system for prime factorization with optical modulo operations is developed and demonstrated. In the system, two-dimensional parallel processing is employed to achieve large-scale information processing for modulo multiplication, which is one of the important elements in an algorithm for prime factorization. This optical component is implemented on a Michelson interferometer. Electronic signal processing for pre-processing, postprocessing, and control of optical hardware is prepared as graphic user interface (GUI) software. With the constructed system, effective results can be obtained using the proposed method.

This report discusses Shor’s quantum factorization algorithm and ρ–Pollard’s factorization algorithm. Shor’s quantum factorization algorithm consists of classical and quantum parts. In the classical part, it is proposed to use Euclidean algorithm, to find the greatest common divisor (GCD), but now exist large number of modern algorithms for finding GCD. Results of calculations of 8 algorithms were considered, among which algorithm with lowest execution rate of task was identified, which allowed the quantum algorithm as whole to work faster, which in turn provides greater potential for practical application of Shor’s quantum algorithm. Standard quantum Shor’s algorithm was upgraded by replacing the binary algorithm with iterative shift algorithm, canceling random number generation operation, using additive chain algorithm for raising to power. Both Shor’s algorithms (standard and upgraded) are distinguished by their high performance, which proves much faster and insignificant increase in time in implementation of data processing. In addition, it was possible to modernize Shor’s quantum algorithm in such way that its efficiency turned out to be higher than standard algorithm because classical part received an improvement, which allows an increase in speed by 12%.

Quantum computing offers a much more efficient way of computation than its classical counterpart, due to the specific characters in quantum mechanics. To realize quantum computers, one must find a specific physical system as a platform. Available systems include atoms, electrons, ions, photons and so on. Photons are easier to manipulate and have a better coherence. This article studies on the basic concepts of optical quantum computing, and then introduces the optical implementation of Shor's quantum factoring algorithm, along with some other present applications, to show the promising future of optical quantum computing.

RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.