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.