A New Efficient Quantum Algorithm for Computing Primality Measure

Gaurav Saxena; Shilpee Srivastava Saxena

doi:https://doi.org/10.14445/22315373/IJMTT-V67I6P504

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 67 | Issue 6 | Year 2021 | Article Id. IJMTT-V67I6P504 | DOI : https://doi.org/10.14445/22315373/IJMTT-V67I6P504

A New Efficient Quantum Algorithm for Computing Primality Measure

Gaurav Saxena, Shilpee Srivastava Saxena

Abstract

In this article we introduce a new concept of Primality Measure based on repeated application of Euler Totient Function. Also, we introduce a new Quantum Algorithm to compute this Primality measure based on Classical Algorithm for Euler Totient Function and Quantum Algorithm for factorization of a number. We next prove that the Classical and Quantum Algorithm used in our New Algorithm (Ramanil Algorithm) are both polynomial time & hence Ramanil Algorithm is also a polynomial time algorithm.

Keywords

Euler Totient Function, Primality Measure, Quantum Algorithms, Classical Algorithms, Polynomial Time Complexity.

References

[1] M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P. Ann. of Math. (2), 160(2) (2004) 781–793.
[2] S. S. Pillai, On a function connected with φ(n), Bull. Amer. Math. Soc. 35(6) (1929) 837–841.
[3] Shor, Peter W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput., 26 (5) (1997) 1484–1509.
[4] G. L. Miller, ‘Riemann’s hypothesis and tests for primality’, J. Comput. System Sci., 13 (1976), 300-317. MR0480295 (58:470a)

Citation :

Gaurav Saxena, Shilpee Srivastava Saxena, "A New Efficient Quantum Algorithm for Computing Primality Measure," International Journal of Mathematics Trends and Technology (IJMTT), vol. 67, no. 6, pp. 35-37, 2021. Crossref, https://doi.org/10.14445/22315373/IJMTT-V67I6P504