ComSec作业二：EGCD

ComSec

/*
* File : GMP_EGCD.cpp
* Author : Hongpei Lin
* Date : 20190910
* Update : 20190921
* Update comment : function EGCD() retrun a array of mpz_t including r,s,d.
* Purpose : using "GMP" to achieve EGCD algorithm
*/
#include <iostream>
#include "gmpxx.h"
using namespace std;
mpz_t * EGCD(mpz_t a, mpz_t b);
int main()
{
    mpz_t a, b;
    mpz_inits(a, b, NULL);
    gmp_printf("please input number a and b\n");
    gmp_scanf("%Zd%Zd", a, b);
    mpz_t * answer;
    answer = EGCD(a, b);
    gmp_printf("We get that d=%Zd, r=%Zd, s=%Zd", answer[0], answer[1], answer[2]);
    system("pause");
    free(answer);
    mpz_clears(b, a, NULL);
}
mpz_t * EGCD(mpz_t a, mpz_t b)
{
    mpz_t * result;
    result = (mpz_t *)malloc(3 * sizeof(mpz_t));
    mpz_t  r0, r1, s0, s1, q, temp_r0, temp_s0, mul, mod, d;
    mpz_init_set_str(r0, "1", 10);
    mpz_init_set_str(r1, "0", 10);
    mpz_init_set_str(s0, "0", 10);
    mpz_init_set_str(s1, "1", 10);
    mpz_inits(q, temp_r0, temp_s0, mul, mod, d, NULL);
    while (!(mpz_sgn(b) == 0))
    {
        //GCD
        mpz_tdiv_q(q, a, b);//q=a/b
        mpz_tdiv_r(mod, a, b);//b=a%b
        mpz_init_set(a, b);//a=b
        mpz_init_set(b, mod);
        //gmp_printf("a=%Zd,b=%Zd\n", a, b);
        mpz_init_set(temp_r0, r0);
        mpz_init_set(temp_s0, s0);
        mpz_init_set(r0, r1);//r0=r1
        mpz_init_set(s0, s1);//s0=s1
        //r1=r0-r1*q
        mpz_mul(mul, r1, q);
        mpz_sub(r1, temp_r0, mul);
        //s1=s0-s1*q
        mpz_mul(mul, s1, q);
        mpz_sub(s1, temp_s0, mul);
    }
    mpz_init_set(result[0], a);
    mpz_init_set(result[1], r0);
    mpz_init_set(result[2], s0);
    mpz_clears(d, mod, mul, temp_s0, temp_r0, q, s1, s0, r1, r0, NULL);
    return result;
}