|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 27 Nov 2001 18:28:36
To : Pavel V. Reich
Subject : Простое число?
--------------------------------------------------------------------------------
Replying to a message of Pavel V. Reich to All:
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> такой теореме)
Малая теорема Ферма утверждает, что если p простое и a не делиться на p, то
a**(p-1) = 1 mod p.
Из нее сразу следует, что если для какого-то n число a**(n-1) <> 1 mod n, то n -
составное.
PVR> и получается ли проверка?
Hадо сказать, в чистом виде эта проверка достаточно хилая. Есть составные числа
(например, Кармайкла), которые на ура проходят эту проверку.
Значительно лучше использовать вероятностный тест Милера-Рабина.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Простое число? 
