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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# 2^k + n (mod p)

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**