I want to test Proth's numbers for primality. These are numbers of the form $h\cdot 2^k+1$ for a natural $k$ and an odd $h<2^k$. I am wondering whether I can find a faster method than the "normal" trialdivision. So my thought is: Let $p$ be an odd prime. Then we have $$ h\cdot 2^k+1\equiv 0 \pmod p \Leftrightarrow h\cdot 2^k\equiv -1 \pmod p \Leftrightarrow h\cdot 2^k\equiv -1 \pmod p $$
So I could check whether $$2^k \equiv -(h^{-1})\pmod p$$ or $$ h\equiv -2^{-k}\pmod p $$ is true. I wrote a short script, but is is very slow. Is that normal or is there a chance to get an improved trial division by these congruences?
