Proth Test Limits

[amcfarlane]

I'm a little confused by Proth's Theorem (http://mathworld.wolfram.com/ProthsTheorem.html)...

If I were to write a function which performed a proth test given the pair of values n, and k; how would I know when to stop iterating through values for a.

As I understand it, there appears to a 50% chance that any given 'a' value will work.

However, say I write a function that iterates a from 1 to 1000, surely there is a chance, albeit a small chance) that none of those values will work, although a number > 1000 ~may~ work.

Is there a hard limit for a, or should I be looking at the percentages - after all 10 values for a would give me a very high percentage chance of at least one of the working?

[R.D. Silverman]

Originally Posted by amcfarlane

I'm a little confused by Proth's Theorem (http://mathworld.wolfram.com/ProthsTheorem.html)...

If I were to write a function which performed a proth test given the pair of values n, and k; how would I know when to stop iterating through values for a.

As I understand it, there appears to a 50% chance that any given 'a' value will work.

However, say I write a function that iterates a from 1 to 1000, surely there is a chance, albeit a small chance) that none of those values will work, although a number > 1000 ~may~ work.

Is there a hard limit for a, or should I be looking at the percentages - after all 10 values for a would give me a very high percentage chance of at least one of the working?

Yes, there is a hard, fully proven limit. Unfortunately, it is exponential
in the size of the number bering tested. The result is due to Burgess.
If GRH is true, than a much smaller limit can be proved: 2 log^2 N.
The constant 2 is due to E. Bach.