I was working on a problem with numbers of the form [itex]2^k+n[/itex] for k (potentially) large and n fixed. I pre-sieve candidate primes in the range by finding a value f such that whenever [itex]k=f\pmod{p-1}[/itex] it holds that [itex]p|2^k+n[/itex], 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 [itex]k=f\pmod m[/itex] it holds that [itex]p|2^k+n[/itex], for some [itex]m|p-1[/itex]. 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?
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 [itex]k=f\pmod m[/itex] it holds that [itex]p|2^k+n[/itex], for some [itex]m|p-1[/itex]. 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?