3. Discussion
If this ngazi method is coded into a computer software then we will create computers that can calculate exponential functions much faster than they currently do. This method is very important because exponential function calculations are done everyday in fields such as engineering, mathematics and computer science. In fact since this method will vastly improve computer efficiency in calculating exponential functions then this method will contribute greatly towards finding the solution to the discrete logarithm problem through the use of discrete exponentiation. Let me explain what the discrete logarithm problem is. Unsolved problems website explains this problem very well.
“Suppose that we have an equation
y=gx mod p.
Where all four variables are integers, and g and p are very large prime numbers, say, greater than 100 digits. Given g, p and x, it takes a modern-day computer only a fraction of a second to calculate y. The Discrete Logarithmic Problem (DLP), is given g, p and y, can we find x, even if we have a million computers and a million years at our disposal?[6] The discrete logarithm is the inverse of the discrete exponentiation in a finite cyclic group.[7] This concept is important in
internet security. A recent finding is that Diffie-Hellman security is not as watertight as was initially believed.[8] Even though digital computers are efficient in computing, they still have challenges in solving two problems, factoring integers and finding discrete logarithms.[9] In common culture, In the famous maths drama television programme called Numbers, discrete logarithm were mentioned in the season 2 episode “In plain sight”.[10]
This author’s reply to the discrete logarithm problem is that it is possible to find x in finite time using ngazi method and rearranging the equation as will be shown later. This author believes that we can solve this problem even if we are given only g,p and y. This is so because this new method reduces tremendously the number of multiplication operations that are needed to solve this problem. The following procedure should be followed in order to make finding solutions to discrete exponentiation and by extension discrete logarithm problems easier.
Since we don’t have x in gx, we have no choice but to use the trial and error method. Some trial and error methods are more efficient than others in predicting what the value of x would be. However, whatever method is used, one must be prepared to carry out several rounds of calculations until one obtains the value of x. In the simplest example, suppose we assume that x is 1 then
y=g1 mod p. We then calculate g1÷p. We then check whether the remainder of this operation is equal to y. If it is, then we have found the solution to x. If it is not, then we must proceed with our calculations. We can set x to be 2. y=g2 mod p. We can then calculate g2÷p and then we can check whether the remainder of this operation is y. If it is not then we can set x to be 3 and then proceed to calculate g3 mod p. Of course we can go on and on setting x to any value and each time using the ngazi method to calculate gx. We can repeat this operation until we find x. Of course since the ngazi method is vastly more efficient in calculating exponential functions, then it will take a finite amount of time to find x in the equation y=gx mod p as long as x is not an infinite value. Of course there are more efficient methods of guessing x instead of just following the number line 1,2,3,4,5, we can use more efficient methods of guessing x and this will save time. It will definitely take a finite period of time to get the answer to that equation.
One last thing that has to be said about the discrete logarithm problem is that it is a problem now better solved via the route of discrete exponentiation. The method of discrete exponentiation that I have explained above can be improved and made more efficient. The problem with the method above is that we require the computer to calculate gx mod p and then find out whether the remainder of this operation has the same value as y. However, this method can be extremely inefficient and time-consuming if the remainder itself is a big number. This big number will take up a lot of precious computer memory and will also consume a lot of computing power and time during its calculation. This author has found a novel and more efficient method of calculating the discrete exponential function in such a way that the remainder does not need to be calculated in full.
Given y=gx mod p and we know the values for g,p and y, is it possible to find x in finite time?
To avoid calculating and manipulating the remainder, we shall have to rearrange the equation above.
The equation gx mod p has a remainder value of y (where y>0). Therefore this means that
gx is not divisible by p since gx÷p produces a remainder y. gx can be understood to be the sum of a number t which is divisible by p and a remainder y which is not divisible by p. Therefore we can subtract the remainder y from gx to obtain the number which is divisible by p.
y=gx mod p
gx-y=t
Now, the value gx-y is divisible by p because it does not have the remainder y. Since gx-y is divisible by p, the next step would be divide gx-y by p.
(gx-y)÷p
So we can confidently say that the value (gx-y)÷p is definitely an integer and that means it does not have a remainder or decimal points. The problem that remains however, is that we do not know what the value of x is. This will force us to do trial and error to get x. Therefore we can feed in arbitrary values for x, we can either follow a systematic approach, for example, 1,2,3,4,5 for values of x or any other suitable approach can be used. This author prefers the systematic approach where the values of x are input starting from 1,2,3,4,5 up to x without skipping any number until x is found. So how will we know when we have found x?
Let us suppose we set x to be 1 as shown (g1-y)÷p. If the result of this calculation has a remainder or a decimal then 1 is not the value for x and we must set x to be 2.
If the computer calculates the equation (g2-y)÷p and then gives an output with decimals then it is clear that this equation has a remainder and therefore we must set x to be 3 and this process goes on and on as long as this equation produces decimal points. It is prudent to program the computer to stop the calculation at the 1st decimal point to save computer power and time. We no longer need to calculate the whole remainder because we no longer need to compare the remainder with y. This act of comparing, after every calculation, whether the remainder is equal to y would have consumed immense computer power and time but because we no longer need to compare the remainder with y then computer resources are conserved. So how will we know when we have found x? It is very simple. We will know that we have found x when the calculation (gx-y)÷p does not give us any decimals. Therefore when we feed in a certain value of x and fail to get a remainder then that value of x is the one we were looking for. Therefore the computer can be programmed to stop the calculation only when a given value of x in the equation (g1-y)÷p=h produces an integer value for h. In conclusion, if h is an integer value then we have found x, however if it a decimal or a fraction then we haven’t found x. Just to summarize, this new approach is more efficient than the previous one because
1. The entire remainder does not need to be calculated. In fact when the first decimal has been calculated then the operation is stopped and the computer moves on to the next value of x. For computers that produce results of division operations in fraction form, the computer can be programmed to terminate calculation after the first digit of the remainder has been calculated. The computer does not need to calculate all the digits of the remainder. Therefore there will be no computer power and time spent calculating this large remainder.
2. The second advantage is that because the entire remainder is not calculated, this means that it does not need to be stored or retrieved at a later date for comparison with y. Because the remainder will not be stored then there will be no memory used for this process.
3. The third advantage is that after every round of calculation, the remainder was supposed to be compared with y to find out whether they have the same value, this would have been an inefficient process. However, we no longer need to compare the remainder with y and therefore we save on computer power and time that would have been used to compare these two large numbers.
This new method can also be used in the creation of new and more efficient computer math libraries that calculate exponential functions. It is important that computer libraries that deal with mathematical calculations should be as fast as possible.
Indeed, this new method can be used in any area that uses exponential functions in their calculations.