The probabilistic problem, improved and strong!

Files given:

• improved.py

def gen_params(nbit):
	p, q = [getPrime(nbit) for _ in range(2)]
	n, f, g = p * q, lcm(p-1, q-1), p + q
	e = pow(g, f, n**2)
	u = divmod(e-1, n)[0]
	v = inverse(u, n)
	params = int(n), int(f), int(v)
	return params

def improved(m, params):
	n, f, v = params
	if 1 < m < n**2 - 1:
		e = pow(m, f, n**2)
		u = divmod(e-1, n)[0]
		L = divmod(u*v, n)[1]
	H = hashlib.sha1(str(L).encode('utf-8')).hexdigest()
	return H

The goal of this challenge is to create a collision given improved as the hash function given . As it is unlikely that we find a sha1 collision, we aim to find a collision in L. We first express L mathematically:

and note that whenever .

Lets suppose we want , then expanding this out, we get

which can easily be computed since we know ! Hence getting collisions is simple.

Solution at solve.py