An advanced technique for primality test with quantum computation and its relevance in cryptography

Abstract

Several classical algorithms exist to detect prime numbers. All such algorithms are NP-hard. In the Quantum Computation domain also, a few algorithms like Shor’s Algorithm exist, which are mainly based on the quantum version of Discrete Fourier Transformation. In this thesis a different approach (i.e. other than Fourier Transformation) has been made to detect Safe prime and Sophie Germain prime by establishing a correlation between balanced -constant function & prime number. Here we use the concept of balanced and constant function i.e. promise algorithm or more precisely, a type of Deutsch Jozsa (DJ) algorithm, a generalized version of Deutsch’s algorithm. Shor’s algorithm has been integrated with the quantum concept of Phi function to overcome its limitations. We have concentrated on detecting the prime property of a number i.e. ‘a given number is prime or not’ without having any interest in identifying its factors.