>>Почему "увы"?
> существуют так называемые числа Кармайкла (561), которые удовлетворяют сравнению Ферма, но не
> являются простыми на самом деле

Да и пусть их существуют. Мне-то что с того? Ну, возьмём любую практическую задачу, например, создание ключей для RSA. Мне нужно два простых числа, я могу сгенерировать два числа, которые будут простыми. Эмм... Точнее, насколько я помню RSA, мне нужны не столько два простых числа p и q, сколько произведение pq, которое никто не сможет разложить на множители. А для этого полезно, если и p, и q будут простыми. Но, если память меня подводит, то это не суть важно. Я могу используя вероятностные тесты получить два числа, которые с вероятностью X, будут простыми, где X настолько близок к 1, насколько мне нужно. Не, я соглашусь, если бы X был бы равен единице, было бы лучше, но практически это не важно, потому что вероятность того, что вся схема сработает как надо, всё равно будет ниже единицы. Как ни крути. Либо дыра в реализации протокола/алгоритма, либо пользователь лоханётся, либо ключи уведут, либо математики найдут способ факторизации... Я могу сделать вероятность лоханутся на выборе "простых" множителей настолько низкой, что она не будет идти ни в какое сравнение со всеми остальными вероятностями проколов.

>>Какая разница с практической точки зрения?
> Математики, особенно занимающиеся "чистой" её частью, практической выгоды не ищут.

В том-то и разница. Если математики найдут практический способ факторизовывать числа, то RSA моментально кончится, и мне не будет нужно генерировать простые числа для RSA. 100% надёжный способ генерации простых чисел, таким образом, совершенно непрактичен. Хоть и с теоретической точки зрения, было бы восхитительно такой способ найти.