Wednesday, February 13, 2019

Fastest way to check whether a given number is prime/Semi Prime

Below is my first discovery in the world of prime numbers:

Problem statement
A semi prime (also called biprime or 2-almost prime, or pq number) is a natural number that is the product of two (not necessarily distinct) prime numbers(Source:Wikipedia)
The only way to check whether a given number is prime with 100% probability is finding whether the given number has factors when you iterate between the value “2” and square root of the given number.
The same number of iterations are used to determine whether a given number is semi-prime.
With 100% probability we can check whether a given number is prime/semi-prime, with very very less time complexity.
Below is the process to follow:
1.       Find the cube root of the given number(let’s say this as “n”). Let’s say the cube root is “cn”
2.       Make a list of all the prime numbers till the prime number which is greater than “cn”, but is the least. So if “cn” is “4”, we need to take prime numbers till “5”.
3.       Check any of the prime number in step-2 divides “n”. If yes, then the “n” is neither prime nor semi-prime
4.       If we exhaust all the prime numbers in step-2 and still nothing divides “n”, then “n” is prime or semi-prime
Let’s say we take any number below 10,000 and want to confirm whether it is prime/semi-prime/none.
Cuberoot of 10,000 is 21.544. Rounding off to nearest integer it is 22.
Take the prime numbers till 23(which is the least prime number that is greater than cuberoot of number we want to determine) and see if any of these divides our number. If nothing is able to divide then our number is prime/semi-prime.

In python the implementation will be as below, if we consider first 10,000 positive integers(note the array is initialized to first 9 prime numbers). Any of the first 10,000 positive integers can be evaluated to be prime/semi-prime using the below function. For numbers greater than 10,000 we just need to increment “arr” array.
Below are some of the possible applications for this solution:
1.       To check whether a given number is prime/not requires exponential time complexity as the number grows big. Although our solution results in Semi-primes along with primes, this helps in narrowing down quickly whether the number is not a prime.
2.       Semi-primes are used in RSA algorithm where the multiple of two large primes is used for modulus.
3.       Other applications that use large prime numbers in cyber security

Compared this with miller-rabin test with first 50,000 positive integers and the results generated are the same. Used 40 iterations for miller-rabin test which is minimum required to get good probability for Miller-rabin.
Although the results generated are same with Miller-rabin, the time taken to check whether the given number is prime/Semi-prime and print them with my solution is nearly half. Below are the times in a 1.6 GHZ clockspeed Ubuntu M/c.

Miller-Rabin(In seconds)
Proposed Solution(In Seconds)

No comments:

Post a Comment