Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is your pair of primes ordered? In that case $(p,q)$ and $(q,p)$ obviously have the same product. –  ronno Dec 13 '12 at 17:55
5  
See the Fundamental theorem of arithmetic. –  Raymond Manzoni Dec 13 '12 at 17:56
    
Since you are combining only primes, it would be unique. –  gt6989b Dec 13 '12 at 17:56
2  
Nice question, that it took a surprisingly long time for mathematicians to ask. In the ordinary integers, (apart from order) there is uniqueness. First proof is due to Gauss. –  André Nicolas Dec 13 '12 at 17:57
1  
@AndréNicolas: What? This was known to (and proved by) Euclid. –  Chris Eagle Dec 13 '12 at 18:24
show 5 more comments

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
That's actually my concern, and thanks for bringing that up. So for something small like 100 prime numbers then it will be (99+1)*99/2 that many unique id which i think it should be okay, but I am not sure if this will be suffice for something big like 1 million of prime numbers. Because I was looking for a way to pair up all the prime numbers in a certain range, and identify each of the pair quickly by their product. –  user1389813 Dec 13 '12 at 18:48
    
The trouble is that with such a small set, a bad guy to figure it out and masquerade IDs. I think you should look at the RFC and choose that method over the one being proposed. - Regards –  Amzoti Dec 13 '12 at 18:51
    
Ok i see the problem and thanks for mentioning, but I am just using this internally inside a function just to identify each pair quicker and as well as being unique, so later if I want to get this particular pair I can just get it from the hash table, so the security issue is not a big deal at this case. –  user1389813 Dec 13 '12 at 19:11
    
If these values are never exposed, that is okay, but recall that someone could take the contents of memory, reverse engineer things and figure this out. If that does not matter, then your approach is fine. –  Amzoti Dec 13 '12 at 19:14
    
Great answer, Amzoti! $\large \checkmark^{+1}$ –  amWhy May 14 '13 at 1:34
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.