Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region.

Can this be done (significantly) faster than multiplying and reducing one-by-one?

Solution 1:

If you already have the primes, and this has boiled down to a computer science question (since you mention speed of computation), you can compute the product in parallel.

For example, if you had two cores you could compute the product of the 1st element, 3rd element, 5th element, etc. on the first core, and the product of the 2nd element, 4th element, 6th element, etc. on the second core.

Since $ab\ mod(n) = (a\ mod(n))*(b\ mod(n))\ mod(n)$, you can then just multiply the results from both cores once they are done, with little need to worry about concurrency issues.