This is pretty straightforward; we just use the [relationship between the Poisson and the chi squared](http://en.wikipedia.org/wiki/Poisson_distribution#Related_distributions):

If $Y\sim \text{Poisson}(\lambda)$ and $X\sim \chi^2_{2(k+1)}$, for integer $k$, then

$$F_Y(k)  = 1-F_{X}(2\lambda) \,.$$

As a result, $$\lambda = \frac{1}{2}\, F_{X}^{-1}(1-F_Y(k))\,.$$


For example, in R, let's try to find the value of $\lambda$ corresponding to $k=6$ and $\alpha=0.1$:

    > alpha=.1;k=6
    > qchisq(1-alpha,2*(k+1))/2
    [1] 10.53207
    > ppois(k,10.53207)
    [1] 0.1000001

So $\lambda\approx 10.53207$.

On my kids little laptop, running R, $10^5$ such calculations took me a well under a second.

Hopefully that will be fast enough for you.