Generating primary keys using one tiny bit of group theory

This is dangerous advice.

First, UUIDs are used when you need Universally Unique identifiers... hence the two 'U's. That's why they take 16 bytes of storage space, so that the probability of duplicate keys is quite low. While it isn't zero, which is true, the chance of generating one duplicate key for every fifty trillion keys or so is less than that of being hit by a meteorite.

So, UUIDs are to all intents and purposes universally unique, without requiring any sort of locking mechanism to provide a reasonable assurance of uniqueness. And, if you store them (in MySQL) as CHAR BINARY, they only take up 16 bytes of space, and incur no practical overhead greater than integer primary keys.

Second, if you use the 'generator of a finite group' method, you are pretty screwed when you run out of keys. One, because once you hit n (the size of the group), every following 'key' is guaranteed to be a duplicate. Two, and this is the real kicker, if you want to increase the size of the keyspace, you either have to partition it (ugh), or find a generator that is coprime to both the old and new keyspace dimensions, which is not guaranteed to be possible.

This approach, using generators of finite groups, has zero advantages over an incrementing primary key. Because you still need that integer (k), which is the last integer in an incrementing sequence, which you get from... an auto-incrementing column. So your insert performance will be slower than just using integer keys, which offer a larger keyspace out of the box to boot.