[Python] Do subset-sum instances inherently require large integers to force exponential...

I'm developing custom subset-sum algorithms and have encountered a puzzling issue: it seems difficult to generate truly "hard" subset-sum instances (i.e., forcing exponential computational effort) without using very large integers (e.g., greater than about 2^22).

I'd specifically like to know:

• Are there known constructions or instance generators for subset-sum that reliably force exponential complexity—particularly against common subset-sum algorithms or custom heuristics—using only moderately sized integers (≤2^22)?
• Is the hardness of subset-sum instances inherently tied to the size of integers involved, or is it possible to create computationally difficult instances purely through numerical structure and relationships, even with smaller numbers?

For context, here are some attempts I've made at generating potentially hard instances (feedback or improvements welcome):

import random

def generate_exponential_instance(n):
max_element = 2 ** 22
A = [random.randint(1, max_element) for _ in range(n)]
while True:
mask = [random.choice([0, 1]) for _ in range(n)]
if sum(mask) != 0:
break
target = sum(A * mask for i in range(n))
return A, target

def generate_dense_high_values_instance(n):
base = 2 ** 22 - random.randint(0, 100)
A = [base + random.randint(0, 20) for _ in range(n)]
target = sum(random.sample(A, k=n // 2))
return A, target

def generate_merkle_hellman_instance(n, max_step=20):
total = 0
private_key = []
for _ in range(n):
next_val = total + random.randint(1, max_step)
private_key.append(next_val)
total += next_val
q = random.randint(total + 1, 2 * total)
r = random.randint(2, q - 1)
public_key = [(r * w) % q for w in private_key]
message = [random.randint(0, 1) for _ in range(n)]
ciphertext = sum(b * k for b, k in zip(message, public_key))
return public_key, ciphertext

Continue reading...