Реализация теста Миллера-Рабина

[mrChester]

Появилась такая проблема, нигде не могу найти рабочей реализации вероятностного теста числа на простоту Миллера-Рабина. В сети имеется псевдокод на него, пробовал делать по нему но не выходит, думаю что есть какая-то ошибка в самом псевдокоде. Может кто сможет помочь в этом вопросе? Мне не обязательно выполнять операции с длинными числами, хотя бы те что входят в диапазон long... Желательно код на C++

[mrChester]

вот мой код который в принципе не работает...

void __fastcall TForm1::Button1Click(TObject *Sender)
{Label3->Caption="";
 long m,r,s=0,t,x,a;
 m=StrToInt(Edit1->Text);
 r=StrToInt(Edit2->Text);
 while (!((m-1)%int(pow(2,s)))) s++;
 s--;
 t=(m-1)/pow(2,s);
 bool pr;
 randomize();
 for (int i=0; i<r; i++)
  {pr=true;
   a=random(m-3)+2;
   x=long(pow(a,t))%m;
   if ((x==1)||(x==m-1)) continue;
   for (int k=0; k<s; k++)
    {x=long(pow(a,pow(2,k)*t))%m;
     if (x==1) {Label3->Caption="Составное"; break;}
     if (x==m-1) {pr=false; break;}
    }
   if (pr) {Label3->Caption="Составное"; break;}
  }
 if (Label3->Caption!="Составное")
  Label3->Caption="Простое";
}

[mrChester]

Проблема решилась не успев начаться ))))
В строке:
x=long(pow(a,pow(2,k)*t))%m;
происходил выход за границы типа long, максимальное простое число, которое удается проверить без выхода за границы типа 17...
А кто-нибудь может сделать то же самое но на языке maple?

[mrChester]

Сообщение от mrChester

Проблема решилась не успев начаться ))))
В строке:
x=long(pow(a,pow(2,k)*t))%m;
происходил выход за границы типа long, максимальное простое число, которое удается проверить без выхода за границы типа 17...
А кто-нибудь может сделать то же самое но на языке maple?

Этот код удалось оптимизировать...

x=(x*x)%m; - результат тотже

[mrChester]

Сообщение от mrChester

x=long(pow(a,t))%m;

в этой строке выполняется возведение в степень, опять таки получается большое число, вот фрагмент как от этого избавиться, но появляется большая проблема с временем выполнения программы числа порядка 10^10 проверяет около 3 минут... может кто поможет еще как-нибудь оптимизировать...
сразу скажу что в С++ такие числа проверить не сможете, я делал в maple...
моя цель: проверять числа порядка 10^300, ну или хотя бы 10^100

x=1;
while (t>0)
{x=(x*a)%m;
t--;
}