|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 29 Nov 2001 13:53:51
To : Pavel V. Reich
Subject : Re: Простое число?
--------------------------------------------------------------------------------
Wed Nov 28 2001 14:23, Pavel V. Reich wrote to Max Alekseyev:
PVR>>> В поисках оптимального алгоритма проверки числа на простое ли?
PVR>>> натолкнулся на функцию в rsa.cpp (rsa-cpp.zip) вот комментарий:
PVR>>> // Test based on Fermats theorem a**(p-1) = 1 mod p for prime
PVR>>> p // For 1000 bit numbers this can take quite a while -Windows
PVR>>> Clipboard- Интересует что это за Теорема Ферма (впервые слышу о
PVR>>> такой теореме)
MA>> Малая теорема Ферма утверждает, что если p простое и a не делиться на
MA>> p, то a**(p-1) = 1 mod p. Из нее сразу следует, что если для какого-то
MA>> n число a**(n-1) <> 1 mod n, то n - составное.
PVR> a=2
PVR> p=5
PVR> 2**(5-1)=16
PVR> 1 mod 5=1
PVR> 16!=1
PVR> получаем что 5 - число составное? Или я неправ?
Вы неправильно понимаете смысл выражения a^(n-1)=1 mod n
Его надо трактовать так: остатки от деления обеих частей равенства на n равны.
В данном случае
16 mod 5 =1
И число не относится этим к составным.
PVR> Какие есть хорошие способы сгенерировать простое число достаточно
PVR> длинное? знаю один из способов:
PVR> 1*2*3*5*7*11...(простые числа)+1
PVR> Hо некриптостойкое для алгоритмов наподобие RSA.
Hет. Этот способ (восходящий к Эвклиду) доказать, что ряд простых чисел
бесконечен. Положим, что есть максимальное простое число. Тогда строим новое
описанным способом вплоть до максимального. Оно будет либо простым
(противоречие с предположением о существовании максимального простого!), либо
составным, не делящимся на все простые, вплоть до "максимального",
следовательно, делящимся на простое, большее максимального (опять
противоречие!). Следовательно, максимального простого не существует.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
