This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is "easy" (i.e., can be solved in polynomial time):
Given $N > 2$, find a prime $p$ such that $p \equiv 1 \pmod{N} \tag{1}.$
(Of course, Dirichlet's theorem assures us that infinitely many such $p$ exist.)
Now, I do not know of a clever way to find such a $p$, so I suggested simply iterating through the arithmetic progression $1+kN$ for $k = 0, 1, 2, \ldots$, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime $p$ satisfying $(1)$ is at most $N^{O(1)}$. (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.
More generally,
Given an integer $N$, what upper bound do we know on the smallest prime satisfying $(1)$?
I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.
Edit: Turns out the claim in the question is false. The procedure will be efficient only if the smallest prime is $O(N \cdot\mathrm{poly}\log N)$, which seems very unlikely. In any case, I will just keep this question as it is, since it makes sense as a stand-alone question as well.