When using a probabilistic algorithm, how is the probability that the number is composite expressed mathematically?
If we repeat the test n times and pass every time, then the probability that our number is composite is 1/(1-p)n, which decreases exponentially with the number of tests, so we can be as sure as we like (though never perfectly sure) that the number is prime.
При использовании вероятностного алгоритма, как математически выражается вероятность того, что число является составным?
Если мы повторим тест n раз и пройдем каждый раз, то вероятность того, что наше число является составным, равна 1/(1-p)n, что экспоненциально уменьшается с количеством тестов, поэтому мы можем быть уверены, насколько нам нравится (хотя никогда не бывает полностью уверен), что число простое.