If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

El problema del logaritmo discreto

Transcripción del video

we need a numerical procedure which is easy in one direction and hard in the other this brings us to modular arithmetic also known as clock arithmetic for example to find 46 mod 12 we could take a rope of length 46 units and wrap it around a clock of 12 units which is called the modulus and where the rope ends is the solution so we say 46 mod 12 is congruent to 10 easy now to make this work we use a prime modulus such as 17 then we find a primitive root of 17 in this case 3 which has this important property that when raised to different exponents the solution distributes uniformly around the clock 3 is known as the generator if we raise 3 to any exponent X then the solution is equally likely to be any integer between 0 and 17 now the reverse procedure is hard say given 12 find the exponent 3 needs to be raised 2 this is called the discrete logarithm problem and now we have our 1 wave function easy to perform but hard to reverse given 12 we would have to resort to trial and error to find matching exponents how hard is this well with small numbers it's easy but if we use a prime modulus which is hundreds of digits long it becomes impractical to solve even if you had access to all computational power on earth it could take thousands of years to run through all possibilities so the strength of a one-way function is based on the time needed to reverse it