Finding an f for 2^k+n: A Number Theory Problem

[CRGreathouse]

I was working on a problem with numbers of the form $2^k+n$ for k (potentially) large and n fixed. I pre-sieve candidate primes in the range by finding a value f such that whenever $k=f\pmod{p-1}$ it holds that $p|2^k+n$, and test a large range of k values.

1. The search for such an f is computationally expensive, since I search in an essentially brute-force manner. Is there a number-theoretic way of getting this directly? I feel like there should be.
2. Sometimes 'more is true': whenever $k=f\pmod m$ it holds that $p|2^k+n$, for some $m|p-1$. Since I test the f values sequentially, this is not the case if 2f > p-1. When 2f < p-1, is there a good way to find values of m that work?

 

[fresh_42]

I'd say the Euclidean algorithm should do. It should at least give you a lower bound. There are primality tests which use ERH and are fast. I would look at them whether the ideas can be used here.