A New Efficient Quantum Algorithm for Computing Primality Measure

  IJMTT-book-cover
 
International Journal of Mathematics Trends and Technology (IJMTT)
 
© 2021 by IJMTT Journal
Volume-67 Issue-6
Year of Publication : 2021
Authors : Gaurav Saxena, Shilpee Srivastava Saxena
  10.14445/22315373/IJMTT-V67I6P504

MLA

MLA Style: Gaurav Saxena, Shilpee Srivastava Saxena  "A New Efficient Quantum Algorithm for Computing Primality Measure" International Journal of Mathematics Trends and Technology 67.6 (2021):35-37. 

APA Style: Gaurav Saxena, Shilpee Srivastava Saxena(2021). A New Efficient Quantum Algorithm for Computing Primality Measure International Journal of Mathematics Trends and Technology, 35-37.

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.

Reference

[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)

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