Что не так с этой реализацией Поллард Ро - PullRequest
Новая
       15

Что не так с этой реализацией Поллард Ро

1 голос
/ 18 мая 2011 
#include <iostream>
#include <cstdlib>
typedef  unsigned long long int ULL;
ULL gcd(ULL a, ULL b)
{
   for(; b >0 ;)
   {
       ULL rem = a % b;
       a = b;
       b = rem;
   }
   return a;
}
void pollard_rho(ULL n)
{
   ULL i = 0,y,k,d;
   ULL *x = new ULL[2*n];
   x[0] = rand() % n;
   y = x[0];
   k = 2;
   while(1){
       i = i+1;
       std::cout << x[i-1];
       x[i] = (x[i-1]*x[i-1]-1)%n;
       d = gcd(abs(y - x[i]),n);
       if(d!= 1 && d!=n)
          std::cout <<d<<std::endl;
       if(i+1==k){
         y = x[i];
         k = 2*k;
       }
   }
}

int main()
{
   srand(time(NULL));
   pollard_rho(10);

}

Эта реализация является производной от CLRS 2-е издание (Страница № 894).while(1) выглядит подозрительно для меня.Каким должно быть условие завершения цикла while?

Я пытался k<=n, но, похоже, это не работает.Я получаю ошибку сегментации.Что за недостаток в коде и как его исправить?

Ответы [ 3 ]

1 голос
/ 18 мая 2011

Зачем хранить все эти промежуточные значения? Вам действительно не нужно помещать x и y в массив. Просто используйте 2 переменные, которые вы продолжаете использовать, x и y.

Также замените while(1) на while(d == 1) и обрежьте цикл до 

 if(d!= 1 && d!=n)
      std::cout <<d<<std::endl;
   if(i+1==k){
     y = x[i];
     k = 2*k;

Таким образом, ваш цикл должен стать 

while(d == 1)
{
    x = (x*x - 1) % n;
    y = (y*y - 1) % n;
    y = (y*y - 1) % n;
    d = abs(gcd(y-x,n))%n;
}
if(d!=n)
  std::cout <<d<<std::endl;
else
  std::cout<<"Can't find result with this function \n";

Дополнительные точки, если вы передаете функцию, используемую в цикле в качестве параметра, pollard, поэтому, если он не может найти результат с одной функцией, он пытается другую.

1 голос
/ 18 мая 2011

У меня есть только 1-е издание CLRS, но при условии, что оно не слишком отличается от 2-го издания, ответ на условие расторжения приведен на следующей странице:

Эта процедура поискафактор может показаться несколько загадочным на первый взгляд.Обратите внимание, однако, что POLLARD-RHO никогда не печатает неправильный ответ;любое число, которое он печатает, является нетривиальным делителем n .ПОЛЛАРД-РО может вообще ничего не печатать;нет никаких гарантий, что это даст какие-либо результаты.Однако мы увидим, что есть веские основания ожидать, что POLLARD-RHO напечатает коэффициент p из n после приблизительно sqrt ( p ) итераций в то время как петля.Таким образом, если n является составным, мы можем ожидать, что эта процедура обнаружит достаточное количество делителей для полного коэффициента n после приблизительно n 1/4 обновление, поскольку каждый простой множитель p из n , за исключением, возможно, самого большого, меньше sqrt ( n ).

Тактехнически говоря, презентация в CLRS не имеет условия завершения (возможно, именно поэтому они называют ее «эвристической» и «процедурой», а не «алгоритмом»), и нет никаких гарантий, что она когда-либо действительно даст что-то полезное,На практике вы, вероятно, захотите установить некоторую итерацию, основанную на ожидаемых n 1/4 обновлениях.

0 голосов
/ 18 мая 2011

Попробуйте заменить while(1) { i = i + 1; на это: 

for (i = 1; i < 2*n; ++i) {
...