I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? because I want to see if I can use that product as a key in the hash table as well as use it as an (unique) ID.
[Math] Is the product of 2 unique prime number unique
algorithmshash functionprime numbers
Related Solutions
If you know nothing about the distribution of the key $k$, then there is absolutely no argument one could formulate for (or against) taking $m$ prime. There is much of a "feel-good" element in using primes: many authors will promote the practice (often without giving the "technical details" that would explain it) and Hey! even Knuth mentions prime numbers in the context of hashing (forget that he does so in a very particular setting that does not match yours), nobody ever gives an argument against using prime numbers, and there are plenty of them around, so why not choose a prime number? I'll repair one of the points I mentioned: choosing $m=2$ is almost always a very poor choice, even though $2$ is a perfectly bona fide prime number; it just is too small.
If your hashing by just reducing modulo $m$ (which is applicable only if your keys are integers, which severely limits the application contexts), then a hash modulus $m$ is relatively bad (with respect to its size) if somehow your keys are very unevenly distributed modulo $m$. Without knowing anything about the origin of the keys there is no way to know whether this is the case; if the keys are uniformly distributed in some interval much larger than $m$ it will never be the case. However if one surmises that keys are have a non-uniform distribution modulo certain unknown "cursed" numbers, then choosing some $m$ amounts to a gamble that this $m$ happens to not be one of those. It is always possible to lose out on this gamble. One can argue that if $m$ is cursed then so will any multiple of $m$, so choosing $m$ prime in some sense limits the risk to one gamble, while choosing a composite number exposes to the risk of a curse on any of its divisors as well. But you can't make a good argument out of this if one does not substantiate the fear that there are any cursed numbers in the first place. And if a set of (prime) numbers are known to be non-cursed, then taking their product is a safer bet then taking an unknown prime number of about the same magnitude.
But all this is mostly beside the point, because if you don't know the origin of your keys, then hashing by modular reduction is just not a good idea. In practice one should first "scramble" the data in the keys (this is what "hashing" means, actually), and then perform a reduction to map to the size of the table. I've written a general-purpose hashing class whose self-adjusting table size is always a power of $2$, which is an advantage in modular reduction and resizing (no need to hunt for an appropriate new size, just double). Used with a bit of attention to writing data-specific hash functions (if you know some lower order bits are likely to be zero, just don't use them) that ensure a uniform distribution, this works quite well in very large practical computations.
Of any three consecutive integers, one is divisible by $3$. In particular, one of $2^n-1$, $2^n$, and $2^n+1$ is divisible by $3$. But $2^n$ is not divisible by $3$, so one of $2^n-1$ and $2^n+1$ is divisible by $3$.
If $n\gt 2$, then $2^n-1$ and $2^n+1$ are both bigger than $3$. One of them is divisible by $3$ and greater than $3$, so is not prime.
Best Answer
Are you familiar with the Fundamental Theorem of Arithmetic (so, by the FTA, this number would be unique, but maybe this is not sufficient for your application - read on)?
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
Additionally, how many unique IDs do you need?
Have you considered how large of prime numbers you will need to represent that?
Maybe you want to use a product_id || serial_number || date & time-stamp or some mixing like that to guarantee a unique ID.
You can also consider using the new SHA-3 (Keccak) at: http://en.wikipedia.org/wiki/SHA-3 . You can take a large hash value and truncate it (but there is the possibility of collisions), so you can prepend the items above to avoid those.
Also, maybe something like this is what you are after: http://www.javapractices.com/topic/TopicAction.do?Id=56 .
RFC 4122: A Universally Unique IDentifier (UUID), covers this sort of thing and you might want to read it because this is likely what you are after (a secure way to generate a universally unique ID).
For security reasons, Unique identifiers which are "published" in some way may need special treatment, since the identifier may need to be difficult to guess or forge.
Just wanted to throw out some additional thoughts for your consideration given some of the comments and feedback above.
Regards -A