Проверка больших чисел на простоту

итак. скрестил алгоритм миллера-рабина с ntl. ну как скрестил... нашёл) с помощью всего этого дела можно определить, является ли число простым с достаточно высокой вероятностью. метод итерационный. чем больше итераций, тем выше точность. идеально для распределенной обработки.

вот, собственно сам код:

#include <NTL/ZZ.h>

NTL_CLIENT
long witness(const ZZ& n, const ZZ& x)

{
  ZZ m, y, z;

  long j, k;

  if (x == 0) return 0;

  k = 1;

  m = n/2;

  while (m % 2 == 0) {

    k++;

    m /= 2;

  }

  z = PowerMod(x, m, n); // z = x^m % n

  if (z == 1) return 0;

  j = 0;

  do {

    y = z;

    z = (y*y) % n; 

    j++;

  } while (j < k && z != 1);

  return z != 1 || y != n-1;

}

long PrimeTest(const ZZ& n, long t)

{

   if (n <= 1) return 0;
   PrimeSeq s; 

   long p;

   p = s.next();  

   while (p && p < 2000) {

      if ((n % p) == 0) return (n == p);

      p = s.next();  

   }
   ZZ x;

   long i;

   for (i = 0; i < t; i++) {

      x = RandomBnd(n); 



      if (witness(n, x)) 

         return 0;

   }
   return 1;

}

всё просто кроме самого алгоритма) он тоже не сложный, но надо вникать)

Работа со сверхбольшими числами в С++

итак. разбираюсь со сверх большими числами. теми, которые ни в один тип не влазят.
нашел интересную библиотеку под это дело. NTL называется. качать отсюда www.shoup.net/ntl/download.html
пока тестил только под винду, но думаю под линух проблемм возникнуть не должно.
коротко, что надо сделать:
1. само собой распаковываем архив куда-нибудь аля c:\ntl
2. надо руками скомпилить библиотеку под себя. можно использовать vc, можно mingw. я делал в визуалке.
поэтапно

File -> New -> Projects 
project name: ntl
location: c:\ntl_lib
Win32 static library
OK
Finish
OK

Project -> Add to Project -> Files
добавляем всё из c:\ntl\WinNTL-xxx\src.
xxx - номер версии. будут какие-то числа

Project -> Settings -> C/C++ 
Категория: Preprocessor.
Additional include directories: c:\ntl\WinNTL-xxx\include.
Click on OK.
Build -> build ntl.lib

3. если вдруг компилироваться не будет, выдавая огромное количество ошибок, надо покопаться в cinfig.h. мне помогла замера

#if 1
#define NTL_STD_CXX

на

#if 0
#define NTL_STD_CXX

(поставили 0 - вырубили опцию)

Вот и всё. у нас есть либа. теперь подключаем ее к проекту и можем работать со сколь угодно большими числами...
пример:

#include <NTL/ZZ.h>
NTL_CLIENT
int main()
{ 
ZZ a, b, c; 
cin >> a; 
cin >> b; 
c = (a+1)*(b+1);
cout << c << "\n";
}

и на сколько бы большие целые мы не ввели в a и b, всё будет считаться.
вот еще примеры: www.shoup.net/ntl/doc/tour-examples.html

это круто.