mersenneforum.org > Math Proth Test Limits
 Register FAQ Search Today's Posts Mark Forums Read

 2006-07-22, 16:12 #1 amcfarlane     Nov 2004 UK 2·19 Posts Proth Test Limits 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?
2006-07-23, 18:29   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post nucleon Hardware 8 2015-04-25 23:01 davieddy Lounge 10 2012-12-04 18:43 Dubslow GPU to 72 29 2011-12-30 18:43 siegert81 Miscellaneous Math 2 2011-02-17 13:37 wblipp Software 0 2003-11-22 23:00

All times are UTC. The time now is 11:57.

Sun Sep 20 11:57:43 UTC 2020 up 10 days, 9:08, 0 users, load averages: 1.94, 1.85, 1.59