Алгоритмы тестирования на простоту и факторизации

Определение 2.1 Время работы алгоритма $$T(n)$$ имеет верхнюю оценку $$g(n)$$ (пишут $$T(n)=O(g(n))$$, читают "О большое от $$g$$ от $$n$$"), если существует натуральное число $$n_0$$ и положительная постоянная $$c$$ такие, что $$\forall n>n_0$$ выполняется неравенство: $$T(n)\leq c\cdot g(n)$$.

Пример 2.1 Докажем, что функция $$T(n)=3n^3 + 2n^2$$ имеет верхнюю оценку $$O(n^3)$$.

Действительно, положим $$n_0=1$$, $$c\geq 5$$. Тогда $$\forall n\geq n_0=1$$ выполняется неравенство $$3n^3 + 2n^2 \leq c n^3$$. Следовательно, $$T(n)=O(n^3)$$.

Оценка сложности алгоритма - важнейший вопрос для криптографии, поскольку от оценки сложности решающим образом зависит стойкость соответствующей криптосистемы.

Далее мы будем рассматривать алгоритмы (в основном теоретико-числовые) и в большинстве случаев будем приводить оценку сложности представленного алгоритма.

2.1 Тестирование на простоту

Существует два типа критериев простоты: детерминированные и вероятностные. Детерминированные тесты позволяют доказать, что тестируемое число - простое. Практически применимые детерминированные тесты способны дать положительный ответ не для каждого простого числа, поскольку используют лишь достаточные условия простоты.

Детерминированные тесты более полезны, когда необходимо построить большое простое число, а не проверить простоту, скажем, некоторого единственного числа.

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

На сегодня известно достаточно много алгоритмов проверки чисел на простоту. Несмотря на то, что большинство из таких алгоритмов имеет субэкспоненциальную оценку сложности, на практике они показывают вполне приемлемую скорость работы.

На практике рассмотренные алгоритмы чаще всего по отдельности не применяются. Для проверки числа на простоту используют либо их комбинации, либо детерминированные тесты на простоту.

Детерминированный алгоритм всегда действует по одной и той же схеме и гарантированно решает поставленную задачу. Вероятностный алгоритм использует генератор случайных чисел и дает не гарантированно точный ответ. Вероятностные алгоритмы в общем случае не менее эффективны, чем детерминированные (если используемый генератор случайных чисел всегда дает набор одних и тех же чисел, возможно, зависящих от входных данных, то вероятностный алгоритм становится детерминированным).

2.1.1 Вероятностные тесты простоты

Для того чтобы проверить вероятностным алгоритмом, является ли целое число $$n$$ простым, выбирают случайное число $$a$$, $$1<a<n$$, и проверяют условие алгоритма. Если число $$n$$ не проходит тест по основанию $$a$$, то алгоритм выдает результат "Число $$n$$ составное", и число $$n$$ действительно является составным.

Если же $$n$$ проходит тест по основанию $$a$$, нельзя сказать о том, действительно ли число $$n$$ является простым. Последовательно проведя ряд проверок таким тестом для разных $$a$$ и получив для каждого из них ответ "Число $$n$$, вероятно, простое", можно утверждать, что число $$n$$ является простым с вероятностью, близкой к 1. Если вероятность того, что составное число пройдёт тест, равна $$p$$, то для обеспечения вероятности $$p_0$$ того, что проверенное число является простым, необходимо сделать $$m = \lceil log_p (1-p_0)\rceil$$ итераций (см. рис 1.1}).

2.1.2 Тест Ферма

Согласно малой теореме Ферма для простого числа $$p$$ и произвольного целого числа $$a$$, $$1 < a < p-1$$, выполняется сравнение:

Следовательно, если для нечетного $$n$$ существует такое целое $$a$$, что $$1 \leq a \leq n$$, $$НОД(a,n)=1$$ и $$a^{n-1} \equiv 1 ~(\mod n)$$, то число $$n$$ вероятно простое. Таким образом, получаем следующий вероятностный алгоритм проверки числа на простоту:

Вход: нечетное целое число $$n\geq 5$$.

Выход: "Число $$n$$, вероятно, простое" или "Число $$n$$ составное".

На шаге 1 алгоритма мы не рассматриваем числа $$a = 1$$ и $$a = n-1$$, поскольку $$1^{n-1} \equiv 1 ~(\mod n)$$ для любого целого $$n$$ и $${(n-1)}^{n-1} \equiv {(-1)}^{n-1} \equiv 1 ~(\mod n)$$ для любого нечетного $$n$$.

Сложность теста Ферма равна: $$O(\log^3 n)$$.

Тест имеет существенный недостаток в виде наличия чисел Кармайкла. Это нечетные составные числа, для которых сравнение из формулы выполняется при любом $$a$$, $$1 \leq a \leq n-1$$, взаимно простом с $$n$$. Для всех $$a$$, $$НОД(a,n)=1$$, тест будет выдавать ошибочный результат.

Числа Кармайкла являются достаточно редкими. В пределах до 100000 существует лишь 16 чисел Кармайкла: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

2.1.3 Тест Леманна

Если для какого-либо целого числа $$a$$, меньшего $$n$$, не выполняется условие:

то число $$n$$ - составное. Если это условие выполняется, то число $$n$$ - возможно простое, причем вероятность ошибки не превышает 50%.

Таким образом, получаем следующий вероятностный алгоритм проверки числа на простоту:

Вход: нечетное целое число $$n \geq 5$$.

Выход: "Число $$n$$, вероятно, простое" или "Число $$n$$ составное".

Сложность теста Леманна равна $$O(log^3 n)$$.

2.1.4 Тест Соловея-Штрассена

В основе этого теста лежит следующая теорема:

Теорема 1.28 (критерий Эйлера) Нечетное число $$n$$ является простым тогда и только тогда, когда для любого целого числа $$a$$, $$1 \leq a \leq n-1$$, взаимно простого с $$n$$, выполняется сравнение:

где $$\left(\dfrac{a}{n}\right)$$ - символ Якоби от параметров $$a$$ и $$n$$.

Критерий Эйлера лежит в основе следующего вероятностного теста числа на простоту:

Вход: нечетное целое число $$n \geq 5$$.

Выход: "Число $$n$$, вероятно, простое" или "Число $$n$$ составное".

На шаге 1 мы снова не рассматриваем числа $$1$$ и $$n-1$$, поскольку в силу свойств символа Якоби сравнение в формуле (2.1) для этих чисел выполняется при любом нечетном $$n$$. Если $$d=НОД(a,n)>1$$, то $$d$$ делит и число $$r$$, вычисляемое на шаге 2. Таким образом, при проверке неравенства $$ r\neq 1$$ на шаге 3 автоматически проверяется условие $$НОД(a,n)\neq 1$$.

Сложность теста Соловэя-Штрассена определяется сложностью вычисления символа Якоби и равна $$O(\log^3 n)$$.

Для теста Соловея-Штрассена не существует чисел, подобных числам Кармайкла, то есть составных чисел, которые были бы эйлеровыми псевдопростыми по всем основаниям $$a$$.

2.1.5 Тест Миллера-Рабина

На сегодняшний день для проверки чисел на простоту чаще всего используется тест Миллера-Рабина, основанный на следующем наблюдении. Если $$p$$ - простое, и $$x^2 = 1 ~(\mod p)$$, то $$x=1$$ или $$-1 ~(\mod p)$$.

Пусть число $$n$$ нечетное и $$n-1=2^{s}r$$, где $$r$$ - нечетное. По малой теореме Ферма, если $$n$$ - простое, то $$a^{n-1}=1~(\mod n)$$ для любого натурального числа $$a<n$$. Из нашего наблюдения следует, что, в ряду элементов $$a^r, a^{2r},\ldots, a^{2^{s-1}r}$$ при каком-либо $$i$$ мы будем иметь $$a^{2^i r} = -1~(\mod p)$$ и $$a^{2^j r} = 1~(\mod p)$$ при $$j>i$$.

Это свойства лежит в основе следующего теста:

Вход: нечетное целое число $$n\geq 5$$.

Выход: "Число $$n$$, вероятно, простое" или "Число $$n$$ составное".

В результате выполнения теста для простого числа $$n$$ в последовательности $$a^r ~(\mod n), a^{2r} ~(\mod n), \dots, a^{2^{s-1}r} ~(\mod n)$$ обязательно перед 1 должна появиться $$-1$$ (или, что то же самое, $$n-1 ~(\mod n)$$). Это означает, что для простого числа $$n$$ единственными решениями сравнения $$y^2 \equiv 1 ~(\mod n)$$ являются $$y\equiv \pm 1 ~(\mod n)$$. Если число $$n$$ составное и имеет $$k>1$$ различных простых делителей (то есть не является степенью простого числа), то по китайской теореме об остатках существует $$2^k$$ решений сравнения $$y^2\equiv 1 ~(\mod n)$$. Действительно, для любого простого делителя $$p_i$$ числа $$n$$ существует два решения указанного сравнения: $$y\equiv \pm 1 ~(\mod p)_i$$. Поэтому $$k$$ таких сравнений дают $$2^k$$ наборов решений по модулям $$p_i$$, содержащих элементы $$\pm 1$$.

Сложность теста Миллера-Рабина равна $$O\left( (\log n)^3 \right)$$. Вероятность ошибки, то есть того, что тест объявит составное число простым, не более $$1/4$$.

2.1.6 N - 1-алгоритмы генерации простых чисел

Перечислим некоторые теоремы, которые могут быть использованы для генерации доказуемо простых чисел [1].

Теорема 2.1 (Прот, 1878) Пусть $$n=2^k R+1$$, где $$R<2^k$$, $$3< 2^k+1$$, и $$3$$ не делит $$R$$. Тогда $$n$$ - простое тогда и только тогда, когда

Для генерации простого числа нужно перебирать числа $$R$$ и $$k$$ и для каждого варианта проверять условие (2.2). Когда условие будет выполнено, полученное число $$n=2^k R+1$$ будет простым.

Недостатком этого подхода является плохое распределение генерируемых простых чисел: все они будут иметь вид $$2^k R+1$$ для большого $$k$$ и не очень большого $$R$$. В примере 1.42 мы также видели, что чем меньше простые делители числа $$p-1$$, тем легче осуществить дискретное логарифмирование по модулю $$p$$. Это делает генерируемые на основе теоремы Прота простые числа мало пригодными, например, для криптосистемы и электронной подписи Эль-Гамаля.

Теорема 2.2 (Диемитко, 1988) Пусть $$n=qR+1>1$$, где $$q$$ - нечетное простое число, $$R$$ - четное, и $$R<4(q+1)$$. Если существует целое число $$a$$ такое, что

то $$n$$ простое число.

С помощью этой теоремы генерировать простые числа можно итерационно. На вход каждой итерации подаётся какое-либо простое число $$q$$. Во время итерации перебираются числа $$R$$ и $$a$$ и проверяются условия теоремы Диемитко. Как только все условия выполнены, мы получили новое простое число $$n$$, порядок которого примерно вдвое больше, чем у исходного простого числа $$q$$. Итерации можно начинать с какого-либо известного простого числа, а заканчивать, когда полученное простое число достигнет требуемого размера.

На заключительной итерации желательно выбирать как можно меньшее число $$R$$. Тогда у полученного простого числа $$n-1$$ будет большой простой делитель $$q$$. Если подобрать достаточно малое $$R$$ не получится, может потребоваться выполнить заново предыдущую итерацию для получения нового числа $$q$$.

Эта теорема лежала в основе алгоритма генерации простых чисел для алгоритма цифровой подписи ГОСТ 34.10-94, пока этот алгоритм не был заменён на новый, основанный на группе точек эллиптической кривой.

2.1 Парадокс дней рождения

Теорема 2.3 Пусть $$\lambda>0$$. Для случайной выборки объёма $$l+1$$ из $$n$$ элементов, где $$l =\sqrt{2\lambda n}$$, вероятность $$p$$ того, что все элементы выборки будут попарно различны, допускает следующую оценку сверху:

Следствие 2.1 (Парадокс дней рождения) Чтобы с вероятностью $$>0,5$$ обнаружить двух людей, празднующих день рождения в один день, достаточно рассмотреть всего 23 человека.

Этот парадокс допускает следующие применения в криптографии.

2.2.1 Алгоритм Полларда для факторизации натурального числа

Пусть нам требуется факторизовать натуральное число $$n$$, то есть найти любой его нетривиальный делитель. Один из простейших алгоритмов приведён ниже [1]. Алгоритм будет вычислять псевдослучайную последовательность $$x_0, x_1,\ldots, x_l$$. Вероятность $$p$$ того, что $$НОД (|x_i - x_j|, n) > d$$ можно оценить по теореме 2.4. Если $$q$$ - минимальный делитель числа $$n$$, то множество $$\mathbb{Z}$$ разбивается на $$q$$ классов, причем если $$x_i$$, $$x_j$$ лежат в одном классе, то $$НОД(x_i-x_j,n)$$ делится на $$q$$. Итак, в теореме 2.4 находим $$\lambda = \dfrac{l^2}{2q}$$, и $$p<e^{-\lambda}$$.

Если $$x_i-x_j=0 ~(\mod q)$, $i<j$$, а $$2^r$$ - наименьшая степень двойки, большая $$i$$, то $$x_{2^r}-x_{j+(2^r-i)}=0~(\mod q)$$. Поэтому вместо того, чтобы сравнивать все пары $$x_i$$, $$x_j$$ с произвольными $$i,j$$, имеет смысл сравнивать пары:

Для сравнения среди таких пар достаточно хранить $$x_{2^k}$$ и $$x_m$$, тогда как для поиска среди всех пар нужно хранить все пары.

Правда, такая хитрость требует увеличить длину последовательности. Допустим, наименьшие $$j$$ и $$i$$, для которых $$НОД(x_j-x_i,n)>1$$, равны, соответственно, $$l$$ и $$0$$. Тогда

Поскольку мы сравниваем $$x_{2^k}$$ и $$x_{m}$$, где $$m<2^{k+1}$$, то у нас $$2^{k+1}>l+2^k$$, то есть $$2^{k} > l$$. Итак, нужно выбрать наименьшее $$k$$ такое, что $$2^k > l$$ и вычислить не $$l+1$$, а $$m=2^k + l$$ членов последовательности.

Отметим, что при фиксированном $$q$$ длина $$l$$ вычисляемой последовательности пропорциональна $$\sqrt{n}$$ - верхней оценке наименьшего простого делителя $$q$$. Таким образом, данный алгоритм имеет сложность, экспоненциальную по числу бит числа $$q$$.

Пример 2.2 С помощью $$\rho$$-алгоритма Полларда найти нетривиальный простой делитель числа $$n=2449$$.

На первом шаге алгоритма требуется выбрать многочлен $$f(x)$$ для генерации последовательности $$x_i$$. Возьмём $$f(x) = x^2 + 1$$. Выберем длину $$l$$ последовательности так, чтобы найти в ней повтор с вероятностью $$p\geq 0,5$$. $$q\leq\sqrt{2449}<50=q_0$$ - оценка сверху для наименьшего простого делителя $$q$$ числа $$N$$. Итак, $$0.5< p < e^{-\lambda}$$, откуда $$-\lambda > ln 0,5 = 0,693147$$. Тогда

Допустим, в последовательности $$x_0,\ldots,x_9$$ есть повтор. Чтобы гарантированно его найти с помощью приведённого алгоритма, нужно вычислить не меньше $$25$$ её членов. В самом деле, так как $$2^3<9<2^4=16$$, то $$k=4$$, и необходимое число членов: $$25=16+9$$.

Выберем $$x_0=10$$.

Итак, нам повезло найти нетривиальный делитель 31 числа 2449. Если бы мы досчитали до $$x_{25}$$ и не нашли повтор, то нам лучше было бы выбрать новый $$x_0$$ (в качестве него можно взять $$x_{25}$$) и начать алгоритм сначала.

2.2.2 Алгоритм Полларда для дискретного логарифмирования

Изменим алгоритм предыдущего параграфа так, чтобы с его помощью решать задачу дискретного логарифмирования. Его идея остаётся прежней: мы будем вычислять последовательность $$x_0, x_1, \ldots$$ и будем находить среди них пары $$x_i=x_j$$ чисел. Зададим последовательность так, чтобы это равенство давало нам дискретный логарифм.

Найдём $$y$$ из условия $$a^y = b ~(\mod p)$$, где $$p$$ - простое число.

Определим последовательности $$u_i$$, $$v_i$$, $$x_i$$ следующим образом:

Тогда если $$x_i=x_j$$, то $$b^{u_{i}-u_{j}} = a^{v_{i}-v_{j}}$$, откуда

Коллизия $$x_i=x_j$$ ищется тем же способом, что и в предыдущем параграфе.

Отметим, что данный алгоритм может быть также обобщен для дискретного логарифмирования в произвольной циклической группе, и даже для поиска коллизий хэш-функций.

2.3 Компьютерные вычисления с большими числами

Как мы увидим в третьей главе, трудноразрешимые задачи, на которых основаны современные системы защиты информации, являются трудноразрешимыми только при использовании действительно больших чисел - размером в тысячи двоичных знаков. В данном параграфе мы рассмотрим некоторые инструменты программиста, полезные для работы с такими числами.

2.3.1 Калькулятор для больших чисел

При отладке любой программы, работающей с большими числами, часто приходится проводить какие-либо вычисления вручную, сравнивая их с результатами программы, и в этом помог бы калькулятор, работающий с большими числами. Стандартный калькулятор Windows непригоден для этих целей.

Играть роль калькулятора для больших чисел хорошо могут системы компьютерной алгебры. Помимо коммерческих систем, таких как Maple или Mathematica, существуют системы компьютерной алгебры с открытым исходным кодом, вполне подходящие для наших целей. Рассмотрим в качестве примера систему компьютерной алгебры Maxima, которую в виде дистрибутива для Windows, либо в виде исходных кодов можно загрузить с её официального сайта http://maxima.sourceforge.net/.

Maxima может работать как интерактивная среда командной строки, в режиме тетради (отличается от предыдущего тем, что введённые ранее команды можно поправлять и запускать заново) так и в виде неинтерактивного интерпретатора языка программирования Maxima, являющегося надстройкой над языком Lisp.

В качестве примера рассмотрим работу с Maxima в режиме тетради. После установки Maxima такой режим доступен из-под любой из двух графических оболочек Maxima: wxmaxima и xmaxima. На рисунке рис 2.1 показан пример сеанса в графической среде wxmaxima.

В строках %i9, %i22, и т.д. пользователь вводил команду и по нажатии Shift+Enter получал ответ в соответствующих строках %o9, %o22, ...

Отметим лишь некоторые полезные для нас команды. Их подробное описание можно найти в поставляемой с maxima документцией.

2.3.2 Программирование с большими числами в C/C++

При написании сложных систем защиты информации не обойтись без компилируемого языка программирования высокого уровня, например, C++. Стандартный тип целых чисел в C/C++ позволяет работать с числами не более 64 двоичных знаков, чего мало для криптографических приложений. Существуют библиотеки для C/C++, реализующие операции с большими числами и другие полезные криптографические функции. Отметим лишь некоторые из них, предоставляемые бесплатно с открытым исходным кодом:

BN_add(x, y, z);
     

Рассмотрим настройку окружения программиста для использования библиотеки Cryptopp.

Пример 2.3 Написать программу, принимающую два целых положительных числа A и B и вычисляющую символ Якоби $$\left(\dfrac{A}{B}\right)$$.

Решение.

а) С помощью среды программирования Visual Studio 2010

Для Visual Studio придётся собирать библиотеку Cryptopp из исходных кодов, доступных на официальном сайте: http://www.cryptopp.com/.

После распаковки архива с исходными кодами нужно открыть и собрать решение cryptest.sln.

Нам понадобятся следующие файлы:

Создадим в Visual Studio 2010 проект "Win32 Console Application". Для того, чтобы в нашей программе использовать cryptopp, необходимо зайти в свойства нашего проекта (см. рис 2.2)

и указать

Файл cryptopp.dll необходимо скопировать в папку, в которой будет размещаться исполняемый файл нашей программы.

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

Код нашего проекта будет выглядеть следующим образом:

#include <dll.h>   //Этот файл должен быть включен до всех 
                   //остальных заголовочных файлов библиотеки
#include <iostream>//Модуль ввода/вывода стандартной библиотеки
                   //C++

#include <integer.h>//В этом заголовочном файле определяется 
                    //класс Integer больших чисел

using namespace std;
using namespace CryptoPP;//Все функции cryptopp находятся в 
                         //пространстве имен CryptoPP

//Функция, вычисляющая символ Якоби
int JacobiSymbol(Integer A, Integer P)
{
  //В самом начале P > 2 и нечетно (проверяется в main())
  int result = 1;
  while (true)
  {
    //Статический метод Gcd класса Integer вычисляет наибольший 
    //общий делитель; если он не равен единице, то символ Якоби
    //будет равен нулю (легко следует из определения)
    if (Integer::Gcd(A, P) > 1)
      return 0;
    
    //Теперь P > 1, НОД(A, P) = 1

    //Равные по модулю P числа являются или не являются 
    //квадратичными вычетами одновременно
    if (A >= P)
      A = A % P; 
    
    //Теперь 1 < A < P, P > 1, НОД(A, P) = 1

    //Отделить четную часть числа A. Определим, на какую 
    //степень двойки делится число A, и символ Якоби 2 по P
    //найдём по свойству.
    int pwr_ = 0;
    while (A.GetBit(pwr_) == false)
      pwr_++;
    if (pwr_ >0)
    {
      A>>=pwr_; //Поделить A на степень двойки
      int pwroftwo = pwr_%2;
      if (pwroftwo == 1)
        if ((P*P-1)%16 != 0)
          result *= -1;
      continue;
    }
    
    //Теперь A нечетно, P > 1, A < P, НОД(A, P) = 1
    if (A == 1)
      break;

    //Теперь A, P нечетны, больше 1 и взаимно просты. Поэтому
    //можно применить квадратичный закон взаимности. 
    if (((A - 1) * (P - 1))%8 != 0)
      result *= -1;
    A.swap(P);
    
    //Теперь снова P > 1 и нечетно, поэтому можно
    //возвращаться в начало цикла.
  }
  return result;

}

int main(int argc, char** argv)
{
  if (argc==3)
  {
    //Проверить корректность аргументов командной строки
    bool correctnumbers = true;
    for (int j=1; j<=2; j++)
      for (int i=0; argv[j][i]!='\0'; i++)
        if ((argv[j][i]<'0') || (argv[j][i]>'9'))
          correctnumbers = false;
    //Если аргументы корректны, посчитать их символ Якоби
    if (correctnumbers == true)
    {
      Integer a(argv[1]);
      Integer b(argv[2]);
      if (b<3)
        cout<<"Jacobi symbol (a/b) is not defined for b="
        <<b<<endl;
      else
      {
        cout<<JacobiSymbol(a,b)<<endl;
        return 0;
      }
    }
  }
  cout<<"Expected two positive integer numbers"<<endl;
  return -1;
}
\end{verbatim}
    

После сборки программу нужно запускать из консоли. Например:

\verb|testcrypt.exe 51 343543|
    

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

Серьёзным минусом данного подхода является необходимость приобретать Microsoft Visual Studio для разработки под Windows. Не станем перечислять причины, по которым в бесплатной версии Microsoft Visual Studio Express описанные нами действия не приведут к успеху.

б) В операционных системах семейства linux

В операционных системах семейства linux огромное количество библиотек, доступных разработчику, запакованы в специальные архивы, называемые пакетами. Отличие пакета от архива в том, что между пакетами существуют зависимости, позволяющие программе установки автоматически устанавливать не только библиотеку или программу, которую попросил пользователь, но и все требуемые для их работы дополнительные библиотеки. Обычно библиотека и заголовочные файлы к ней запаковываются в разные пакеты. Пакет с заголовочными файлами, как правило, имеет суффикс -dev или -devel.

В linux-системах, основанных на Debian GNU/Linux, для разработки с использованием cryptopp требуется установка всего двух пакетов. Все действия можно выполнить из коммандной строки с правами администратора:

# apt-get install libcrypto++-dev
    

Благодаря автоматической системе распознавания зависимостей также будет установлена нужная версия библиотеки libcrypto++.

Как и в Windows, в Linux доступно множество сред разработки. Действия, производимые в среде разработки Eclipse (с подключенным расширением CDT - C Development Tools), аналогичны нашим предыдущим действиям в Visual Studio.

Недостаток проектов Eclipse (так же, как и Visual Studio) в том, что в них явно указывается путь к заголовочным файлам, которые на другом компьютере могут располагаться в другой директории. Поэтму рекомендуется создать файл проекта, не зависящий от среды разработки, например, проект в системе сборки Cmake (см. http://www.cmake.org/documentation/).

Для автоматического поиска заголовочных файлов и самой библиотеки используется система pkgconfig. Её можно использовать из cmake-проекта следующим образом.

cmake_minimum_required(VERSION 2.4)
project(jacobi)
INCLUDE(FindPkgConfig)
pkg_check_modules(CRYPTOPP REQUIRED libcrypto++)
include_directories(${CRYPTOPP_INCLUDEDIR} ${CRYPTOPP_INCLUDEDIR}/cryptopp)
link_directories(${CRYPTOPP_LIBRARY_DIRS})
add_executable(jacobi jacobi.cpp)
target_link_libraries(jacobi ${CRYPTOPP_LIBRARIES})
     

\verb|cmake  make|
     

Для отладки программы, снабженной файлом Cmake-проекта, можно использовать интегрированные среды разработки. Одна из лучших сред разработки с поддержкой Cmake - QtCreator.

Список литературы