Choosing Hash Base and Modulus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

def recommended_base(alphabet_description: str) -> int:
    """
    Return a recommended base for the given alphabet type.
    
    The base must be:
    1. Greater than the maximum character value in the alphabet
    2. Preferably prime (for better distribution)
    3. Not too large (to avoid overflow issues)
    """
    recommendations = {
        'lowercase': 31,      # 'a'-'z' (26 chars, values 0-25 or 97-122)
        'alphanumeric': 37,   # a-z, A-Z, 0-9 (62 chars)
        'ascii_printable': 131,  # Characters 32-126 (95 chars)
        'ascii_full': 257,    # Characters 0-255 (256 chars)
        'unicode': 1000003,   # Large prime for Unicode
    }
    
    return recommendations.get(alphabet_description, 31)
 
 
def validate_base(base: int, characters: str) -> tuple[bool, str]:
    """
    Validate that a base is appropriate for the given character set.
    """
    max_char = max(ord(c) for c in characters)
    
    if base <= max_char:
        return (False, f"Base {base} must be > max character value {max_char}")
    
    # Check if base is prime (simple check)
    def is_prime(n):
        if n < 2: return False
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0: return False
        return True
    
    if not is_prime(base):
        return (True, f"Warning: Base {base} is not prime, consider using a prime")
    
    return (True, f"Base {base} is valid for this character set")
 
 
# Example: Demonstrate the problem with too-small bases
def show_collision_risk():
    """Demonstrate why base must exceed alphabet size."""
    
    # With base = 26 for lowercase letters (using 'a'=0 mapping)
    base = 26
    
    def hash_with_base(s: str, b: int) -> int:
        h = 0
        for c in s:
            h = h * b + (ord(c) - ord('a'))
        return h
    
    # These should have different hashes but...
    test_pairs = [
        ("ba", "aa"),  # Different strings
    ]
    
    print("Demonstrating collision risk with small base:")
    print(f"Using base = {base}")
    
    # 'ba' = 1*26 + 0 = 26
    # 'aa' = 0*26 + 0 = 0 (no collision here)
    # But consider longer strings and patterns...
    
    for s in ["aa", "ba", "ab", "bb"]:
        h = hash_with_base(s, base)
        print(f"  H('{s}') = {h}")
    
    print("
With proper base = 31:")
    base = 31
    for s in ["aa", "ba", "ab", "bb"]:
        h = hash_with_base(s, base)
        print(f"  H('{s}') = {h}")
 
 
show_collision_risk()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

# Common modulus choices with their properties
MODULI = {
    'CP_STANDARD': 10**9 + 7,      # Standard competitive programming
    'CP_ALT': 10**9 + 9,          # Alternative for double hashing
    'NTT_FRIENDLY': 998244353,     # For Number Theoretic Transform
    'MERSENNE_61': (1 << 61) - 1,  # Mersenne prime, very low collision
    'MERSENNE_31': (1 << 31) - 1,  # Smaller Mersenne prime
}
 
 
def is_prime(n: int) -> bool:
    """Miller-Rabin primality test for large numbers."""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Witnesses to test
    witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    
    for a in witnesses:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
 
 
def analyze_modulus(m: int, name: str):
    """Analyze properties of a modulus choice."""
    print(f"
{name}: {m}")
    print(f"  Prime: {is_prime(m)}")
    print(f"  Bits needed: {m.bit_length()}")
    print(f"  Max product before overflow (64-bit): {(1 << 63) // m}")
    
    # Collision probability per pair
    collision_prob = 1 / m
    print(f"  Collision probability (per pair): {collision_prob:.2e}")
    
    # Number of strings before 50% collision (birthday paradox)
    import math
    birthday_50 = int(math.sqrt(2 * m * math.log(2)))
    print(f"  50% collision threshold (birthday): ~{birthday_50:,} strings")
 
 
# Analyze common moduli
for name, mod in MODULI.items():
    analyze_modulus(mod, name)
 
 
def safe_product(a: int, b: int, mod: int) -> int:
    """
    Compute (a * b) % mod safely without overflow.
    
    In Python, this is automatic (arbitrary precision).
    In C++/Java, you'd need __int128 or modular multiplication.
    """
    return (a * b) % mod
 
 
def demonstrate_overflow_risk():
    """
    Show why intermediate overflow is a concern.
    
    When computing (hash * base + char) % mod:
    - hash can be up to mod-1
    - base is typically 31-1000
    - So hash * base can be (mod-1) * base
    
    For mod = 10^9+7, base = 31:
    - Max intermediate: ~3.1 × 10^10
    - Fits in 64-bit (max ~9.2 × 10^18) ✓
    
    For mod = 10^18, base = 31:
    - Max intermediate: ~3.1 × 10^19
    - EXCEEDS 64-bit! Need 128-bit arithmetic
    """
    mod_small = 10**9 + 7
    mod_large = 10**18 + 9
    base = 31
    
    max_64bit = (1 << 63) - 1
    
    intermediate_small = (mod_small - 1) * base
    intermediate_large = (mod_large - 1) * base
    
    print("
Overflow Risk Analysis:")
    print(f"  64-bit signed max: {max_64bit:,}")
    print(f"  Mod=10^9+7, base=31: intermediate max = {intermediate_small:,}")
    print(f"    Safe for 64-bit: {intermediate_small < max_64bit}")
    print(f"  Mod=10^18+9, base=31: intermediate max = {intermediate_large:,}")
    print(f"    Safe for 64-bit: {intermediate_large < max_64bit}")
 
 
demonstrate_overflow_risk()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// Strategy 1: Standard 64-bit with safe modulus
namespace StandardHash {
    const long long MOD = 1e9 + 7;
    const long long BASE = 31;
    
    long long hash(const string& s) {
        long long h = 0;
        for (char c : s) {
            // Safe: (10^9) * 31 + 127 < 2^63
            h = (h * BASE + c) % MOD;
        }
        return h;
    }
}
 
// Strategy 2: 128-bit intermediate for large modulus
namespace LargeModHash {
    using u64 = uint64_t;
    using u128 = __uint128_t;  // GCC/Clang extension
    
    const u64 MOD = 1000000000000000009ULL;  // 10^18 + 9
    const u64 BASE = 31;
    
    u64 safe_mod(u128 x) {
        return x % MOD;
    }
    
    u64 hash(const string& s) {
        u64 h = 0;
        for (char c : s) {
            // Use 128-bit for intermediate
            h = safe_mod((u128)h * BASE + c);
        }
        return h;
    }
}
 
// Strategy 3: Natural 64-bit overflow (non-prime modulus)
namespace OverflowHash {
    using u64 = uint64_t;
    const u64 BASE = 31;
    
    u64 hash(const string& s) {
        u64 h = 0;
        for (char c : s) {
            // Let it overflow naturally at 2^64
            h = h * BASE + c;
        }
        return h;
    }
}
 
// Strategy 4: Mersenne prime with fast modulo
namespace MersenneHash {
    using u64 = uint64_t;
    using u128 = __uint128_t;
    
    // 2^61 - 1 is a Mersenne prime
    const u64 MOD = (1ULL << 61) - 1;
    const u64 BASE = 31;
    
    // Fast modulo for Mersenne prime: x % (2^61 - 1)
    u64 mersenne_mod(u128 x) {
        // x = a * 2^61 + b
        // x mod (2^61-1) = a + b (mod 2^61-1)
        u64 low = x & MOD;       // b = x mod 2^61
        u64 high = x >> 61;       // a = x / 2^61
        u64 result = low + high;
        if (result >= MOD) result -= MOD;
        return result;
    }
    
    u64 hash(const string& s) {
        u64 h = 0;
        for (char c : s) {
            h = mersenne_mod((u128)h * BASE + c);
        }
        return h;
    }
}
 
int main() {
    string test = "Hello, World! This is a test string for hashing.";
    
    cout << "Standard (10^9+7): " << StandardHash::hash(test) << endl;
    cout << "Large mod (10^18+9): " << LargeModHash::hash(test) << endl;
    cout << "Overflow (2^64): " << OverflowHash::hash(test) << endl;
    cout << "Mersenne (2^61-1): " << MersenneHash::hash(test) << endl;
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

import random
import time
 
class SecureStringHasher:
    """
    String hasher with randomized parameters for adversarial resistance.
    
    The base is randomly chosen at instantiation, making it impossible
    for an attacker to pre-compute colliding inputs.
    """
    
    def __init__(self, seed: int = None):
        """
        Initialize with random or seeded parameters.
        
        Args:
            seed: For reproducibility in testing; None for random
        """
        if seed is not None:
            random.seed(seed)
        
        # Randomize base from a range of primes
        prime_bases = [31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
                       101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151]
        
        # Choose random base
        self.base = random.choice(prime_bases)
        
        # Use two different moduli for double hashing
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        
        # Also randomize which of several mod pairs we use
        mod_choices = [
            (10**9 + 7, 10**9 + 9),
            (998244353, 10**9 + 7),
            (10**9 + 21, 10**9 + 33),
        ]
        self.mod1, self.mod2 = random.choice(mod_choices)
    
    def hash(self, s: str) -> tuple[int, int]:
        """
        Compute double hash for collision resistance.
        
        Returns a tuple (hash1, hash2) that both must match.
        """
        h1, h2 = 0, 0
        for c in s:
            code = ord(c)
            h1 = (h1 * self.base + code) % self.mod1
            h2 = (h2 * self.base + code) % self.mod2
        return (h1, h2)
    
    def are_likely_equal(self, s1: str, s2: str) -> bool:
        """
        Check if two strings are likely equal based on hash.
        
        Returns True if both hashes match (collisions rare but possible).
        For guaranteed correctness, verify with string comparison.
        """
        return self.hash(s1) == self.hash(s2)
 
 
def demonstrate_randomization():
    """Show that each hasher instance uses different parameters."""
    print("Demonstrating parameter randomization:")
    
    for i in range(5):
        hasher = SecureStringHasher()
        h = hasher.hash("test")
        print(f"  Instance {i}: base={hasher.base}, mods=({hasher.mod1}, {hasher.mod2})")
        print(f"    hash('test') = {h}")
 
 
def collision_attack_simulation():
    """
    Simulate attempting a collision attack.
    
    With fixed parameters, an attacker can find collisions.
    With randomized parameters, they cannot.
    """
    print("
Collision attack simulation:")
    
    # Fixed hasher (vulnerable)
    class FixedHasher:
        def hash(self, s: str) -> int:
            h = 0
            for c in s:
                h = (h * 31 + ord(c)) % (10**9 + 7)
            return h
    
    # Attacker knows parameters and crafts collision
    fixed = FixedHasher()
    
    # Find two different strings with same hash (simplified demo)
    # In practice, attackers use mathematical techniques
    target = fixed.hash("hello")
    print(f"  Fixed hasher: hash('hello') = {target}")
    
    # With randomized hasher, attacker doesn't know parameters
    secure = SecureStringHasher()
    h1 = secure.hash("hello")
    h2 = secure.hash("world")
    print(f"  Secure hasher: hash('hello') = {h1}")
    print(f"  Secure hasher: hash('world') = {h2}")
    print(f"  Attacker cannot predict these values without knowing parameters!")
 
 
demonstrate_randomization()
collision_attack_simulation()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

"""
Production-ready string hasher with recommended parameters.
"""
 
class PolynomialHash:
    """
    Standard polynomial hash implementation with recommended parameters.
    
    Uses the competitive programming standard: base=31, mod=10^9+7
    with optional double hashing for increased collision resistance.
    """
    
    # Standard competitive programming parameters
    BASE1 = 31
    MOD1 = 10**9 + 7
    
    # Second set for double hashing
    BASE2 = 37
    MOD2 = 10**9 + 9
    
    def __init__(self, s: str, double_hash: bool = False):
        """
        Initialize hasher with precomputed prefix hashes.
        
        Args:
            s: The string to hash
            double_hash: If True, compute two independent hashes
        """
        self.s = s
        self.n = len(s)
        self.double_hash = double_hash
        
        # Precompute prefix hashes and powers (first hash)
        self.prefix1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        
        for i in range(self.n):
            self.prefix1[i + 1] = (
                self.prefix1[i] * self.BASE1 + ord(s[i])
            ) % self.MOD1
            self.power1[i + 1] = (
                self.power1[i] * self.BASE1
            ) % self.MOD1
        
        # Second hash if requested
        if double_hash:
            self.prefix2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
            
            for i in range(self.n):
                self.prefix2[i + 1] = (
                    self.prefix2[i] * self.BASE2 + ord(s[i])
                ) % self.MOD2
                self.power2[i + 1] = (
                    self.power2[i] * self.BASE2
                ) % self.MOD2
    
    def get_hash(self, left: int, right: int) -> int | tuple[int, int]:
        """
        Get hash of substring s[left:right+1] (inclusive).
        
        Returns int if single hash, tuple if double hash.
        Time: O(1)
        """
        length = right - left + 1
        
        h1 = (
            self.prefix1[right + 1] 
            - self.prefix1[left] * self.power1[length]
        ) % self.MOD1
        if h1 < 0:
            h1 += self.MOD1
        
        if not self.double_hash:
            return h1
        
        h2 = (
            self.prefix2[right + 1] 
            - self.prefix2[left] * self.power2[length]
        ) % self.MOD2
        if h2 < 0:
            h2 += self.MOD2
        
        return (h1, h2)
    
    def compare(self, l1: int, r1: int, l2: int, r2: int) -> bool:
        """Compare two substrings by hash. O(1) time."""
        if r1 - l1 != r2 - l2:
            return False
        return self.get_hash(l1, r1) == self.get_hash(l2, r2)
 
 
# Demonstration
def demo():
    # Single hash (standard)
    text = "abracadabra"
    hasher = PolynomialHash(text)
    
    print(f"String: '{text}'")
    print(f"
Single hash mode:")
    print(f"  hash(0,3) 'abra': {hasher.get_hash(0, 3)}")
    print(f"  hash(7,10) 'abra': {hasher.get_hash(7, 10)}")
    print(f"  Equal? {hasher.compare(0, 3, 7, 10)}")  # True
    
    # Double hash (when correctness matters)
    hasher2 = PolynomialHash(text, double_hash=True)
    print(f"
Double hash mode:")
    print(f"  hash(0,3): {hasher2.get_hash(0, 3)}")
    print(f"  hash(7,10): {hasher2.get_hash(7, 10)}")
    print(f"  Equal? {hasher2.compare(0, 3, 7, 10)}")  # True
 
 
demo()