In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the a_i's are generated randomly in the range [0,M), and we are
asked to produce a subset of them such that the sum is t(mod M).
The hardness of RMSS depends on the relationship between the
parameters M and n. When M=2^{O(n^2)}, RMSS can be solved in
polynomial time by a reduction to the shortest vector problem. When
M=2^{O(log{n})}, the problem can be solved in polynomial time by
dynamic programming, and recently an algorithm was proposed that
solves the problem in polynomial time for M=2^{O(log^2{n})}. In
this work, we present an algorithm that solves the Random Modular
Subset Sum problem for parameter M=2^{n^c} for c<1
in time (and space) $2^{O((n^c)/log(n)))}$. As far as
we know, this is the first algorithm that performs in time better
than $2^{Omega(n^c)}$ for arbitrary c<1.