So a question I see a lot of people post as having gotten in an interview setting is "Write a function to determine if a number is prime"
The brute force method would be to of course divide some number N by all numbers from 2 to N-1 (easier to implement by checking if N % i == 0).
A slightly smarter approach is to do the same method above but only up to floor(sqrt(N)) which can cut down a good bit.
How many people have broken out the method of determining that N is prime by some extremely high probability using Fermat's little theorem and Miller-Rabin test? I only know of it from cryptography, but it's the only reasonable time complexity algorithm for very large values of N. Wonder if that's overkill for an interview question >_>
Determining if a number is prime (interview setting)
I don't know the fermats theorem nor the miller-rabin test, but you can do this:
- Check if the number is even or odd. Even numbers are never prime as they can be devided by 2 (exception: 2)
- Numbers whose last digit is 5 are not prime (exception: 5).
There are two more of these rules I think, knowing these is enough to determine a prime numner. I think the additional rules have something to do with divinh by 3 and 6, but I'm not sure..
- Check if the number is even or odd. Even numbers are never prime as they can be devided by 2 (exception: 2)
- Numbers whose last digit is 5 are not prime (exception: 5).
There are two more of these rules I think, knowing these is enough to determine a prime numner. I think the additional rules have something to do with divinh by 3 and 6, but I'm not sure..
It's probably overkill for an interview question if you're expected to code it! I wouldn't expect many to have even heard of the Sieve of Atkin, and I've never seen an implementation of it. But if it's just a discussion of theory then if you're told that the number can be big, then it would certainly be a bonus to be able to mention techniques such as Miller-Rabin.
Otherwise, trial division by primes < sqrt(n), or even Sieve of Eratosthenes, would be fine answers I expect.
Otherwise, trial division by primes < sqrt(n), or even Sieve of Eratosthenes, would be fine answers I expect.
Wow, these two techniques were never even mentioned in my cryptography class... in which finding large primes is important to multiple cryptography algorithms.
Thanks for the name drop, I'm going to check these out =)
Thanks for the name drop, I'm going to check these out =)
The sieve of Erathostenes is a correct answer that can be coded on the fly. My answer would be that, and mention deterministic polynomial time tests for an hypothetical "phase 2".
The sieve of Erathostenes is a correct answer that can be coded on the fly. My answer would be that, and mention deterministic polynomial time tests for an hypothetical "phase 2".
This.
I would expect you to stop at floor(sqrt(n)) and know that there are better algorithms for larger numbers. If you went to n-1 or n/2 that would be a red flag. If you thought that was the end-all be-all of algorithms, that would be a smaller red flag (depending on the position). If you knew about the quadratic or number field sieve bonus points (and a follow up question to describe the algorithms to me in layman's terms).
Fermat's theorem is pretty simple, though requires a little modification to be completely accurate.
that is directly out of my code from cryptography class. modexp(a,b, c) being modular exponentiation: a^b % c.
this is also done on a arbitrary size number that this is put into, hence the generation of random bits instead of a random number.
public bool isPrime()
{
bignum a = new bignum();
Random rand = new Random();
bool prime = true;
a.genRandomBits(dataLength * 16, rand);
if (!(modexp(a, this - 1, this) == 1))
prime = false;
return prime;
}
that is directly out of my code from cryptography class. modexp(a,b, c) being modular exponentiation: a^b % c.
this is also done on a arbitrary size number that this is put into, hence the generation of random bits instead of a random number.
that is directly out of my code from cryptography class
You probably don't want to be allocating a Random inside the function. Consider what happens if you call isPrime in a loop. (Just a side point.)
[quote name='Hartra34' timestamp='1320771577' post='4881807']that is directly out of my code from cryptography class
You probably don't want to be allocating a Random inside the function. Consider what happens if you call isPrime in a loop. (Just a side point.)
[/quote]
true, though in this case, the random or the reuse of the random really doesn't matter. Theoretically it could be a constant off the top of my head, I just like using random better.
Fermat's theorem is pretty simple, though requires a little modification to be completely accurate.
public bool isPrime()
{
bignum a = new bignum();
Random rand = new Random();
bool prime = true;
a.genRandomBits(dataLength * 16, rand);
if (!(modexp(a, this - 1, this) == 1))
prime = false;
return prime;
}
that is directly out of my code from cryptography class. modexp(a,b, c) being modular exponentiation: a^b % c.
this is also done on a arbitrary size number that this is put into, hence the generation of random bits instead of a random number.
So...
What is the run-time and space complexity of this algorithm?
What if a == 0? What if it's -1?
How is modulo defined and how is it calculated for negative numbers? What about other languages and architectures, such as built in % operators or idiv?
How could one implement such an algorithm without bignum class?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement