Bzzzzzzzzzz

// Practice1_spring_pro.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <time.h>
#include "\Program Files (x86)\Math (под VisualC++)\MMATH.H"
#include "\Program Files (x86)\Math (под VisualC++)\!-Src\Src_DivTest\DivTest.h"

void PrintBin(M_LONG N, bool EOL);
void PrintHex(M_LONG N, bool EOL = true) {
    int word = N[0];
    printf("%X ", N[word--]);
    for (; word > 0; --word)
        printf("%08X ", N[word]);
    if (EOL)
        printf("\n");
}
/*
16 - hex
10 - dec
2  - bin

1 - false
0 -true
*/

int PrintLONG(M_LONG N, DIGIT Base, bool EOL = true) {
    if (Base != 16 && Base != 10 && Base != 2)
        return 1;

    int word = N[0];
    switch (Base)
    {

    case 16:
        printf("Hexidecimal: %X ", N[word--]);
        for (; word > 0; --word)
            printf(" %08X ", N[word]);
        if (EOL)
            printf("\n");
        break;

    case 10:
        printf("Decimal: %u ", N[word--]);
        for (; word > 0; --word)
            printf(" %010u ", N[word]);
        if (EOL)
            printf("\n");
        break;

    case 2:
        PrintBin(N, EOL);
        break;
    }
    return 0;
}

// для нормализованого числа. Длина корректная. Пример №7 в пз
DIGIT BitLen(M_LONG N) {
    DIGIT word, MSW;
    int bit;
    // нормализация числа. У MSW стоят 0.
    word = N[0];
    while (N[word] == 0 && word > 1)
    {
        --word;
        N[0] = word; // Длина корректная
    }
    MSW = N[word];
    for (bit = 31; (MSW & (1 << bit)) == 0 && bit >= 0; --bit);
    bit = (word - 1) * 32 + bit + 1;
    return bit;
}

void PrintBin(M_LONG N, bool EOL = true)
{
    DIGIT word = N[0];
    DIGIT MSW;
    int bit;
    // визначення позиции старшого значушого бита в старшому значушому слову (число нормализоане)

          // нормализация числа. У MSW стоят 0.
    word = N[0];
    while (N[word] == 0 && word > 1)
    {
        --word;
        N[0] = word; // Длина корректная
    }
    MSW = N[word];
    for (bit = 31; (MSW & (1 << bit)) == 0 && bit >= 0; --bit);

    for (; bit >= 0; --bit)
    {
        printf("%u", (N[word] >> bit) & 1);

    }
    printf(" ");
    --word;

    for (; word > 0; --word)
    {
        for (bit = 31; bit >= 0; --bit)
        {
            //printf("&u", (N[word] & (1 << bit)) >> bit); //Second option
            printf("%u", (N[word] >> bit) & 1);
            /* N[word] & (1 << bit);// First option
             if (N[word] & (1 << bit)!=0)
             {
                 return 1;
             }*/
        }
        printf(" ");
    }
    if (EOL)
        printf("\n");
}


void GenRandBinVect(M_LONG P, DIGIT BitLen) {
    int Len32;
    srand(time(NULL));
    Len32 = (BitLen + 31) / 32;
    //Len32 = BitLen / 32 + (BitLen%32)?1:0;
    m_rand(P, Len32);

    P[Len32] &= (1 << (BitLen % 32)) - 1;
    P[Len32] |= (1 << ((BitLen % 32) - 1));

}

int LemanTest(M_LONG P, int k) {//100-150
    M_LONG P_1, P_1_2, a,res;// P-1, (P-1)/2
    int i,counter=0;
    m_copy(P_1, P);
    P_1[1]--; //P-1 7   0111 -- 0110
    m_copy(P_1_2, P);
    m_shr(P_1_2, 1);
    for ( i = 0; i < k; ++i)
    {
        m_rand(a, P[0]);
        m_blockpowmod(a, P_1_2, P, res);
        if (res[0] == 1 && res[1] == 1)//{1,1}
            continue;
        if (m_cmp(res, P_1) == 0) {
            ++counter;
            continue;
        }
        return 1;
    }
    if (counter)
        return 0; //pseudo prime
    return 1; //composite
}

int RabinTest(M_LONG P, int k){
    M_LONG P1, a, res;
    int counter=0;
    M_LONG s;
    DIGIT r = 0;
    m_copy(P1, P);
    P1[1] &= 0XFFFFfffE; //P-1 7   0111 -- 01100000/ Для парных не будет зануляться
    while (!(P1[1] & 1)) {
        //P1[1]=P1[1] >> 1;
        m_shr(P1, 1);
        r++;
    }
    m_copy(s,P1);
    printf("2 ^ %u * %d + 1", r,s);

    for (int i = 0; i < k; ++i)
    {
        m_rand(a, P1[0]);
        m_blockpowmod(a,s, P, res);
        if (res[0] == 1 && res[1] == 1)//{1,1}
            ++counter;
        //else if (m_cmp(res, P1) == 0)
        //{
        //    ++counter;
        //    continue;
        //}
        //return 1;
        else
        {
            for ( int j = 0; j < r-1; ++j)
            {
                if (m_cmp(res, P1) == 0) {
                    ++counter;
                    continue;
                }

            }
            return 1;
        }

    }
    if (counter)
        return 0; //pseudo prime
    return 1; //composite
}

void  GenPrimeRabin(M_LONG P, DIGIT BitLength, int k) {
    M_LONG two = { 1,2 };

    GenRandBinVect(P, BitLength);
    P[1] |= 1;
    while ( RabinTest(P, k) || DivTest(P))
    {
        m_add(P, two, P);
        if (BitLen(P) > BitLength)
        {
            GenRandBinVect(P, BitLength);
            P[1] |= 1; //  odd
        }
    }
}

void  GenPrimeLeman(M_LONG P, DIGIT BitLength, int k) {
    M_LONG two = { 1,2 };

    GenRandBinVect(P, BitLength);
    P[1] |= 1;
    while ( DivTest(P)||LemanTest(P, k))
   {
        m_add(P, two, P);
        if (BitLen(P) > BitLength)
        {
            GenRandBinVect(P, BitLength);
            P[1] |= 1; //  odd
        }
   }

}

int main()
{


    M_LONG   P = { 16,  0x6f18544d,0xedb374f5,0xffbc3bcc,0x7249bb52,
            0xb09152ec,0x9551dc2c,0x7f6e2853,0xa4dba914,
            0xa9bd6e9b,0x70cd54ce,0x31fe7bd3,0xcc61f6d2,
            0x5d45c7fc,0x11a20acc,0x39b8708c,0x9df3ef1d },
        Q = { 16,  0xab74d85d,0x8e352852,0xf440ab72,0x790f53f3,
            0xb51fbad0,0x10555a11,0xd79b004c,0x90ca7e6c,
            0x8bcca0b1,0xba0262f8,0xc2e3603d,0x52e68e5e,
            0xb4a22921,0xa234ee79,0x5ae28905,0xf5fe50db };

    M_LONG N, FN, E, D, P_1, Q_1, two = { 1,2 }, M = { 1,3 }, C, M1;
    char* str = (char*)&M[1];
    //gets_s(str, 100);
    // L = ByteLen / 4; k = (ByteLen % 4) * 8
    //blabla = (1 << (strlen(str) % 4)) - 1
    //M[1] &= blabla;

    srand(time(NULL)); // not necessary

   // option 1 LEMAN TEST
    //if (RabinTest(P, 10))
    //{
    //    printf("Error");
    //    return 1;
    //}else
    //{
    //    printf("OK");
    //    return 0;
    //}

     GenPrimeLeman(P, 512, 10); // Bitlen(N) = BitLen(P)+Bitlen(Q)
     do {
         GenPrimeLeman(Q, 512, 10);
     } while (m_cmp(P, Q) == 0);


     //Rabin test
     GenPrimeRabin(P, 512, 10); // Bitlen(N) = BitLen(P)+Bitlen(Q)
     do {
         GenPrimeRabin(Q, 512, 10);
     } while (m_cmp(P, Q) == 0);

    m_mul(P, Q, N);

    printf("P = "); PrintLONG(P, 16);
    printf("Q = "); PrintLONG(Q, 16);
    printf("N = "); PrintLONG(N, 16);

    m_copy(P_1, P); m_copy(Q_1, Q);
    P_1[1]--; Q_1[1] &= 0XFFFFfffE;

    m_mul(P_1, Q_1, FN);

    printf("P = "); PrintLONG(P, 16);
    printf("Q = "); PrintLONG(Q, 16);
    printf("N = "); PrintLONG(N, 16);

    // Variant 1
    do {
        m_rand(E, FN[0] - 1);
        // in loop using m_cmp() make sure size of FN < size of E
        E[1] |= 1;
    } while (m_inv(E, FN, D) || m_cmp(E, D) == 0);

    // Variant 2
    //m_rand(E, FN[0] - 1);
    //// in loop using m_cmp() make sure size of FN < size of E
    //E[1] |= 1;
    //while (m_inv(E, FN, D)  m_cmp(E, D) == 0) {
    //    m_add(E, two, E);
    //}

    // Variant 3
    srand(time(NULL));
    //do {
    //    m_rand(E, FN[0]);
    //} while (m_cmp(E, FN) >= 0);
    //in loop using m_cmp() make sure size of FN < size of E
    //E[1] |= 1;

    printf("\nE = "); PrintLONG(E, 16);
    printf("D = "); PrintLONG(D, 16);

    while (m_inv(E, FN, D) || m_cmp(E, D) == 0) {
        m_add(E, two, E);
        // m_cmp(E,FN)>=0 ???
    }
    m_blockmontpowmod(M, E, N, C);
    m_blockmontpowmod(C, D, N, M1);
    if (m_cmp(M, M1) == 0) {
        printf("\nM1 = M = %u", M1[1]);
        printf("\nM = "); PrintLONG(M, 16);
        printf("C = "); PrintLONG(C, 16);
        printf("M1 = "); PrintLONG(M1, 16);
    }
    else {
        printf("Error");
    }



}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы с

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.