VPF::Тест Ферма сквозь числа Кармайкла?!

PsiMagistr

Дата 17.5.2020, 17:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 479
Регистрация: 31.12.2009

Репутация: нет
Всего: 1

Код


private Boolean isPrime(BigInteger num)
        {
            for (int i = 2; i <= 100; i++) //Сто попыток, меняем основание.
            {               
                    var n = BigInteger.ModPow(i, num - 1, num);
                    if (n != 1) //Если нечетное, то точно непростое.
                    {
                        return false;
                    }
                             
            }
            return true;   //Вероятно простое.            
        }

Друзья, перед вами вероятностный тест на простоту Ферма, который выполняется 100 раз с разными основаниями степеней.
Существуют так называемые числа Кармайкла, которые данный тест распознает как простые, несмотря на то, что они составные, сколько бы мы не меняли основание. Однако этот алгоритм как ни странно распознает числа Кармайкла. Например 561
В чем же дело?

Это сообщение отредактировал(а) PsiMagistr - 17.5.2020, 18:05

--------------------

"Арфы нет? Возьмите бубен!

Ребята, будем жить!"

(с) "В бой идут одни старики"

---

"ИЕ" - один из самых сумасшедших браузеров в нашей галактике.

james93

Дата 28.5.2020, 09:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 28.5.2020

Репутация: нет
Всего: нет

This is such a great resource that you are providing and you give it away for free. bloons tower defense 5

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »