Operaciones en Zn

main.cpp

/*
*   C++ - Operaciones en Zn
*   Copyright 2014 J. Martin Cruz Otiniano
*   Description :   Contiene los metodos de adición, multiplicicación, inverso multiplicativo, división y exponenciación.
*   Site        :   martincruz.me
*/

#include <iostream>
#include <cstdlib>
#include "OperacionZn.h"

using namespace std;

void menu()
{
    cout << "\n\n\tOperaciones en Zn            \n\n";
    cout << "\t 1. Adicion                      \n";
    cout << "\t 2. Multiplicacion               \n";
    cout << "\t 3. Inverso multiplicativo       \n";
    cout << "\t 4. Division                     \n";
    cout << "\t 5. Exponenciacion               \n";
    cout << "\t 6. Radicacion                   \n";
    cout << "\t 7. Salir                        \n";

    cout << "\n\t Opcion >  ";
}


int main()
{
    OperacionZn  operacion;
    //peracionZn* op;

    int         opcion;  // menu
    int         zn;      // Zn = {1, 2, 3,..., n}
    int         _a;
    int         _b;

    do
    {
        menu(); cin >> opcion;

        op = new OperacionZn();

        cout << endl;

        switch (opcion)
        {
            case 1:
                cout << "\t Ingrese a: "; cin >> _a;
                cout << "\t Ingrese b: "; cin >> _b;
                cout << "\t Zn       : "; cin >> zn;
                cout << "\t Suma     : " << operacion.adicion(_a, _b, zn) << endl;
                break;

            case 2:
                cout << "\t Ingrese a     : "; cin >> _a;
                cout << "\t Ingrese b     : "; cin >> _b;
                cout << "\t Zn            : "; cin >> zn;
                cout << "\t Multiplicacion: " << operacion.multiplicacion(_a, _b, zn) << endl;
                break;

            case 3:
                cout << "\t Ingrese a   : "; cin >> _a;
                cout << "\t Zn          : "; cin >> zn;

                int inv;
                inv = operacion.inv_multiplicativo(_a, zn);

                if (inv == -1)
                    cout << "\n\t No es invertible! \n";
                else
                    cout << "\t Inverso : " << inv << endl;
                break;

            case 4:
                cout << "\t Ingrese a : "; cin >> _a;
                cout << "\t Ingrese b : "; cin >> _b;
                cout << "\t Zn        : "; cin >> zn;

                int div;

                div = operacion.division(_a, _b, zn);

                if (div == -1)
                    cout << "\n\t No se puede efectuar la division! \n";
                else
                    cout << "\t Division : " << div << endl;
                break;

            case 5:
                cout << "\t Ingrese a     : "; cin >> _a;
                cout << "\t Ingrese k     : "; cin >> _b;
                cout << "\t Zn            : "; cin >> zn;
                cout << "\t Exponenciacion: " << operacion.exponenciacion(_a, _b, zn) << endl;
                break;

            case 6:
                break;

            case 7:
                exit(0);

            default:
                cout << "\n\n\t Opcion incorrecta! \n";
        }

        //delete(op); // eliminando objeto

        cout << endl;
        system("pause");
        system("cls");

    } while(opcion != 6);


    return 0;
}

OperacionZn.cpp

/*
*   C++ - Operaciones en Zn
*   Copyright 2014 J. Martin Cruz Otiniano
*   Description :   Contiene los metodos de adición, multiplicicación, inverso multiplicativo, división y exponenciación.
*   Site        :   martincruz.me
*/

#include "OperacionZn.h"

OperacionZn::OperacionZn()
{
    //ctor
}

OperacionZn::~OperacionZn()
{
    //dtor
}
int OperacionZn::adicion(int a, int b, int n)
{
    if (a + b < n)
        return a + b;
    else                //  a + b >= n
        return a + b - n;
}

int OperacionZn::multiplicacion(int a, int b, int n)
{
    return (a * b) % n;
}

int OperacionZn::inv_multiplicativo(int a, int n)
{
    vector<int> _mcd;

    _mcd = euclides_extendido(n, a);

    int d  = _mcd[0];
    int x  = _mcd[1];
    int y  = _mcd[2];

    cout << "\t mcd = " << d << endl;

    if (d != 1)
    {
        return -1;  // No es inversible!
    }
    else
    {
        if (y < 0)
            return y + n;
        else
            return y;
    }
}

int OperacionZn::division(int a, int b, int n)
{
    int inverso_b;

    inverso_b = this->inv_multiplicativo(b, n);

    if (inverso_b == -1)
        return -1;
    else
        return (a * inverso_b) % n;
}

int OperacionZn::exponenciacion(int a, int k, int n)
{
    int exp;
    int xp;

    exp = 1;
    xp  = a % n;

    while (k > 0)
    {
        if (k % 2 != 0)
            exp = (exp * xp) % n;

        xp = (xp * xp) % n;
        k  = k / 2;
    }

    return exp;
}

vector<int> OperacionZn::euclides_extendido(int a, int b)
{
    vector<int> arr(3, 0);        // [d, x, y]
    int         x1, x2, y1, y2;   // variables temporales
    int         q, r;             // variables cociente y resto

    // Caso base
    if (b == 0) {
        arr[0] = a;     // d
        arr[1] = 1;     // x
        arr[2] = 0;     // y
        return arr;
    }

    // Inicializamos variables
    x1 = 0; x2 = 1;
    y1 = 1; y2 = 0;

    while (b > 0) {
        q       = a / b;
        r       = a - q * b;

        arr[1]  = x2 - q * x1;  // x
        arr[2]  = y2 - q * y1;  // y

        a       = b;
        b       = r;

        x2      = x1;
        y2      = y1;

        x1      = arr[1];
        y1      = arr[2];
    }
    arr[0] = a;
    arr[1] = x2;
    arr[2] = y2;

    return arr;
}

OperacionZn.h

/*
*   C++ - Operaciones en Zn
*   Copyright 2014 J. Martin Cruz Otiniano
*   Description :   Contiene los metodos de adición, multiplicicación, inverso multiplicativo, división y exponenciación.
*   Site        :   martincruz.me
*/

#ifndef OPERACIONZN_H
#define OPERACIONZN_H

#include <vector>
#include <iostream>

using namespace std;

class OperacionZn
{
    public:
        OperacionZn();
        ~OperacionZn();

        int adicion(int a, int b, int n);

        int multiplicacion(int a, int b, int n);

        int inv_multiplicativo(int a, int n);

        int division(int a, int b, int n);

        int exponenciacion(int a, int k, int n);

    protected:
    private:
        vector<int> euclides_extendido(int a, int b);
};

#endif // OPERACIONZN_H