Форумы на Хакер

Добро пожаловать! Это — архивная версия форумов на «Хакер.Ru». Она работает в режиме read-only.

Опишите пожалуйста тест на простоту Рабина-Карпа

Пользователи, просматривающие топик: none

Зашли как: Guest

Все форумы >> [Компилируемые языки] >> Опишите пожалуйста тест на простоту Рабина-Карпа

Имя

Сообщение

<< Старые топики Новые топики >>

Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-25 20:15:09.340000

Promlol

Сообщений: 19
Оценки: 0
Присоединился: 2010-04-04 23:00:01.010000

Не могу найти в инете описание этого теста, может у кого и на С код есть?

Post #: 1

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-25 20:31:34.290000

Denaturat

Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000

quote:

ORIGINAL: Promlol

Не могу найти в инете описание этого теста, может у кого и на С код есть?

http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

ты точно ничего не перепутал?

Post #: 2

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-25 20:32:32.746666

Родригес

Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000

quote:

Не могу найти в инете описание этого теста

Может тест на простоту Миллера — Рабина?

Post #: 3

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-25 22:24:09.073333

Promlol

Сообщений: 19
Оценки: 0
Присоединился: 2010-04-04 23:00:01.010000

да точно, есть у кого исходник теста Миллера-Рабина на С?

Post #: 4

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-26 02:20:17.540000

Denaturat

Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000

quote:

ORIGINAL: Promlol

есть у кого исходник теста Миллера-Рабина на С?

у всех, умеющих пользоваться открытыми источниками:

http://rosettacode.org/wiki/Miller-Rabin_primality_test#C

но вот скажи - что мешало тебе написать реализацию самому?

Post #: 5

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-26 10:43:55.870000

Promlol

Сообщений: 19
Оценки: 0
Присоединился: 2010-04-04 23:00:01.010000

ой, некрасивый код, какой-то, я сам сделал, более простой и короткий

p.s. попросил выложить, потому что времени не хватает =\\ еще 6 лаб до конца семестра надо сдать по объектно-ориентированному программмированию =\\

Post #: 6

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-26 10:54:26.426666

Родригес

Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000

quote:

я сам сделал, более простой и короткий

Может поделишся с общественностью?

Post #: 7

RE: Опишите пожалуйста тест на простоту Рабина-Карпа - 2010-04-26 18:15:35.176666

Promlol

Сообщений: 19
Оценки: 0
Присоединился: 2010-04-04 23:00:01.010000


 int test_prime(int N)
 {
  int a,n,m,k=0,i,T,chet=0;
 
  n=N-1;
  m=n;
  while((m%2)==0)
  {
  &nbsp;&nbsp;&nbsp; m=m/2;
  &nbsp;&nbsp;&nbsp; k++;
  }
  for(a=2;a&lt;11;a++)
  {
  &nbsp;&nbsp;&nbsp; T=mod_pow(a,m,N);
  &nbsp;&nbsp;&nbsp; if(T==1 || T==n)
  &nbsp;&nbsp;&nbsp; {
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; chet++;
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; T =0;
  &nbsp;&nbsp;&nbsp; }
  &nbsp;&nbsp;&nbsp; for(i=1;i&lt;k;i++)
  &nbsp;&nbsp;&nbsp; {
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; T=(T*T) % N;
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (T == 1) 
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; {
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; chet--;
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; break;
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }
 
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (T == n) 
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; {
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; chet++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; break;
  &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }
  &nbsp;&nbsp;&nbsp; }
  }
  if(chet==9)
  &nbsp;&nbsp;&nbsp; return 1;
  else
  &nbsp;&nbsp;&nbsp; return 0;
 }

делал по http://www.intuit.ru/department/security/mathcryptet/12/5.html#example.12.2

Post #: 8

Страниц: [1]

Все форумы >> [Компилируемые языки] >> Опишите пожалуйста тест на простоту Рабина-Карпа

Связаться:
Вопросы по сайту / xakep@glc.ru

Предупреждение: использование полученных знаний в противозаконных целях преследуется по закону.