Wikipedia:Reference desk/Archives/Mathematics/2018 August 30
| Mathematics desk | ||
|---|---|---|
| < August 29 | << Jul | August | Sep >> | Current desk > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
August 30
editConfusion concerning a "level of confidence" calculation
editI'm in the process of implementing the Miller-Rabin primality test and I'd like to allow the user to pass a "confidence" parameter in the form of a number on the interval of (0, 1]. That is to say 1 being "absolutely certain", 1/2 being a 50% level of certainty, etc. Now the article states that the minimum number of trials needed in order for the test to be deterministic (based on the assumption that the Generalized Riemann Hypothesis is indeed true) is 2 log^2 N, then goes on to say that the error term for a given number of K trials is 4^(-K). I assume that means that after say 3 trials there would be a 4^(-3) = 1.5625% chance that the test returns a false result or conversely a 1-4^(-3) = 98.4375% level of certainty. What confuses me though is that the size of N is not taken into account here. I would expect, for example, a confidence level of 100% to translate to 2 log^2 N trials. In other words how am I supposed to merge these together to obtain an equation which converts a confidence level into a minimum number of trials needed? Earl of Arundel (talk) 16:48, 30 August 2018 (UTC)
- 4^(-K) and 2 log^2 N are unrelated numbers related to different properties of the algorithm. Don't try to connect them. The probability that a number which passes the algorithm with K random bases is actually composite is lower than 4^(-K). It's just a weak bound. The actual probability may be far lower. Use the bound 4^(-K) if you want to give a confidence level saying "at least this confident". The 2 log^2 N count for certainty is based on an unproven conjecture so it isn't actually certain. You can easily pick K large enough that the risk of hardware or software error is far greater than the 4^(-K) bound so I suggest you just forget about 2 log^2 N. Note that 2 log^2 N requires use of the smallest bases while 4^(-K) requires random bases. You want random bases for a confidence level. Otherwise you may be fooled by a composite number deliberate designed to pass small bases. PrimeHunter (talk) 17:49, 30 August 2018 (UTC)
- I see! Well that clears things up. So I guess what I'll do then is just offer up two variants, one probabalistic and the other (presumably) deterministic. I say that because there doesn't seem to be a shred of evidence indicating that GRH could possibly be false (see this paper for example) so I'm just going to go ahead and assume it to be so, prima facie. In fact since the experimental evidence overwhelmingly indicates that the lower bound for a deterministic test is actually less than log N I may well just use that as the low-water mark instead. (Or at least give the user the choice to decide between the "strict" or "lax" criteria). Earl of Arundel (talk) 19:02, 30 August 2018 (UTC)
- On a side note I just found a paper by Damgård, Landrock, and Pomerance which actually does provide an equation for a probabalistic error bound in terms of the number of bits K in N for T trials. Earl of Arundel (talk) 20:20, 30 August 2018 (UTC)
- I see! Well that clears things up. So I guess what I'll do then is just offer up two variants, one probabalistic and the other (presumably) deterministic. I say that because there doesn't seem to be a shred of evidence indicating that GRH could possibly be false (see this paper for example) so I'm just going to go ahead and assume it to be so, prima facie. In fact since the experimental evidence overwhelmingly indicates that the lower bound for a deterministic test is actually less than log N I may well just use that as the low-water mark instead. (Or at least give the user the choice to decide between the "strict" or "lax" criteria). Earl of Arundel (talk) 19:02, 30 August 2018 (UTC)
Do I understand this error-term in the probabilistic Miller-Rabin test correctly?
editAs described above in my earlier post the Damgård-Landrock-Pomerance paper gives a maximum error-term of (K^(3/2))(2^T)(T^(-1/2))(4^(2(-((TK)^(1/2))))) [where K is the number of bits in N and T is the number of trials]. The really unusual thing about that is the fact that [1] the error-term actually seems to grow inversely-proportional to the size of of K and [2] when I plug into the equation say 5 trials for a given number containing for example anywhere between 8 to 18446744073709552000 bits (!!!) I obtain an error-term somewhere on the order of 10^(-40) in either case. Can that possibly be right? The fourth answer provided by user Warren MacEvoy in this Stackoverflow thread seems to support such a conclusion but it just seems too unbelievable to be true. Earl of Arundel (talk) 22:28, 30 August 2018 (UTC)
- The paper says the formula applies for 3 ≤ t ≤ k/9, k ≥ 21, so you should not use it on k = 8. I get completely different numbers so I guess you are not evaluating the formula correctly. I get 0.81 for the dissallowed t = 5, k = 8, and 3.5×10−5782087095 for t = 5, k = 18446744073709552000. PrimeHunter (talk) 22:57, 30 August 2018 (UTC)
- Yeah my calculator pretty much exploded on that equation. So the takeaway here is that anywhere between 5 and 20 random trials is pretty much more than sufficient in any case I suppose? (I'll be using a hard-coded set of bases for all N less than 2^81 anyhow). Earl of Arundel (talk) 23:21, 30 August 2018 (UTC)
- Also, any idea why the error-term growth is inversely-proportional to the number of bits? Seems rather counterintuitive to say the least! Earl of Arundel (talk) 23:30, 30 August 2018 (UTC)
- The error term approaches zero faster than inversely-proportional to the number of bits. The test computes something modulo n where n is the candidate. The larger n is, the more potential values modulo n there are, and only one of those values means that n is a probable prime. Any other value proves that n is composite. It sounds sensible to me that the larger n is, the larger is the probability that n really is prime when the special value occurs. PrimeHunter (talk) 23:53, 30 August 2018 (UTC)
- Interesting! It does indeed make sense when you explain it that way. Well thanks for the comments, very much appreciated. Earl of Arundel (talk) 00:06, 31 August 2018 (UTC)
- The error term approaches zero faster than inversely-proportional to the number of bits. The test computes something modulo n where n is the candidate. The larger n is, the more potential values modulo n there are, and only one of those values means that n is a probable prime. Any other value proves that n is composite. It sounds sensible to me that the larger n is, the larger is the probability that n really is prime when the special value occurs. PrimeHunter (talk) 23:53, 30 August 2018 (UTC)
- @Earl of Arundel: Also, if you have a relatively small limit on the size of numbers you will be testing, you can use data here to give a small number of Miller-Rabin tests that is certain to be correct. In the programs I write, I only use numbers , so I can use a small number of M-R tests. Bubba73 You talkin' to me? 02:15, 31 August 2018 (UTC)
- Agree, that's really the best approach for smaller numbers. I haven't seen any set of bases for numbers much larger than 2^81 yet but I'm keeping my eyes open. Anyway thanks for the link, I'll be sure to bookmark. :) Earl of Arundel (talk) 03:00, 31 August 2018 (UTC)
- @Earl of Arundel: Also, if you have a relatively small limit on the size of numbers you will be testing, you can use data here to give a small number of Miller-Rabin tests that is certain to be correct. In the programs I write, I only use numbers , so I can use a small number of M-R tests. Bubba73 You talkin' to me? 02:15, 31 August 2018 (UTC)
