**Update 2017.07.13**: The question has been made more precise and interesting by having some uncertainty introduced in knowing some information in an 'unordered' fashion. Part of the interest stems from the fact that a multiset of residues mod small primes has some limitations in making a valid interpretation. For example, if 6 is a residue, is that mod 5 or mod 7? If it is 6 mod 2 or mod 3 then most of the other residues have to have the same value, either 2 or 3.

In spite of this uncertainty, much of the post below applies. If you know n (equivalently p_n) is small enough, you can still have a multiset of about (say) 3 log (n) many terms to specify the prime. This is because the primes less than M are few in number compared to the number of appropriate multisets of length 3*log M. A question similar to one that has appeared on MathOverflow I record here: if p is a small prime with residue multiset consisting of 1's and 2's only, how long does it take to find it? Notice that this has a connection with consecutive smooth numbers.

**End Update 2017.07.13.**

If you are given the value m=k(n), and the first m primes and moduli p_i and x_i, and you are given the information that the prime p_n you are looking for is less than the product of the known primes, then (since the product of the first m primes is about exp(p_m) ), you can have k(n) be as small as something like 2log(n), perhaps smaller. Because of the wording of the question, it is not clear if you have or can derive the information that p_1 p_2... p_m is greater than p_n . If you have no clue of n other than p_n is prime, then (as was pointed out in another post) because of the infinitude of primes in certain arithmetic progressions the only congruence that specifies the prime p_n is p_n =0 mod p_n; no other finite system of congruences mod primes that excludes p_n does so.

For example, suppose I know n is 11. From other theory, I know p_11 is less than 11 * 4, (using log 11 + log log 11) and so k(11) is 4, and so p_11 is less than 2*3*5*7. Using moduli, I get p_11 is 31. If I did not know n was 11, I might not know if the prime was 31 or 241 just from knowing k(n)=4 and the four congruences.

Gerhard "Hopefully This Answers The Question" Paseman, 2017.07.12.