How to handle a large modulus? I am researching on Proth-numbers, i.e. numbers of the form $n :=h\cdot 2^k + 1$, where $h$ odd and $h<2^k$. There is a test:

If there exists an $a$ such that $a^{\frac{n-1}{2}}\equiv -1 \pmod n$, then $n$ is prime.

My problem is computing this modpower. Most programming languages have a fast powermod-function, but if $k$ is very large, it will still take a lot of time. So I wondered if there is a better way.
Since I do not know whether $n$ is prime or composite, I can't make a statement about possible divisors.
I would be glad already if I had the info that this congruence does NOT hold.
So, does anyone know whethere there are maybe sufficient or necessary conditions?
 A: Comment: May be these facts from the book (number theory by Sierpinski) help you to filter the numbers you test and reduces the time of calculations:
1-Particular case where in $n=h\cdot 2^k+1$, $h=k$; in this case it can be shown that for any odd prime p there exist infinitely many number like h such that $p|h\cdot 2^h+1$.
Proof: If p is an odd prime and :
$n=(p-1)(k\cdot p+1)$
we will have:
$n\equiv -1 \bmod p$
and n is divisible by $(p-1)$
and due to Fermat little theorem $2^n\equiv 1 \bmod p$ and number $n=h\cdot 2^h+1$ will be divisible by p.
We can conclude that there are infinitely many composite numbers in the form $h\cdot2^h+1$ . These numbers are called Cullen numbers.The known Cullen prime numbers are with $h=1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548$ and $6679881$. It has been shown that almost all Cullen numbers $C_n$ are composite!
2- In other case $h\neq k$, it can be shown there exist infinite numbers like h such that number $n=h\cdot 2^k+1 $ is composite.
Proof: We know $F_m=2^{2^m}+1$  for $m= 0, 1, 2, 3, 4$ , $F_m $ is prime and $F_5=641 p$ , where $p>F_4=2^{16}+1$  is prime. Also $F_5$ is divisible by $p$ and we have:
$(p, F_5-2)=1 \Rightarrow (p, 2^{32}-1)=1$
Now due to Chinese remainder theorem there exists infinitely many natural numbers like k which satisfy following congruences:
$k\equiv 1[\bmod(2^{32}-1)\cdot 641]$
and:
$k\equiv -1\bmod p$
It can be proved that if natural number $k>p$ and satisfy these congruences then all numbers $k\cdot 2^n+1 $ are composite.
