Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2203.12884 · Advanced Quantum Technologies

Quantum‐Accelerated Algorithms for Generating Random Primitive Polynomials Over Finite Fields

Shan Huang, Hua‐Lei Yin, Zeng‐Bing Chen, Shengjun Wu

Published Nov 3, 2023• 3 citations
arXivHTMLPDF

Abstract

Abstract Primitive polynomials over finite fields are crucial resources with broad applications across various domains in computer science, including classical pseudo‐random number generation, coding theory, and post‐quantum cryptography. Nevertheless, the pursuit of an efficient classical algorithm for generating random primitive polynomials over finite fields remains an ongoing challenge. In this work, it shows how this problem can be solved efficiently with the help of quantum computers. Moreover, the designs of specific quantum circuits to implement them are also presented. The research paves the way for the rapid and real‐time generation of random primitive polynomials in diverse quantum communication and computation applications.

DOI
10.1002/qute.202300302

Related papers

Efficient Quantum Algorithm for Post Quantum Cryptography

Aswini Kumar Mallick, Puspak Pain, Kunal Das +4 more

The realization of Quantum computers could significantly affect society and global security in many ways. A considerable amount of research has been on quantum cryptography - machines that exploit quantum computerized sensations to solve mathematical problems inaccessible to conventional computers. The flourishing 6th generation of 'Quantum computing' can break and threaten much of the current established protection and digital economy, but may provide cryptographic alternatives. Thus, we are able to optimize various processes more effectively, improving efficiency and enabling faster quantum mechanical simulations for better drug and material design, among other applications. This research focuses on implementing a post-quantum cryptographic algorithm by connecting large-number Quantum multiplication with a quantum random number generator (QRNG). A code-based cryptographic approach using a Quantum Fourier Transformation (QFT) is taken with a giant asymmetric key in an explicit quantum circuit to establish a secure quantum communication system. In this research work, a 'plain text' (classical data) has been encrypted with QRNG using a Quantum multiplier with the aid of quantum arithmetic. Consequently, the resultant quantum data with QRNG data will be transmitted to the receiver end through the quantum channel, where the quantum divider decrypts the same. Furthermore, each intended component's IBM Qiskit simulation results and comparative analysis with previous works and algorithms suggest more robustness and reliability of the proposed quantum proof algorithm when considering large qubit quantum devices. The work provides a valuable direction for further developments in this domain and paves the way for future applications of quantum computing in post-quantum cryptography.

Journal of Visualized Experiments•Nov 14, 2025•0 citations

Novel Quantum Random Number Generator for Cryptographical Applications

Maksim Iavich, Tamari Kuchukhidze, Tetyana Okhrimenko +1 more

Random numbers are a fundamental resource in science and engineering, and are also widely used in many fields, such as simulation, cryptography, lotteries, fundamental science. There are algorithmically generated numbers that look like random numbers but are not truly random. These pseudo random numbers are generated from a computer, using deterministic algorithms. Because, we cannot use pseudo random generators in situations, where true randomness is necessary, we use true random number generators. In this case, we use unpredictable random events as a random source. Quantum random number generators (QRNG) output true random numbers based on inherent randomness in quantum measurements. Our goal is to generate fast random numbers at a lower cost. At the same time, a high level of randomness is essential. We present the improved novel quantum random number generator, which is based the on time of arrival QRNG. It is rather efficient, as it uses the simple version of the detectors with rather few requirements. The novel QRNG produces more than one random bit per each photon detection.

International Scientific-Practical Conference Problems of Infocommunications Science and Technology•Oct 6, 2020•4 citations

Improved Real‐Time Post‐Processing for Quantum Random Number Generators

Li Qian, Xiaoming Sun, Xingjian Zhang +1 more

Abstract Randomness extraction is a key problem in cryptography and theoretical computer science. With the recent rapid development of quantum cryptography, quantum‐proof randomness extraction has also been widely studied, addressing the security issues in the presence of a quantum adversary. In contrast with conventional quantum‐proof randomness extractors characterizing the input raw data as min‐entropy sources, it is found that the input raw data generated by a large class of trusted‐device quantum random number generators can be characterized as the so‐called reverse block source. This fact enables us to design improved extractors. Two novel quantum‐proof randomness extractors for reverse block sources that realize real‐time block‐wise extraction are proposed specifically. In comparison with the general min‐entropy randomness extractors, the designs achieve a significantly higher extraction speed and a longer output data length with the same seed length. In addition, they enjoy the property of online algorithms, which process the raw data on the fly without waiting for the entire input raw data to be available. These features make the design an adequate choice for the real‐time post‐processing of practical quantum random number generators. Applying the extractors to the raw data generated by a widely used quantum random number generator, a simulated extraction speed as high as 300 Gbps is achieved.

arXiv:2301.08621•Advanced Quantum Technologies•Apr 29, 2024•4 citations

Quantum Random Number Generators : Benchmarking and Challenges

David Cirauqui, Miguel Ángel García-March, Guillem Guigó i Corominas +5 more

We discuss the current state of the art of Quantum Random Number Generators (QRNG) and their possible applications in the search for quantum advantages. To this aim, we first discuss a possible way of benchmarking QRNG by applying them to the computation of complicated and hard to realize classical simulations, such as critical dynamics in two-dimensional Ising lattices. These are performed with the help of computing devices based on field-programmable gate arrays (FPGAs) or graphic processing units (GPUs). The results obtained for QRNG are compared with those obtained by classical pseudo-random number generators (PRNG) of various qualities. Monte Carlo simulations of critical dynamics in moderate lattice sizes (128$\times$128) start to be sensitive to the correlations present in pseudo-random numbers sequences, allowing us to detect them. By comparing our analysis with that of Ref. [PRE {\bf 93}, 022113 (2016)], we estimate the requirements for QRNGs in terms of speed, rapidity of access, and efficiency to achieve the objective of quantum advantage with respect to the best PRNGs. We discuss the technical challenges associated with this objective.

arXiv:2206.05328•Jun 10, 2022•5 citations

Toward an optimal quantum algorithm for polynomial factorization over finite fields

Javad Dolizkani

We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field F_q, the average-case complexity of our algorithm is an expected O(n^{1 + o(1)} \log^{2 + o(1)}q) bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of O(n^{4/3 + o(1)} \log^{2 + o(1)}q) bit operations. This breaks the classical 3/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.

Quantum Information and Computation•Feb 1, 2019•0 citations

Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields

Javad Doliskani

We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree $n$ over a finite field $\F_q$, the average-case complexity of our algorithm is an expected $O(n^{1 + o(1)} \log^{2 + o(1)}q)$ bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of $O(n^{4 / 3 + o(1)} \log^{2 + o(1)}q)$ bit operations. This breaks the classical $3/2$-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.

arXiv:1807.09675•Jul 25, 2018•0 citations
Abstract Primitive polynomials over finite fields are crucial resources with broad applications across various domains in computer science, including classical pseudo‐random number generation, coding theory, and post‐quantum cryptography. Nevertheless, the pursuit of an efficient classical algorithm for generating random primitive polynomials over finite fields remains an ongoing challenge. In this work, it shows how this problem can be solved efficiently with the help of quantum computers. Moreover, the designs of specific quantum circuits to implement them are also presented. The research paves the way for the rapid and real‐time generation of random primitive polynomials in diverse quantum communication and computation applications.
The realization of Quantum computers could significantly affect society and global security in many ways. A considerable amount of research has been on quantum cryptography - machines that exploit quantum computerized sensations to solve mathematical problems inaccessible to conventional computers. The flourishing 6th generation of 'Quantum computing' can break and threaten much of the current established protection and digital economy, but may provide cryptographic alternatives. Thus, we are able to optimize various processes more effectively, improving efficiency and enabling faster quantum mechanical simulations for better drug and material design, among other applications. This research focuses on implementing a post-quantum cryptographic algorithm by connecting large-number Quantum multiplication with a quantum random number generator (QRNG). A code-based cryptographic approach using a Quantum Fourier Transformation (QFT) is taken with a giant asymmetric key in an explicit quantum circuit to establish a secure quantum communication system. In this research work, a 'plain text' (classical data) has been encrypted with QRNG using a Quantum multiplier with the aid of quantum arithmetic. Consequently, the resultant quantum data with QRNG data will be transmitted to the receiver end through the quantum channel, where the quantum divider decrypts the same. Furthermore, each intended component's IBM Qiskit simulation results and comparative analysis with previous works and algorithms suggest more robustness and reliability of the proposed quantum proof algorithm when considering large qubit quantum devices. The work provides a valuable direction for further developments in this domain and paves the way for future applications of quantum computing in post-quantum cryptography.
Random numbers are a fundamental resource in science and engineering, and are also widely used in many fields, such as simulation, cryptography, lotteries, fundamental science. There are algorithmically generated numbers that look like random numbers but are not truly random. These pseudo random numbers are generated from a computer, using deterministic algorithms. Because, we cannot use pseudo random generators in situations, where true randomness is necessary, we use true random number generators. In this case, we use unpredictable random events as a random source. Quantum random number generators (QRNG) output true random numbers based on inherent randomness in quantum measurements. Our goal is to generate fast random numbers at a lower cost. At the same time, a high level of randomness is essential. We present the improved novel quantum random number generator, which is based the on time of arrival QRNG. It is rather efficient, as it uses the simple version of the detectors with rather few requirements. The novel QRNG produces more than one random bit per each photon detection.
Abstract Randomness extraction is a key problem in cryptography and theoretical computer science. With the recent rapid development of quantum cryptography, quantum‐proof randomness extraction has also been widely studied, addressing the security issues in the presence of a quantum adversary. In contrast with conventional quantum‐proof randomness extractors characterizing the input raw data as min‐entropy sources, it is found that the input raw data generated by a large class of trusted‐device quantum random number generators can be characterized as the so‐called reverse block source. This fact enables us to design improved extractors. Two novel quantum‐proof randomness extractors for reverse block sources that realize real‐time block‐wise extraction are proposed specifically. In comparison with the general min‐entropy randomness extractors, the designs achieve a significantly higher extraction speed and a longer output data length with the same seed length. In addition, they enjoy the property of online algorithms, which process the raw data on the fly without waiting for the entire input raw data to be available. These features make the design an adequate choice for the real‐time post‐processing of practical quantum random number generators. Applying the extractors to the raw data generated by a widely used quantum random number generator, a simulated extraction speed as high as 300 Gbps is achieved.
We discuss the current state of the art of Quantum Random Number Generators (QRNG) and their possible applications in the search for quantum advantages. To this aim, we first discuss a possible way of benchmarking QRNG by applying them to the computation of complicated and hard to realize classical simulations, such as critical dynamics in two-dimensional Ising lattices. These are performed with the help of computing devices based on field-programmable gate arrays (FPGAs) or graphic processing units (GPUs). The results obtained for QRNG are compared with those obtained by classical pseudo-random number generators (PRNG) of various qualities. Monte Carlo simulations of critical dynamics in moderate lattice sizes (128$\times$128) start to be sensitive to the correlations present in pseudo-random numbers sequences, allowing us to detect them. By comparing our analysis with that of Ref. [PRE {\bf 93}, 022113 (2016)], we estimate the requirements for QRNGs in terms of speed, rapidity of access, and efficiency to achieve the objective of quantum advantage with respect to the best PRNGs. We discuss the technical challenges associated with this objective.
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree n over a finite field F_q, the average-case complexity of our algorithm is an expected O(n^{1 + o(1)} \log^{2 + o(1)}q) bit operations. Only for a negligible subset of polynomials of degree nnn our algorithm has a higher complexity of O(n^{4/3 + o(1)} \log^{2 + o(1)}q) bit operations. This breaks the classical 3/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree nnn over a finite field $\F_q$, the average-case complexity of our algorithm is an expected O(n1+o(1)log⁡2+o(1)q)O(n^{1 + o(1)} \log^{2 + o(1)}q)O(n1+o(1)log2+o(1)q) bit operations. Only for a negligible subset of polynomials of degree nnn our algorithm has a higher complexity of O(n4/3+o(1)log⁡2+o(1)q)O(n^{4 / 3 + o(1)} \log^{2 + o(1)}q)O(n4/3+o(1)log2+o(1)q) bit operations. This breaks the classical 3/23/23/2-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.