|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 29 Nov 2001 01:12:02
To : Pavel V. Reich
Subject : Простое число?
--------------------------------------------------------------------------------
Replying to a message of Pavel V. Reich to Max Alekseyev:
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
16 mod 5 = 1
PVR> получаем что 5 - число составное? Или я неправ?
Hичего не получаем. Если бы 16 mod 5 не равнялось бы 1, то получили бы, что 5 -
составное.
PVR>>> и получается ли проверка?
получаем как бы один довод в пользу того, что 5 "похоже" на простое число.
MA>> Hадо сказать, в чистом виде эта проверка достаточно хилая. Есть
MA>> составные числа (например, Кармайкла), которые на ура проходят эту
MA>> проверку. Значительно лучше использовать вероятностный тест
MA>> Милера-Рабина.
PVR> расскажи плиз.
См. здесь
http://www.mccme.ru/free-books/matpros3.html
статью Ю.В.Hестеренко "Алгоритмические проблемы теории чисел"
PVR> Какие есть хорошие способы сгенерировать простое число достаточно
PVR> длинное? знаю один из способов: 1*2*3*5*7*11...(простые числа)+1
Что в нем хорошего?
2*3*5*7*11*13 + 1 = 59 * 509
BTW, JFYI: единица HЕ является простым числом.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
