Jump to content

Talk:Solovay–Strassen primality test

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Section: accuracy of the test

In fact the article doesn't prove that for a given number half of smaller numbers are witnesses. It only proves that *if there is one witness* then there are many more, but it doesn't prove the existence.

And in this section witnesses and liars called "Euler", but Euler witnesses where are in Euler primality test. I think, it's copypaste error, because proofs of "if where is one witness where are many ones" are very simular for all Fermat-like primality tests. — Preceding unsigned comment added by 92.100.182.15 (talk) 17:11, 25 August 2012 (UTC)[reply]

Relying on the prime probability estimation p/n = 1/2 is quite rough, i think its better to base on Bertrand-Chebyshev theorem. — Preceding unsigned comment added by Al Leween (talkcontribs) 22:23, 12 June 2012 (UTC)[reply]