0
0 комментариев

Функция проверки числа на простоту по малой теореме Ферма:

import math
import random
 
def is_prime(num, test_count):
    for i in range(test_count):
 
        rnd = random.randint(1, num - 1)
 
        if (rnd ** (num - 1) % num != 1):
            return False
 
    return True
 
print(is_prime(13, 10))

Сказано, что надо выполнять большее кол-во тестов, чтобы результат был точнее (чтобы с меньшей вероятностью наткнуться на «обманщиков» Ферма»).


В книге Рода Стивенсона «Алгоритмы» сказано: «..для натурального числа p минимум половина значений n между 1 и p — свидетели Ферма… Вам может не повезти, и вы возьмете в качестве n обманщика Ферма…введите сюда описание изображения


Сам вопрос: я проводил тесты и никак не находил этих «обманщиков» Ферма… Кроме, собственно числа 1. Как «наткнуться» на это число, или я что-то неправильно понял/делаю?


Добавить комментарий