Integer relation detection for Subset Sum or NPP?
Let m be the logarithm of the largest number.
If $m=O(\log n)$ then it is solvable in polynomial time using dynamic programming.
In general, every known algorithm take at least $\Omega(2^{m})$ time. There is no known polynomial time algorithm when $m=\omega(\log n)$ and $m=o(n)$

However, Flaxman and Przydatek provide an algorithm that solves Medium-Density Subset Sum Problems in Expected Polynomial Time.

Check this reference:

Flaxman and Przydatek, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time