Newbie question: one-way functions in cryptography I'm reading this article on the basics of cryptography and it says that the main principle is about taking such an algorithm that knowing the end result and the algorithm, an eavesdropper wouldn't be able to determine the initial data.

They give an example:



Supposedly, I know the numbers in the second and third row, but don't know the x and can't derive x. But I can: all I need is to do something like this:

for (int i=0; i&lt;100_000_000; i++)  {
      if (i%7==5)  {    
        if (getPower(i, 3)!=-1)  {
            System.out.println(i+", " + getPower(i, 3));
        }
      }

}


It gives me:

243, 5
177147, 11


meaning, that 243 and 177147 are 3^5 and 3^11 respectively and also give the residual 5 when divided by 7. So it doesn't look like a one-way function to me.
So it doesn't look like a one-way function to me.


What you're missing is the scale and basic ideas used in cryptography. Namely the following three facts:


Cryptographic exponents for discrete logarithms have thousands of bits instead of 3 as the example in the question. As such merely trying one value at a time, would take several billion years at least.
In cryptography, you only ever see the result of the exponentiation after the modular reduction (the third row of the graphic), because there are efficient algorithms for finding logarithms over the real numbers.
When using these system in cryptography we don't actually perform $2^{1000}$ or so multiplications but instead use repeated square and multiply which brings this down to a few thousand multiplications. Note that this algorithms requires full knowledge of the exponent to be applied.