In this article, we explore the relationship between modular exponentiation and the equation.

$$g^r = nM+1$$

This all started after I watched a video on Quantum computational code breaking and one part i found interesting is the Exponential sequence, if instead of computing the entire stack, one could compute the first couple and then pick random parts of the sequence and see if there is a partial match.

Really, so if g to the power of r runs in a sequence, we can find a match on this sequence for a longer array, if we only calculate a fraction of it at a time, dismissing the entire computation cost..

Method

First, we define some variables:

  • t = 77: The modulus for the modular exponentiation calculations.
  • g = 8: A randomly picked base number for the modular exponentiation.
  • l = 1000: The number of bits of the prime number.
  • sl = 4: The number of bits of the secret number.
  • jf = sl - 1: The number of bits of the secret number minus margin.

We start by calculating:

$$g^i \mod t$ for $i = 0, 1, 2, \dots, sl-1$$
$$\text{xf} = \{g^0 \mod t, g^1 \mod t, g^2 \mod t, \dots, g^{sl-1} \mod t\}$$

Next, we generate a shuffled array of indexes, Indexes, to iterate through.

We then define two more variables:

  • r = 2: The number of attempts before determining the secret number sequence iterational length.
  • ns = 0: The number of secret number sequence iterational lengths.

We will search for secret number sequences iterational lengths by iterating through the Indexes array and calculating

$$g^i \mod t$$

for a given index and its subsequent sl indices:

$$\text{y} = \{g^{\text{index}} \mod t, g^{\text{index} + 1} \mod t, g^{\text{index} + 2} \mod t, \dots, g^{\text{index} + sl-1} \mod t\}$$

If the calculated sequence y matches the initial sequence xf, we add the index to the array n2.

After finding r successful matches, we calculate the greatest common divisor (GCD) of the indices in the n2 array. Finally, we compute the value of g raised to the power of the calculated GCD:

$$f = g^{\text{GCD(n2)}}$$

Results and Discussion

The provided code calculates the modular exponentiation of a base, g, raised to various powers, then takes the result modulo t. It iteratively searches for a secret number sequence iterational length by comparing sub-sequences of the computed modular exponentiation.

The code also calculates the GCD of the indices where the sub-sequences match the initial sequence xf. The final result is the base g raised to the power of the calculated GCD. This approach demonstrates a relationship between modular exponentiation and the equation

$$g^r = nM+1$$
using System.Numerics;

int t = 77;                                       
BigInteger g = 8;                                  
int l = 1000;                                    
int sl = 4;                                        
int jf = sl - 1;                                 

BigInteger[] xf = CalculatePowerMod(g, 0, sl, t);  

Random rand = new Random();

int iDx = 0;
int[] Indexes = GenerateShuffledIndexes(l);
int r = 2;                                          
int ns = 0;                                      
int[] n2 = new int[r];                              

//int itr = 0;
while (ns < r)
{
    int index = Indexes[iDx++];                     

    int i = 0;
    int j = 0;

    BigInteger[] y = CalculatePowerMod(g, index, sl, t);   

    while (i < sl && j < sl && y[i] == xf[j])               
    {
        i++;
        j++;
    }

    if (j >= jf)                                   
    {
        n2[ns] = Indexes[iDx-1];                  
        ns++;                                       
    }
}

BigInteger f = BigInteger.Pow(g, CalculateGCD(n2));

Console.WriteLine(f);


static int[] GenerateShuffledIndexes(int n)
{
    Random rand = new Random();
    int[] indexes = new int[n];
    for (int i = 0; i < n; i++)
    {
        indexes[i] = i;
    }

    for (int i = n - 1; i > 0; i--)
    {
        int j = rand.Next(0, i + 1);
        int temp = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = temp;
    }

    return indexes;
}

static int CalculateGCD(int[] numbers)
{
    int n = numbers.Length;
    int gcd = numbers[0];

    for (int i = 1; i < n; i++)
    {
        int a = gcd;
        int b = numbers[i];
        while (b != 0)
        {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        gcd = a;
    }

    return gcd;
}

static BigInteger[] CalculatePowerMod(BigInteger g, int index, int count, int m)
{
    BigInteger[] result = new BigInteger[count];
    int c = index + count;
    for (int i = index, j = 0; i < c; i++, j++)
    {
        result[j] = BigInteger.ModPow(g, i, m);
    }
    return result;
}

Note that the code above does not take in to account the best approach to pattern matching since if the index is off by 1, and the entire match will fail. so a partial match should also be added.

Conclusion

This was fun, but eventually it proves that there is no shortcut to quantum computation as this would hit the CPU ever so hard, on large numbers.
So in conclusion I’d recommend not to venture on such stupid goose chases. hah

Math, Programming, Technology

Tagged in:

, , , , ,