Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел

длинных положительных чисел mpz_t и набор основных операций с этим форматом чисел. Описание переменной типа mpz_t выполняется так же, как и обычных типов, то есть командой mpz_t список переменных, разделенных запятой; после чего переменные, перечисленные в этом списке должны быть инициализированы командой mpz_init. Переменная типа mpz t являет­ ся указателем на блок памяти, выделенной переменной этого типа. После использования переменной память, занимаемая переменной, может быть освобождена командой mpz_clear. Приведем пример программирования алгоритма Евклида вычисле­ ния НОД для пары длинных чисел А и В, А > В: mpz_t Euclid (mpz_t A, mpz_t В){ mpz_t С; mpz_init(C); size_t L=mpz_size(B); while (L>0){ mpz_fdiv_r(C, A, B); mpz_set(A, B); mpz_set(B, C); L=mpz_size(B); } return A; mpz_clear(C); } В этой процедуре команда mpz_set присваивает значение второго операнда первому, а команда mpz_fdiv_r вычисляет остаток от деления второго операнда на третий и заносит полученное значение в первую пе­ ременную. Длина переменной типа mpz_t определяется функцией mpz_size и вычисляется в лимбах, где лимб - это длина регистра процессора компью­ тера, в котором установлена библиотека, т.е. лимб равен 32 или 64 битам. Если число не превышает 264 для 64-битового процессора, то длина такого числа равна 1. Условие mpz_size(B)> 0 эквивалентно условию В > 0, но выполняется быстрее. Перейдем теперь к программированию аппроксимирующего алгорит­ ма. mpz_t AKA(mpz_t A, mpz_t В, int k){ mpz_t AA, BB; int i=0, a, b, q, m, n,x,y,y-; double r,alpha, beta; mpz_init_set(AA, A); mpz_init_set(BB, B); // copy A, В to AA, BB j size_t L1,L2; 15