Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.04.2008, 18:54
РСАйзер

 
Сообщений: n/a

Тест простоты Рабина
Вопрос возник после прочтения http://algolist.manual.ru/maths/teornum/rabmil.php.
[Цитата]
Тест Рабина выдает ответ 'm -- составное число' в случае, если
1) xt =/= 1 (mod m), или
2) в последовательности x0, x1, x2, ..., xt имеется фрагмент вида ..., *, 1, ... где звездочкой обозначено число, отличное от единицы или минус единицы по модулю m.
В противном случае тест Рабина выдает ответ "не знаю". Последовательность x0, x1, ..., xt в этом "плохом" случае либо начинается с единицы, либо содержит (-1) где-нибудь не в конце.
[/Цитата]
С первым пунктом все понятно, но вот с интерпретацией второго... Если единица хоть раз встретится в последовательности x0...xt, разве не будут все последующие члены последовательности также равны единице? Поэтому меня особенно смущает часть "либо содержит (-1) где-нибудь не в конце." Что это значит?
  #2  
Старый 05.04.2008, 12:30
гость

 
Сообщений: n/a

Цитата:
разве не будут все последующие члены последовательности также равны единице?
Будут.

Суть теста Рабин-Миллера в том, что для любого простого p, уравнение x^2 = 1 (mod p) имеет всегда ровно два решение: 1 и -1 (есть теоремы утверждающие это), и, как следствие, если возводя какое-то число в квадрат мо модулю p ты случайно обнаружишь какой-то еще корень, то это налицо доказывает что p не простое.
  #3  
Старый 06.04.2008, 12:02
гость

 
Сообщений: n/a

Кусок кода из статьи:

isprime:=true;
q:=p-1;
repeat q:=q shr 1; until odd(q);
for i:=1 to Rounds do
begin
{$IFDEF USE32}
a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
if powmod(a,p-1,p)<>1 then
begin
isprime:=false; break;
end;
a:=powmod(a,q,p);
if a<>1 then
begin
while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p); //зачем проверка (а<>p-1)?
if a=1 then
begin
isprime:=false; break;
end;
end;
end;

Зачем проверка (а<>p-1)?
  #4  
Старый 06.04.2008, 12:22
гость

 
Сообщений: n/a

p-1 это тоже самое что и -1 по модулю p.

А зачем -1 -- см. пост выше
  #5  
Старый 06.04.2008, 12:29
гость

 
Сообщений: n/a

Цитата:
Поэтому меня особенно смущает часть "либо содержит (-1) где-нибудь не в конце." Что это значит?
А в конце у тебя будет просто число a^{p-1} (mod p).
По теореме Ферма, если p простое, то оно должно быть равно 1, и если нет, то p - не простое.

Если -1 встречается не в конце, то после него в последовательности будут идти только одни единицы, и в этом случае ничего о простоте p сказать нельзя.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Тест для АВЛ-дерева Straight Реализация, исходники, языки 0 18.10.2007 21:26
тест простоты Рабина гость Математические алгоритмы (другое) 2 26.09.2007 19:27