Funciones unidireccionales

Como ejemplos de funciones unidireccionales están los siguientes:

• Productos y factorizaciones. Dados dos números primos p, q, el cálculo de su poducto n = p q es una operación muy sencilla de ser realizada. Recíprocamente, si se sabe que el entero n es el producto de dos primos p, q, calcular a estos últimos partiendo sólo de n es una tarea harto costosa. En efecto, supongamos que cada uno de los factores p, q se escribe con k dígitos (si los consideramos binarios hagamos b = 2 y si fuesen decimales hagamos b = 10), en otras palabras, que p, q son de tamaño k. Entonces n se escribe con 2k dígitos. El cálculo de n, dados p, q, se realiza con el más convencional de los procedimientos con k k operaciones dígito a dígito o bien con k log(k) de tales operaciones si se hace de una manera más inteligente (usando la llamada Transformada Rápida de Fourier). El producto es pues de costo menor que cuadrático en el tamaño de los factores. En cambio, dado n de tamaño 2k prácticamente la única manera de encontrar a los factores p, q es localizando a uno primero revisando si acaso n es divisible por cada uno de los primos menores que su raíz cuadrada. Por el Teorema de los Números Primos se tiene que hay del orden de n/log(n) de tales primos, es decir hay del orden de b a la potencia k, dividido entre k, candidatos. Factorizar es pues de costo exponencial con el tamaño, lo que es irrealizable para valores considerables de k. El producto de dos primos es una función unidireccional.
• Exponenciaciones y logaritmos. Sea x un número real positivo. La órbita de x en el conjunto de reales positivos consta de todas las potencias de x con exponente entero. Para determinar si acaso un real positivo y está o no en la órbita de x basta con calcular el logaritmo de y en base x: se tendrá que éste es entero si y sólo si y está en la órbita de x. El cálculo de logaritmos en los reales, siendo ésta una función analítica, es un problema muy sencillo, trivial en la práctica. Sin embargo, el problema cambia radicalmente cuando en vez de los reales consideramos grupos finitos. Si G es un tal grupo, su orden es su cardinalidad. Dado un elemento x en él, el orden de x es el número de elementos de su órbita. El Teorema de Lagrange establece que el orden de cualquier elemento es un divisor del orden del grupo. Hay grupos finitos en los que el problema de decidir cuándo un elemento y está en la órbita de un elemento x sólo puede hacerse de manera exhaustiva: una a una se van calculando las potencias de x y se detiene la primera vez que se obtiene y o la unidad del grupo. El cálculo de los llamados logaritmos discretos sólo puede hacerse de manera exhaustiva, lo que es irrealizable si el orden del generador x es grande. En cambio, el cálculo de las potencias se hace de manera muy eficiente. En grupos finitos, la exponenciación a potencias enteras es pues una función unidireccional.
• Elevación al cuadrado y raíz cuadrada. Aunque ambas operaciones son inmediatas en el grupo multiplicativo de los números reales positivos, la extracción de raíces en el grupo multiplicativo de residuos módulo un entero producto de dos primos es equivalente al problema de factorización de ese entero. Así, en tales grupos multiplicativos, la elevación al cuadrado es una función unidireccional.
• Reiteración de funciones. Supongamos dada una familia de funciones, cada una de las cuales se calcula eficientemente. Para un argumento dado y un criterio de selección de funciones, se reitera la aplicación sucesiva de funciones de acuerdo con el criterio de selección dado, partiendo del punto dado (la manera en la que actúan los autómatas celulares se adecúa a este esquema). La reiteración es una función unidireccional.