Below is my first discovery in the world of prime numbers:
Problem statement
A semi prime (also called biprime or
2almost 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 semiprime.
Solution
With 100% probability we can check whether
a given number is prime/semiprime, 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 step2 divides “n”. If yes, then the “n” is neither prime nor
semiprime
4.
If we exhaust all the
prime numbers in step2 and still nothing divides “n”, then “n” is prime or
semiprime
Example
Let’s say we take any number below 10,000
and want to confirm whether it is prime/semiprime/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/semiprime.
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/semiprime using the below function. For
numbers greater than 10,000 we just need to increment “arr” array.
Impact
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 Semiprimes along with primes, this
helps in narrowing down quickly whether the number is not a prime.
2.
Semiprimes 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 millerrabin test with first 50,000
positive integers and the results generated are the same. Used 40 iterations
for millerrabin test which is minimum required to get good probability for
Millerrabin.
Although the results generated are same with Millerrabin,
the time taken to check whether the given number is prime/Semiprime and print
them with my solution is nearly half. Below are the times in a 1.6 GHZ
clockspeed Ubuntu M/c.
MillerRabin(In seconds)

Proposed Solution(In Seconds)


Real

0.497

0.227

User

0.188

0.183

Sys

0.026

0.025

No comments:
Post a Comment