Again, I do not know how to solve this problem. Leave it to the future me to digest how to solve lattice problems and understand a bit more about group theory. The original attack is from Shamir et al., but a low-density attack that leverages the LLL algorithm. A version is mentioned in this awesome paper. Sage Implementation: a = [ #public key ] s = #ciphertext n = len(a) N = ceil(sqrt(n) / 2) b = [] for i in range(n): vec = [0 for _ in range(n + 1)] vec[i] = 1 vec[-1] = N * a[i] b.