lab12(euler)

 #include <iostream> 

#include <cmath> 

using namespace std; 


long long gcd(long long a, long long b) { 

    if (b == 0) 

        return a; 

    return gcd(b, a % b); 

} 


long long eulerTotient(long long n) { 

    long long result = n; 

    for (long long i = 2; i * i <= n; i++) { 

        if (n % i == 0) { 

            while (n % i == 0) 

                n /= i; 

            result -= result / i; 

        } 

    } 

    if (n > 1) 

        result -= result / n; 

    return result; 

} 


long long modExp(long long base, long long exp, long long mod) { 

    long long result = 1; 

    base = base % mod; 

    while (exp > 0) { 

        if (exp % 2 == 1) 

            result = (result * base) % mod; 

        base = (base * base) % mod; 

        exp /= 2; 

    } 

    return result; 

} 


void eulerTheoremDemo() { 

    long long a, n; 

    cout << "Enter a positive integer (n): "; 

    cin >> n; 

    cout << "Enter an integer (a) such that gcd(a, n) = 1: "; 

    cin >> a; 

    if (gcd(a, n) != 1) { 

        cout << "Error: 'a' must be coprime to 'n'." << endl; 

        return; 

    } 

    long long phi_n = eulerTotient(n); 

    cout << "Euler's Totient Function φ(" << n << ") = " << phi_n << endl; 

    long long result = modExp(a, phi_n, n); 

    cout << a << "^" << phi_n << " mod " << n << " = " << result << endl; 

    if (result == 1) { 

        cout << "Euler's Theorem is verified!" << endl; 

    } else { 

        cout << "Euler's Theorem failed. Check input values." << endl; 

    } 

} 


int main() { 

    eulerTheoremDemo(); 

    return 0; 

}


Comments

Post a Comment

Popular posts from this blog

lab7

#include <iostream> #include <string> using namespace std; string xorOperation(const string &text, const string &key) {     string result = text;     for (size_t i = 0; i < text.size(); i++) {         result[i] = text[i] ^ key[i % key.size()];     }     return result; } string encryptDES(const string &plainText, const string &key) {     return xorOperation(plainText, key); } string decryptDES(const string &encryptedText, const string &key) {     return xorOperation(encryptedText, key); } int main() {     string plainText, key;     cout << "Enter a plain text sentence or paragraph: ";     getline(cin, plainText);     cout << "Enter a key (word or sentence): ";     getline(cin, key);     string encryptedText = encryptDES(plainText, key);     cout << "Encrypted Message: ";    ...
Read more

lab6b

#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; vector<int> getPermutationOrder(string key) {     vector<pair<char, int>> keyOrder;     vector<int> order(key.length());     for (int i = 0; i < key.length(); i++) {         keyOrder.push_back(make_pair(key[i], i));     }     sort(keyOrder.begin(), keyOrder.end());     for (int i = 0; i < keyOrder.size(); i++) {         order[keyOrder[i].second] = i;     }     return order; } string preprocessText(string text) {     for (char &ch : text) {         if (ch == ' ') {             ch = '~';         }     }     return text; } string restoreSpaces(string text) {     for (char &ch : text) {       ...
Read more