#include <bits/stdc++.h>
using namespace std;
 
#define lli long long int  
 
lli N, G; //Chaves pública P e G
lli a, b; //Números secretos de Alice e Bob respectivamente para criar a chave.
lli A, B; //Números enviados um para o outro
lli Sa, Sb; //Chave secreta usando os números compartilhados
 
//Retorna a ^ b mod P
lli modularPower(lli base, lli exponent, lli mod) {
    base %= mod;
    lli ans = 1;
    while(exponent > 0) {
        if (exponent & 1) {
            ans = ans * base % mod;
        }
        base = base * base % mod;
        exponent >>= 1;
    }
    return ans;
}
 
int main() {
    N = 23; //Primo
    G = 9; //Raiz primitiva de mod P
 
    cout << "Número primo público: " << N << "n";
    cout << "Raiz primitiva pública: " << G << "n";
 
    a = 4;
    cout << "Número secreto escolhido por Alice: " << a << "n";
    A = modularPower(G, a, N); //Gera a chave que será compartilhada
 
    b = 3;
    cout << "Número secreto escolhido por Bob: " << b << "n";
    B = modularPower(G, b, N);
 
    cout << "Chave que Alice manda para Bob: " << A << "n";
    cout << "Chave que Bob manda para Alice: " << B << "n";
 
    Sa = modularPower(B, a, N);
    Sb = modularPower(A, b, N);
 
    cout << "Chave secreta de Alice: " << Sa << "n";
    cout << "Chave secreta de Bob: " << Sb << "n";
 
    return 0;
}