Bijective ID Generator

High-performance, collision-free ID generation using format-preserving encryption. Generates 6-character alphanumeric IDs with mathematical guarantee of uniqueness.

H.Overman
Email: opsec.ee@pm.me

---

Features

• Zero Collisions: Mathematically guaranteed unique IDs (bijective mapping)
• High Performance: 20+ million IDs/second
• Thread-Safe: Lock-free atomic operations
• Compact: 6-character base62 IDs (0-9a-zA-Z)
• Non-Sequential: Cryptographically scrambled appearance
• Verified: Tested with 1 million IDs, zero duplicates found

---

Quick Start

Build

gcc -std=c2x -O3 -march=native -flto -o id_gen id_gen_test.c id_gen.c

Run Test

./id_gen

---

Expected Output

========================================
Bijective ID Generation - 1 Million ID Test
========================================

Generator initialized with secret key
Target: Generate and verify 1,000,000 unique IDs

Allocating memory for 1 million IDs...
Allocating hash table for duplicate detection...
Memory allocated successfully

Generating 1,000,000 IDs...
Generated: 1,000,000 IDs
  Time: 0.042520 seconds
  Rate: 23518612 IDs/second

First 20 IDs generated:
        1: 87onUh
        2: PZXmuX
        3: VfBFbY
        4: rbttAg
        5: Ijyjny
        6: WLVSvi
        7: LXzCdM
        8: fRTBr6
        9: k1hR1P
       10: uyTzxB
       11: Dbv3Jg
       12: O0RgzC
       13: GwcTZj
       14: hYefUh
       15: om3uTe
       16: Culm5R
       17: 0qHT8g
       18: 9kFQMS
       19: dgYgNx
       20: TgyG0S

Verifying uniqueness (checking for duplicates)...
  Checked 100000 IDs...
  Checked 200000 IDs...
  Checked 300000 IDs...
  Checked 400000 IDs...
  Checked 500000 IDs...
  Checked 600000 IDs...
  Checked 700000 IDs...
  Checked 800000 IDs...
  Checked 900000 IDs...
  Checked 1000000 IDs...

VERIFICATION PASSED: All 1,000,000 IDs are unique
  Verification time: 0.063578 seconds

Analyzing distribution (first 100,000 IDs)...

Character Distribution Analysis:
--------------------------------
Total characters: 600000
Expected per character: 9677 (uniform distribution)

Sample distribution (first 10 digits, first 10 letters):
  '0': 9464 (97.79% of expected)
  '1': 9702 (100.25% of expected)
  '2': 9731 (100.55% of expected)
  '3': 9620 (99.41% of expected)
  '4': 9517 (98.34% of expected)
  '5': 9693 (100.16% of expected)
  '6': 9739 (100.64% of expected)
  '7': 9601 (99.21% of expected)
  '8': 9548 (98.66% of expected)
  '9': 9597 (99.17% of expected)
  'a': 9567 (98.86% of expected)
  'b': 9679 (100.02% of expected)
  'c': 9613 (99.33% of expected)
  'd': 9604 (99.24% of expected)
  'e': 9775 (101.01% of expected)
  'f': 9834 (101.62% of expected)
  'g': 9596 (99.16% of expected)
  'h': 9907 (102.37% of expected)
  'i': 9762 (100.87% of expected)
  'j': 9766 (100.92% of expected)

Chi-square statistic: 65.42
(Lower values indicate more uniform distribution)


Last 20 IDs generated:
   999981: w3ghW4
   999982: 3RtXzg
   999983: u3XIRN
   999984: BXeTuJ
   999985: G5GKzm
   999986: krrPfY
   999987: 2H5465
   999988: M6sA82
   999989: 7j7D1b
   999990: NiNGmL
   999991: 5Pcv8U
   999992: TpWsLl
   999993: PqoguR
   999994: 3syeRV
   999995: QWMSqa
   999996: XewM75
   999997: OxF9Zt
   999998: hgKNoq
   999999: CwnK6i
  1000000: kVw7ZF

========================================
SUMMARY
========================================
Total IDs generated:     1,000,000
Unique IDs verified:     1,000,000 (100%)
Duplicates found:        0
Generation time:         0.042520 seconds
Generation rate:         23518612 IDs/second
Verification time:       0.063578 seconds
Total time:              0.106098 seconds
========================================
SUCCESS: Bijective guarantee confirmed
========================================

---

How It Works

Monotonic counter encrypted via 8-round Feistel network (XOR/multiply operations). Cycle-walking ensures output fits 62^6 space without modulo. Base62 encoding produces 6-character ID. Each step preserves bijection = zero collision guarantee.

Architecture

Counter → Feistel Encrypt → Cycle-Walk → Base62 Encode → ID
   0    →    [8 rounds]   →  [validate] →   encode     → "87onUh"
   1    →    [8 rounds]   →  [validate] →   encode     → "PZXmuX"
   2    →    [8 rounds]   →  [validate] →   encode     → "VfBFbY"

---

Capacity

• ID Space: 62^6 = 56,800,235,584 unique IDs

---

Requirements

• Compiler: GCC 10+ or Clang 12+ with C2x support
• Standard: C23 (uses C2x flag for GCC)
• Platform: Linux, macOS, BSD (POSIX)
• Dependencies: Standard C library only

---

Files

id_gen.h              - Public API header
id_gen.c              - Core implementation
id_gen_test.c         - 1 million ID verification test

---

Technical Details

Algorithm

1. Feistel Network - 8 rounds of bijective encryption
2. MurmurHash3 Mixing - Avalanche effect for diffusion
3. Cycle-Walking - Ensures output in valid range without modulo
4. Base62 Encoding - Converts to alphanumeric string

Why No Collisions

Traditional approach using modulo breaks bijection:

// WRONG - causes collisions
return scramble(counter) % (62^6);

This approach preserves bijection:

// CORRECT - maintains one-to-one mapping
while (encrypted >= 62^6) {
    encrypted = encrypt_again(encrypted);
}
return encrypted;

Verification

Tested with 1,000,000 IDs:

• ✓ Zero duplicates found
• ✓ Uniform character distribution (Chi-square: 65.42)
• ✓ Non-sequential appearance
• ✓ Thread-safe concurrent generation

---

Use Cases

Recommended:

• Database primary keys
• Order/transaction IDs
• Request tracking
• Session identifiers
• Log correlation IDs

Not Recommended:

• Cryptographic tokens
• Password reset links
• Security-critical authentication

---

Support

Issues: Open a GitHub issue with:

• Compiler version
• Platform (OS/CPU)
• Test demonstrating problem
• Expected vs actual behavior

Email: opsec.ee@pm.me

---

Acknowledgments

Based on format-preserving encryption techniques (Feistel networks, cycle-walking) used in cryptographic standards.

---