Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Общие вопросы по .NET и C# > Тест Ферма сквозь числа Кармайкла?!

Автор: PsiMagistr 17.5.2020, 17:29

Код


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
В чем же дело?

Автор: james93 28.5.2020, 09:47

This is such a great resource that you are providing and you give it away for free. https://bloonstowerdefense5.io