ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Krotoff 2:5020/400 28 Nov 2001 15:07:35
To : Pavel V Reich
Subject : Re: Простое число?
--------------------------------------------------------------------------------
Pavel V. Reich <Pavel.V.Reich@f75.n5004.z2.fidonet.org> wrote:
PVR> В поисках оптимального алгоритма проверки числа на простое ли? натолкнулся
PVR> на функцию в rsa.cpp (rsa-cpp.zip) вот комментарий:
PVR> ДWindows ClipboardД
PVR> // Test based on Fermats theorem a**(p-1) = 1 mod p for prime p
PVR> // For 1000 bit numbers this can take quite a while
PVR> ДWindows ClipboardД
PVR> Интересует что это за Теорема Ферма (впервые слышу о такой теореме)
PVR> и получается ли проверка? для 5 у меня получается
PVR> 2**(5-1)=16
PVR> 1 mod 5=1
Ошибка здесь. = 1 mod 5 - это не остаток от деления.
x=y mod z (читается x сравнимо с у по модулю z)
означает что x-y делится без остатка на z.
PVR> 16!=1;
PVR> а насколько я понял - должно быть простым числом.
PVR> Заранее благодарен за ответы.
16 = 1 mod 5 потому что (16-1)=15 делится на 5.
--
Успехов,
Саша.
--- ifmail v.2.15dev5
* Origin: Он знал Сашу Бло. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
