Proth's Theorem (1878): Let n = h. 2^k + 1 with 2^k > h.

If there is an integer a such that a^[(n-1)/2] = -1 (mod n), then n is

prime.

Examining small integers which satisfy the condition 2^k > h of proth's

theorem

n 2^k h

3 = 2 * 1 + 1

5 = 2^2 * 1 + 1

9 = 2^3 * 1 + 1

13 = 2^2 * 3 + 1

17 = 2^4 * 1 + 1

25 = 2^3 * 3 + 1

33 = 2^5 * 1 + 1

41 = 2^3 * 5 + 1

It seems clear that the chance of n satisfying this condition, 2^k > h, of

Proth drops very

quickly as n becomes larger.

How critical is this condition to primeness?

I understand that this condition is critical to the proof of primeness.

I am asking, what is the probability that a given n would be prime

if n = 2^k * h + 1, where h > 2^k and

for some a, a^[(n-1)/2] = -1 ?

I expect that the answer could be determined only empirically in terms of

the size of n.