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.