Accuracy increase in determination composite number by probabilistic primality tests

Abstract

Accuracy increasing problem became important after there were found so-called numbers of Carmichael, and it became evident that the simplest primality test based on Fermat’s Little Theorem failed. Since then, many tests have been offered which have been more efficient than Fermat’s, and the first successful results were made by Lehmer. The Miller-Rabin test is considered as most important probabilistic test with sufficient accuracy, complexity and computational costs. This article is meant to give some comparison between existing probabilistic primality tests in current use, and also to present results found in which accuracy may be increased.