Question (Use Sage):
The following describes the simple hash function:
Choose p, q primes and compute N = pq.
Choose g relatively prime to N and less than N.
Then a number n is hashed as follows:
H = gn mod N
If there is an m that hashes to the same value as n, then
gm ≡ gn mod N
gm-n ≡ 1 mod N
which implies that
m –n ≡ 0 mod φ (N)
So breaking this amounts to finding a multiple of φ (N), which is the hard problem in RSA.