I was thinking about the strategy of solving Subset-Sum (with a set of size n and integers having n bits each) by using Dynamic Programming (described here: http://en.wikipedia.org/wiki/Subset_sum_problem) modulo n small primes, 2,3,5,7,11,...,nth prime. The algorithm would then compute the intersection of the sets of answers modulo each prime. The solution to Subset-Sum would be in the intersection, and probably no wrong answers would be in the intersection.
Would such an algorithm be expected to run in polynomial-time? In other words, is it possible to compute the intersection of the sets of answers modulo each prime efficiently in the average case scenario?
(Note that in the worst-case scenario, this algorithm would have exponential running-time, since the intersection may have exponential size. I'm only talking about the average-case scenario here when there are only few or no solutions. This question has nothing to do with the P vs. NP problem.)