Encrypt the code using two key values | Algorithm to help Bob to encrypt the secret code

In today’s world, data security and encryption are critical. Bob needs to send a secret code (S) to his boss securely. To achieve this, he encrypts the code using two key values (N and M) through a mathematical formula:Encrypted Code=(((SNmod  10)M)mod  1000000007)\text{Encrypted Code} = (((S^N \mod 10)^M) \mod 1000000007)Encrypted Code=(((SNmod10)M)mod1000000007)

This encryption ensures that even if someone intercepts the message, decoding it without the key values is nearly impossible.

What You’ll Learn

• Understanding the encryption logic
• Handling large numbers efficiently
• Optimized implementations in C++, Java, and Python
• Suggested visuals for better understanding

Understanding the Encryption Logic

Breaking Down the Formula

The encryption formula can be broken down into three steps:

1. Compute (S^N mod 10):
   • Since S is large (up to 10910^9109) and N is even larger (up to 101010^{10}1010), we only need the last digit of S^N.
   • The last digit of a number follows a cycle when raised to powers (ex: 2 → 4 → 8 → 6 → repeat).
   • We determine this cycle and find the effective exponent modulo 4.
2. Compute ((Result)^M mod 1000000007):
   • Again, M is very large (up to 101010^{10}1010), so direct computation is not possible.
   • We use modular exponentiation to efficiently compute the power under modulo 1000000007.

Algorithm to Encrypt the Code

Step 1: Extract the Last Digit of S

• Compute last_digit = S % 10
• Identify the cycle of last digits for last_digit when raised to different powers.

Step 2: Reduce the Exponent N

• Since last digits cycle every 4 numbers, compute effective_exponent = (N % cycle_length).

Step 3: Compute First Power using Modular Exponentiation

• Calculate X = (last_digit ^ effective_exponent) % 10.

Step 4: Compute Final Power using Modular Exponentiation

• Compute encrypted_code = (X ^ M) % 1000000007.

Optimized Code Implementations

Python Implementation

def mod_exponentiation(base, exp, mod):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

def encrypt_code(S, N, M):
    last_digit = S % 10
    
    # Identify last digit cycle
    cycles = {0: [0], 1: [1], 2: [2, 4, 8, 6], 3: [3, 9, 7, 1], 4: [4, 6],
              5: [5], 6: [6], 7: [7, 9, 3, 1], 8: [8, 4, 2, 6], 9: [9, 1]}
    
    cycle_list = cycles[last_digit]
    cycle_length = len(cycle_list)
    
    effective_exponent = mod_exponentiation(N, 1, cycle_length) - 1
    X = cycle_list[effective_exponent]
    
    # Compute final encrypted code
    encrypted_code = mod_exponentiation(X, M, 1000000007)
    
    return encrypted_code

# Example usage
S, N, M = map(int, input("Enter S, N, M: ").split())
print("Encrypted Code:", encrypt_code(S, N, M))

Why this works efficiently:

• Handles large exponents efficiently using modular exponentiation.
• Optimized cycle detection for last-digit calculations.
• Reduces computation complexity from exponential to logarithmic.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007

// Function to perform modular exponentiation
long long mod_exponentiation(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// Encryption function
long long encrypt_code(long long S, long long N, long long M) {
    int last_digit = S % 10;
    vector<vector<int>> cycles = {
        {0}, {1}, {2, 4, 8, 6}, {3, 9, 7, 1}, {4, 6},
        {5}, {6}, {7, 9, 3, 1}, {8, 4, 2, 6}, {9, 1}
    };

    vector<int> cycle_list = cycles[last_digit];
    int cycle_length = cycle_list.size();

    long long effective_exponent = mod_exponentiation(N, 1, cycle_length) - 1;
    long long X = cycle_list[effective_exponent];

    return mod_exponentiation(X, M, MOD);
}

int main() {
    long long S, N, M;
    cout << "Enter S, N, M: ";
    cin >> S >> N >> M;
    cout << "Encrypted Code: " << encrypt_code(S, N, M) << endl;
    return 0;
}

Java Implementation

import java.math.BigInteger;
import java.util.Scanner;

public class SecretCodeEncryption {

    static final BigInteger MOD = BigInteger.valueOf(1000000007);

    // Function to perform modular exponentiation
    public static BigInteger modExponentiation(BigInteger base, BigInteger exp, BigInteger mod) {
        BigInteger result = BigInteger.ONE;
        while (exp.compareTo(BigInteger.ZERO) > 0) {
            if (exp.mod(BigInteger.TWO).equals(BigInteger.ONE)) {
                result = result.multiply(base).mod(mod);
            }
            base = base.multiply(base).mod(mod);
            exp = exp.divide(BigInteger.TWO);
        }
        return result;
    }

    public static BigInteger encryptCode(BigInteger S, BigInteger N, BigInteger M) {
        int lastDigit = S.mod(BigInteger.TEN).intValue();
        int[][] cycles = {
            {0}, {1}, {2, 4, 8, 6}, {3, 9, 7, 1}, {4, 6},
            {5}, {6}, {7, 9, 3, 1}, {8, 4, 2, 6}, {9, 1}
        };

        int[] cycleList = cycles[lastDigit];
        int cycleLength = cycleList.length;

        int effectiveExponent = modExponentiation(N, BigInteger.ONE, BigInteger.valueOf(cycleLength)).intValue() - 1;
        int X = cycleList[effectiveExponent];

        return modExponentiation(BigInteger.valueOf(X), M, MOD);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter S, N, M: ");
        BigInteger S = sc.nextBigInteger();
        BigInteger N = sc.nextBigInteger();
        BigInteger M = sc.nextBigInteger();
        sc.close();

        System.out.println("Encrypted Code: " + encryptCode(S, N, M));
    }
}

Conclusion

This guide provided an optimized and scalable approach to encrypt Bob’s secret code using modular exponentiation. The techniques used ensure fast computation even for extremely large numbers.