2
$\begingroup$

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.

  • 0
    Is your pair of primes ordered? In that case $(p,q)$ and $(q,p)$ obviously have the same product.2012-12-13
  • 5
    See the [Fundamental theorem of arithmetic](http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic).2012-12-13
  • 0
    Since you are combining only primes, it would be unique.2012-12-13
  • 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.2012-12-13
  • 0
    @ronno yes they are in ordered. I mean are there any chance to have collision other than (p,q) and (q,p) ?2012-12-13
  • 0
    @user1389813 No other collisions are possible, as Raymond already pointed out. Given the product $n$, it is possible to determine $p$ and $q$ by the simple procedure of trial division.2012-12-13
  • 0
    So is it overall a good idea to use it as an Id and the key for hash table ?2012-12-13
  • 0
    @user1389813: Hash? That's a different question and has a different answer: no2012-12-13
  • 1
    @AndréNicolas: What? This was known to (and proved by) Euclid.2012-12-13
  • 0
    @ChrisEagle: There is some controversy about that, but not much. Certainly the result does not appear in *Elements*. If Euclid had *formulated* the Fundamental Theorem, then a result proved in *Elements* would have been a key lemma. But it didn't happen, at least not in any surviving text.2012-12-13

1 Answers 1

7

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

  • 0
    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.2012-12-13
  • 0
    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. - Regards2012-12-13
  • 0
    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.2012-12-13
  • 0
    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.2012-12-13
  • 0
    Great answer, Amzoti! $\large \checkmark^{+1}$2013-05-14
  • 0
    @amWhy: thanks, that is another tricky area! Check out the updates I just here, that is an amazing system, so rich! http://math.stackexchange.com/questions/390439/possible-ways-to-do-stability-analysis-of-non-linear-three-dimensional-differen/390463?noredirect=1#comment836528_3904632013-05-14