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

while(L2>0){ i++; Ll==mpz_size(A); L2=mpz_size(B); double r=mpz_fdivq_ui(A,B); // Take rests of least limbs of A, В ny module к a=(A->_mp_d[0] )‘/,k; b = (B->_mp_d[0]) У, k; q = (a*InvK(b,k) У, k; // Compute q=AB“{-l} (mod k) beta=(r-q)/к; int sO=int(beta); alpha=beta-sO; // beta=alpha+sO sum of fraction and int parts of beta Farey(k, alpha, m,n); // proc Farey computes approximating fraction m/n for alpha x=n; y-=q*n+(m+sO*n)*k;// y-=-y mpz_mul_ui(Tl,A,x);// Tl=Ax mpz_mul_ui(T2,B,y-);// T2=-By int d=mpz_cmp(Tl,T2);// Compare T1 and T2 if(d>0)mpz_sub(C,Tl,T2); if(d<0)mpz_sub(C,T2,Tl); // C=Ax+By if(d==0) goto finl;// Case Ax+By=0. mpz_fdiv_q_ui(С,С ,к);// C=(Ax+By)/к while((C->_mp_d[0])y,2==0) mpz_fdiv_q_ui(C,C,2); // Divide C by 2 while C is even mpz_set(A,B); mpz_set(B,C); \\ go to the next iteration } return A; > Основной цикл представляет собой одну итерацию, в которой по паре нечетных чисел А ,В , А > В , вычисляются целые числа х, у, такие что О< х < к,у < 0, Ах + B y = 0(mod к), Ах « —By. (3) После этого вычисляется число С = \(Ах + В у)/к \, С проверяется на четность и если четно, то сокращается на 2 до тех пор, пока не станет нечетным. После этого выполняется присвоение значений А = В , В = С, и выполняется переход к следующей итерации. Нами была приведена грубая схемы вычисления НОД с помощью аппроксимирующего алгоритма. Приведем пример вычислений по этому алгоритму для 33-битовых чисел А и В и к = 64: 16