The standard crypto answer for this type of problem is to use some sort of homomorphic encryption. Homomorphic encryption allows you to encrypt your input in such a way that a third-party can still perform computations on it (but is unable to read the results of these computations without breaking the encryption).
A silly example of this is that if you want to get a third-party to perform some multiplication operations for you (say multiply $a$ and $b$), you can encrypt your values via RSA, send him $a^{e}$ and $b^{e}$, he multiplies the encrypted values together to get $(ab)^{e}$ and sends it back, upon which you can recover $(ab)$ by computing $(ab)^{de}$ (all operations done modulo some semiprime $n$). Of course, performing any of these encryption/decryption steps require multiple multiplication operations, but you could imagine this possibly being useful if you wanted to know the product of a million numbers. Computer scientists now know how to perform fully homomorphic encryption in polynomial time, which means there are methods to encrypt things that allow the third-party to not only multiply, but also add, compare, and in general perform arbitrary computation. You could use such a method for this problem.
I think these methods are not quite fast enough to be used in practice, yet. You might hope for a simpler sort of construction like your construction for finding a Hamiltonian cycle. I'm not sure of whether anyone has thought about this before, but here is a method that might work.
One of the fastest methods for factoring integers is via the General Number Field Sieve. This algorithm is a little complicated, but can be roughly summarized as follows (see the Wikipedia article for a more accurate description):
- Generate two (degree $d$) polynomials $f(x)$ and $g(x)$ such that $f$ and $g$ are irreducible over the rationals, but have a common root $m$ modulo $n$.
- Repeatedly choose integers $a$ and $b$ and compute $r = b^d f(a/b)$ and $s = b^d g(a/b)$. If $r$ and $s$ are both $B$-smooth (i.e., all their prime factors are at most $B$) then store this pair (along with the associated $a$ and $b$) for later ($B$ is a parameter which depends on $n$ in some simple way).
- Use Gaussian elimination (or some sparse linear solver) to find a subset of pairs $(r_1, s_1), \dots (r_k, s_k)$ such that $r_1r_2\dots r_k$ and $s_1s_2\dots s_k$ are both squares (technically you need a slightly stronger condition, but this is a reasonable simplification).
- It turns out that $r_i$ is the norm of $a_i + \alpha b_i$ over $\mathbb{Z}[\alpha]$, where $\alpha$ is a root of $f$ over $\mathbb{C}$. Similarly, $s_i$ is the norm of $a_i + \beta b_i$ over $\mathbb{Z}[\beta]$, where $\beta$ is a root of $g$. If $r_1r_2\dots r_k$ is a square (plus that other stronger condition), then this implies there is an element $x \in \mathbb{Z}[\alpha]$ with $x^2 = r_1r_2\dots r_k$, and an element $y \in \mathbb{Z}[\beta]$ with $y^2 = s_1s_2\dots s_k$. There are known methods to compute these $x$ and $y$.
- Since $f$ and $g$ both have a root $m$ modulo $n$, there exist two homomorphisms $u: \mathbb{Z}[\alpha] \rightarrow \mathbb{Z}/n\mathbb{Z}$ and $v: \mathbb{Z}[\beta] \rightarrow \mathbb{Z}/n\mathbb{Z}$ which just send $\alpha$ and $\beta$ respectively to $m$. Then, if we let $C = \prod (a_i + mb_i) \bmod n$, we have that $u(x)^2 = C \bmod n$ and $v(y)^2 = C \bmod n$. If $u(x)$ and $v(y)$ are equal (or negatives of each other), this doesn't tell us anything, but otherwise, this lets us factorize $n$. On average, this will happen with probability about $1/2$.
For your question, the important thing to takeaway from this is that the only steps of this procedure where it is really important to know $n$ are steps $1$ and $5$, and these steps are relatively computationally light. Performing steps $2$, $3$, and $4$ just require knowing $f$ and $g$ (and perhaps the approximate size of $n$, to set parameters like $B$).
The question then becomes, if these minions know $f$ and $g$, can they figure out $n$? I'm not sure of the answer to this. If they know $m$, then they can compute $f(m)$ and $g(m)$, both of which are divisible by $n$ (so probably their gcd will basically give you $n$). However, it seems like you can construct $f$ and $g$ in such a way that it is hard to find $m$ (by say, choosing random degree $d$ polynomials and adjusting the constant term so that $m$ is a root modulo $n$). I don't know if there is any standard hardness assumption that gives you this though.
Finally, there's an implicit second component to your question, which is that you have an army of minions instead of just one. This suggests you might also want a problem which parallelizes well. Luckily, step 2 above (probably the most computationally heavy step) is highly parallelizable, so you can divide this work amongst many minions easily. If you think your minions won't collude, then there's some additional approaches to gain some privacy via splitting the problem up amongst them so that no individual minion can learn much about the problem (e.g. something like giving only $f$ to half the minions and only $g$ to half the minions); this is probably worth thinking about.
