1 Números Seudoaleatorios

1.1 Introducción

Hemos visto que varios de los algoritmos importantes usan números aleatorios (o, equivalentemente, bits aleatorios independientes). Pero ¿Cómo hacemos nosotros para obtener tales bits? Una fuente posible para obtener estos bits es puede ser no ocupar una computadora. Podríamos obtener secuencias ’realmenteáleatorias, es decir, de descomposición radiactiva. En la mayoría de los casos, sin embargo, esto no trabajaría: Nuestras computadoras son muy rápidas y no tenemos dispositivo físico que nos de el equivalente a lanzar una moneda. Así debemos recurrir para generar nuestros bits aleatorios a la computadora. Sin embargo, una secuencia larga generada por un programa pequeño nunca es aleatorio, según la noción de aleatoriedad introducido por complejidad de la información. Así nos vemos forzados a usar los algoritmos que genera secuencias que parecen aleatorias; pero, como Von Neumann (uno de los primeros matemáticos en proponer el uso de estos) propuso, todo el mundo los usa es inevitablemente debido á nuestro estado primitivo’. En este capítulo, entenderemos el tipo de protección que podemos poner en contra de las consecuencias al ocupar esto. Hay otras razones además de las prácticas para estudiar generadores de número pseudoaleatorios. A menudo queremos repetir alguna computación por varias razones, incluyendo detección de errores. En este caso, si nuestra fuente de números aleatorios fuera realmente aleatoria, entonces la única forma para usar los mismos números aleatorios otra vez, es almacenarlos, usando un montón de espacio. Con números pseudoaleatorios, esto no es el caso: sólo debemos almacenar la ’semilla’, la cual es mucho más corta. Otra, y más importante, razón es que hay aplicaciones donde lo que queremos es únicamente que la secuencia ’se vea aleatoria’para alguien que no sabe cómo que fue generada. La colección de estas aplicaciones es llamada criptografía, pero será tratada en un capítulo posterior. La forma en que trabaja el generador de bit seudoaleatorio es cambiar una cadena corta aleatoria llamada la ’semillaén una cadena pseudoaleatoria más larga. Requerimos que trabaje en tiempo polinomial. La cadena resultante tiene que ’verseáleatoria: y el hecho importante es que ésta puede estar definida exactamente. Hablando en términos generales, no debería haber algoritmo de tiempo polinomial que lo distinga de una secuencia verdaderamente aleatoria. Otro rasgo, a menudo más fácil para asegurarse, es que ningún algoritmo puede predecir cualesquiera de sus bits previos. Probaremos la equivalencia de estas dos condiciones.

8.2 Introducción

Hemos visto que varios de los algoritmos importantes usan números aleatorios (o, equivalentemente, bits aleatorios independientes). Pero ¿Cómo hacemos nosotros para obtener tales bits? Una fuente posible para obtener estos bits es puede ser no ocupar una computadora. Podríamos obtener secuencias ’realmenteáleatorias, es decir, de descomposición radiactiva. En la mayoría de los casos, sin embargo, esto no trabajaría: Nuestras computadoras son muy rápidas y no tenemos dispositivo físico que nos de el equivalente a lanzar una moneda. Así debemos recurrir para generar nuestros bits aleatorios a la computadora. Sin embargo, una secuencia larga generada por un programa pequeño nunca es aleatorio, según la noción de aleatoriedad introducido por complejidad de la información. Así nos vemos forzados a usar los algoritmos que genera secuencias que parecen aleatorias; pero, como Von Neumann (uno de los primeros matemáticos en proponer el uso de estos) propuso, todo el mundo los usa es inevitablemente debido á nuestro estado primitivo’. En este capítulo, entenderemos el tipo de protección que podemos poner en contra de las consecuencias al ocupar esto. Hay otras razones además de las prácticas para estudiar generadores de número pseudoaleatorios. A menudo queremos repetir alguna computación por varias razones, incluyendo detección de errores. En este caso, si nuestra fuente de números aleatorios fuera realmente aleatoria, entonces la única forma para usar los mismos números aleatorios otra vez, es almacenarlos, usando un montón de espacio. Con números pseudoaleatorios, esto no es el caso: sólo debemos almacenar la ’semilla’, la cual es mucho más corta. Otra, y más importante, razón es que hay aplicaciones donde lo que queremos es únicamente que la secuencia ’se vea aleatoria’para alguien que no sabe cómo que fue generada. La colección de estas aplicaciones es llamada criptografía, pero será tratada en un capítulo posterior. La forma en que trabaja el generador de bit seudoaleatorio es cambiar una cadena corta aleatoria llamada la ’semillaén una cadena pseudoaleatoria más larga. Requerimos que trabaje en tiempo polinomial. La cadena resultante tiene que ’verseáleatoria: y el hecho importante es que ésta puede estar definida exactamente. Hablando en términos generales, no debería haber algoritmo de tiempo polinomial que lo distinga de una secuencia verdaderamente aleatoria. Otro rasgo, a menudo más fácil para asegurarse, es que ningún algoritmo puede predecir cualesquiera de sus bits previos. Probaremos la equivalencia de estas dos condiciones. Pero ¿cómo diseñamos tal generador? Existen varios métodos adhoc que producen secuencias que parecen aleatorias (nos gusta hablar de bits por la representación binaria de una raíz de una ecuación dada) el resultado produce cadenas que estrictamente hablando no soy muy aleatorias. Un método general para obtener tales secuencias se basa en funciones de un solo sentido: funciones que son fáciles para evaluar pero difíciles de invertir. Mientras la existencia de esto funciona, no ha sido probado (significaría que P es diferente de NP), hay varios candidatos, esto es seguro al menos con las técnicas actuales.

8.3 Métodos Clásicos

Hay varios métodos clásicos que generan una secuencia de bits que ’parecen aleatorias’. Ninguno de estos métodos reúnen las normas estrictas, los que serán explicados en la siguiente sección; pero debido a su simplicidad y eficiencia, ellos (especialmente los generadores de congruencia lineal, el ejemplo 2 mas abajo) pueden ser usado bien en la práctica. Hay una gran cantidad de información práctica acerca de la mejor elección de los parámetros; Nosotros no nos referiremos de esto aquí, pero pueden referirse al Volumen 2 del libro de Knuth.

(8.1) Ejemplo Los registros de desplazamiento están definidos como sigue. Sea f : {0,1}^{n} → {0,1} una función que es fácil para computar. Empezando con una semilla de n bits a_{0},a_{1},...,a_{n−1}, nosotros computaremos bits a_{n},a_{n+1},a_{n+2}... recursivamente, por

a_{k} = f (a_{k−1},a_{k−2},...,a_{k−n}).

El nombre de ’registro de desplazamiento’viene del hecho que sólo necesitamos almacenar n+1 bits: después de almacenar f (a_{0},...,a_{n−1}) en a_{n}, no necesitamos mas a a_{0}, y podemos desplazarnos de a_{1} a a_{0}, a_{2} a a_{1}, etc. Lo más importante es el caso especial cuando f es una función lineal sobre el registro de 2 - elementos, y nos restringiremos a este caso.

Mirando ejemplos particulares, los bits generados por un registro de desplazamiento lineal se ven aleatorios, al menos por algún rato. Por supuesto, la secuencia a_{0},a_{1},..., eventualmente tendremos alguna tupla-n que se repetirá, y entonces será periódico desde ahí; pero esto no necesariamente ocurrirá antes que a_{2^{n}}, y ciertamente uno puede seleccionar la (lineal) función f a fin de que el período de la secuencia sea tan grande como 2^{n}. 121 El problema es que la secuencia tiene más estructuras escondida que solo periodicidad. Ciertamente, si

f(x_{0},dots,x_{n−1})=b_{0}x_{0}+b_{1}x_{1}+...b_{n−1}x_{n−1}

(donde b_{i} ∈ {0, 1}). Asumamos que no conocemos los coeficientes b_{0},...,b_{n−1}, pero observamos los primeros n bits a_{n} , ..., a_{2n−1} de la secuencia de salida. Entonces tenemos el siguiente sistema de ecuaciones lineales para determinar los b_{i} :

b_{0}a_{0}+b_{1}a_{1}+...b_{n−1}a_{n−1} = a_{n} b_{0}a_{1}+b_{1}a_{2}+...b_{n−1}a_{n} = a_{n+1}

⋮

b_{0}a_{n−1}+b_{1}a_{n}+...b_{n−1}a_{2n−2} = a_{2n−1}

Aquí hay n ecuaciones para determinar estas n incógnitas (las ecuaciones son sobre el campo 2-elementos).Una vez que tenemos los b_{i}, podemos predecir todos los elementos restantes de la secuencia a_{2n}, a_{2n+1}, ... Puede ocurrir, por supuesto, que este sistema no tenga solución única, porque las ecuaciones son dependiente. Por ejemplo, podríamos comenzar con la semilla 00...0, en cuyo caso las ecuaciones son inútiles. Pero puede ser que para una elección aleatoria de la semilla, las ecuaciones determinen los coeficientes b_{i} con alguna probabilidad positiva. Así después de ver los primeros 2n elementos de la secuencia, los demás ño se vean aleatorios’para un observador que está dispuesto solo a ocupar una computación relativamente simple (tiempo polinomial). (8.2) Ejemplo Lo mas importante para generadores de número pseudoaleatorios en la práctica son los generadores de congruencia lineales . Tal generador es definido por tres parámetros a, b y m, los cuáles son números enteros positivos. Comenzando con una semilla X_{0}, el cuál es un entero en el rango 0 ≤ X_{0} ≤ m-1, el generador computa recursivamente enteros X_{1}, X_{2}, ... por

X_{i} = aX_{i−1} + b (mod m).

Uno podría usar todos los Xi o extraerlos, es decir, el centro de cada bit, y la salida de esta secuencia. Sin considerar que la salida de estos generadores también puede ser calculada por una computación de tiempo polinomial, después de observar un número polinomial de bits de salida. Los algoritmos al hacer eso están más involucrados, sin embargo, y debido a su rápido y su simplicidad, los generadores de congruencia lineales son buenos para la mayoría de aplicaciones prácticas.

(8.3)Ejemplo Como un tercer ejemplo, miremos la expansión binaria de, es decir, \sqrt{5} :

\sqrt{5} = 10.001111000110111...

Esta secuencia se ve bastante aleatoria. Por supuesto, no podemos usar el mismo número todo el tiempo; pero se puede ocupar, es decir, un entero de n-bite a como nuestra ’semilla’, y la salida los bits de \sqrt{a} - ⌊\sqrt{a}⌋. Desafortunadamente, este método resulta ser ’frágil’por razones complejas (pero de tiempo polinomial) de metodologías de teoría algorítmica de número.

122

8.4 La noción de un generador de número seudoaleatorio En general, un generador de bit seudoaleatorio transforma una pequeña,

pero verdaderamente secuencia aleatoria s (la ’semilla’) en una secuencia más larga g(s) que todavía ’se veáleatoria. El éxito de utilizar g(s) en lugar de una secuencia aleatoria depende de qué tan estricto es testeada la aleatoriedad de g(s) por la aplicación. Si la aplicación tiene la habilidad para probar todas las semillas posibles que podrían haber generado g(s), entonces esta encontraría la verdadera semilla y poco de aleatoriedad quedaría. Para esto, sin embargo, la aplicación puede tener que correr demasiado tiempo. Nos gustaría llamar a g un generador de bit seudo-aleatorio si ninguna de las aplicaciones corriendo en tiempo polinómial pueden distinguir g(s) de una verdadera cadena aleatoria. Para hacer la definición precisa, necesitamos alguna preparación. Decimos que una función f : ℤ_{+} → ℝ es ínfima, si n^{k}f(n) → 0 como n → ∞ para cada k fijo. En otras palabras, f tiende a 0 mas rápido que el recíproco de cualquier polinomio. Será conveniente para denotar esto (análogamente a la notación ’big-O’), por f (n) = NEGL (n).

Notar que una multiplicación polinomial de funciones ínfimo es todavía ínfimo; Así

n^{r}NEGL(n) = NEGL(n)

Para cada r fijo. Considere una función de tiempo polinomial G : {0,1}^{∗} → {0, 1}^{∗}, Donde damos por supuesto que |G(x)| depende de |x| y |x| ≤ |G(x)| < |x|^{c} para alguna constante c. Llamamos tal función un generador. Sea A un algoritmo de tiempo polinomial aleatorizado (máquina de Turing) que acepta cualquier cadena x de 0-1 como entrada y los computa un bit A(x) de ella. (Interpretaremos 0 como una salida ño aleatoria’, y 1 como una salida áleatoria’.) Fijamos n ≤ 1. Sea x seleccionado uniformemente de {0,1}^{n} y será y seleccionada uniformemente de {0,1}^{N}, donde N = |G(x)|. Nosotros lanzamos una moneda al aire, y dependiendo del resultado, nosotros alimentaremos a G(x) o y a A. Decimos que A es exitosa si cualquier G(x) fue alimentada para A y la salida fue 0 o y fue alimentada y la salida es 1. El generador G es llamado un (estrictamente) generador de números aleatorios si para cada algoritmo de tiempo polinomial aleatorizado A que toma una cadena x de 0-1 como la entrada y computa un bit A(x) de esto, la probabilidad que A sea exitosa es en la mayoría 1/2 + NEGL(n). La condición (b) dice que G(x) pasa cada prueba ’razonable’(cualquier experimento computable en tiempo polinomial aleatorizado) en el sentido que la probabilidad que tal prueba reconozca que G(x) no es verdaderamente aleatorio es sólo ínfimamente más grande que 1/2 (suponiendo que pueda ser llevado a cabo este adivinador de aleatoriedad). La probabilidad en (b) es sobre la elección aleatoria de x e y, sobre el lanzamiento de la moneda determinando cuál es que alimenta a A, y sobre los lanzamientos internos de A. Este requisito es tan necesario que es desconocido si los generadores de números aleatorios seguros existen del todo (si existen, entonces P ≠ NP; vea los ejercicios). Pero veremos en la siguiente sección que existen, bajo algunas suposiciones de la teoría de complejidad. La condición (b) es muy general y esto es difícil de verificar. El siguiente teorema de Yao provee una forma para establecer que una función es un generador de números aleatorios seguro más conveniente. Lo que dice es que todo bit de G(x) es altamente imprevisible de los bits previos, mientras el algoritmo de predicción no se exceda mucho en el tiempo.

123

Decimos que un generador g es impredecible si se aplica lo siguiente. Sea n ≥ 1 y x seleccionada uniformemente de {0,1}^{n}. Sea g(x) = G_{1}G_{2}...G_{N}. Para cada algoritmo de tiempo polinomial aleatorizado A que acepta una cadena x ∈ {0,1}^{i} (i≤N) como la entrada y se computa un bit así

max P(A(G_{1}...G_{i})=G_{i+1}) = \frac{1}{2} + NEGL(n)

i

Informalmente: Tratamos de usar A para predecir cada bit de g_{1}...g_{N} de los bits previos. Entonces en cualquier etapa, la probabilidad que suceda es sólo ínfimamente más grande que 1/2 (el cual seria posible si lleváramos a cabo un adivinador aleatorio).

(8.2) Teorema [A. Yao] Un generador g es un generador de números aleatorios seguro si y sólo si es impredecible.

Prueba I. Suponga que g no es impredecible. Entonces hay un algoritmo de tiempo polinómial aleatorizado A, una constante k > 0, existen infinitamente muchos valores de n, y para cada valor hay un cierto i < N, tal que

P(A(G_{1}...G_{i})=G_{i+1}) > \frac{1}{2} + \frac{1}{n^{k}}.

(Donde la x ∈ {0,1}^{n} es una cadena aleatoria escogida uniformemente y g(x) = G_{1}...G_{N}).

Pero entonces podemos realizar la siguiente prueba de aleatoriedad B en la cadena y = y_{1}...y_{N}: si A(y_{1}...y_{i}) = y_{i+1} nosotros declararemos a y ño al azar’, o sino la declaramos ál azar’. Entonces si suponemos B una cadena verdaderamente aleatorio R_{1}...R_{N} o g(x) (cada una con probabilidad 1/2), la probabilidad de éxito es.

\frac{1}{2}P(A(R_{1}...R_{1})≠R_{i+1})+\frac{1}{2}P(A(G_{1}...G_{i})=G_{i+1})

≥\frac{1}{2} \frac{1}{2}+\frac{1}{2}(\frac{1}{2}+\frac{1}{n^{k}})=\frac{1}{2}+\frac{1}{2n^{k}}.

Siempre que sea más grande que 1/2 (obviamente, no sea ínfimamente mas grande), el generador no es seguro.

II. Asume que allí existe un algoritmo A que, para muchos valores infinitamente de n, distingue la secuencia pseudoaleatoria g(x) = G_{1}...G_{N} de una secuencia verdaderamente aleatoria r = R_{1}...R_{N} con una probabilidad de éxito que está al menos en 1/2 + n^{−k} para alguna constante k > 0. Queremos mostrar que en este caso podemos predecir algunos de los bit de G_{1}...G_{N}.

La probabilidad de éxito de A es.

\frac{1}{2}P(A(r) = 1)+\frac{1}{2}P(A(g(x)) = 0) (El éxito quiere decir que A acepte a r, si r es dado para eso, pero rechaza g(x), si g(x) es dado para esto). En otras palabras, esta probabilidad es.

\frac{1}{2}+\frac{1}{2}(P(A(r)=1)-P(A(g(x))=1)). Así esto sigue como.

P(A(r)=1)-P(A(g(x))=1)>\frac{2}{n^{c}}.

124

El truco es considerar las secuencias mixtas.

y^{i} = G_{1}...G_{i}R_{i+1}...R_{N} y lo sujetamos a A. Tenemos que y^{0} = r y y^{N} = g(x) y

P(A(y^{0})=1)-P(A(y^{N})=1) > \frac{2}{n^{k}}. Por lo tanto se deduce que hay un índice i, 1 ≤ i ≤ N, algo semejante a

P(A(y^{i−1})=1)-P(A(y^{i})=1) > \frac{2}{Nn^{k}}. Vamos a enseñar que éste i es predecible con probabilidad de éxito no ínfima más grande que 1/2. El algoritmo de predicción es simple: Suponemos que

X = R_{i+1} ⊕ A(y^{i}) el valor de G_{i+1} (este valor es ciertamente computado por un algoritmo de tiempo polinomial aleatorizado de G_{1}...G_{i}).

Para la simplicidad de notación, escribimos G=G_{i}, R = R_{i}, y

A_{0} = A(G_{1}...G_{i−1}0R_{i+1}...R_{N}),A_{1} = A (G_{1}...G_{i−1}1R_{i+1}...R_{N}). Note que G,X,R, A_{0} y A_{1} son bits aleatorios. Estos no son independientes en general, pero R es independiente de los demás. Además, es fácil ver que podemos escribir

X = R(1- A_{1}) + (1 - R) A_{0} si G=X (en otras palabras, nuestra predicción es exitosa) es equivalente decir que.

G(R(1-A_{1})+(1-R)A_{0})+(1-G)(1-R(1-A_{1})-(1-R)A_{0})=1, O

GR(1-A_{1})+G(1-R)A_{0}+(1-G) - (1-G)R(1-A_{1})-(1-G)(1-R)A_{0}=1. El lado izquierdo es siempre 0 o 1, la probabilidad que ésta ocurre depende de la otra parte. Pero esto es.

E(GR(1-A_{1}) + G(1-R)A_{0} + (1-G)-(1-G)R(1-A_{1})-(1-G)(1-R)A_{0})

= E(GR(1-A_{1})) + E(G(1-R)A_{0} )+ E(1-G)-E((1-G)R(1-A_{1}))-E((1-G)(1-R)A_{0})).

125 Como R es independiente de las otras variables, podemos poner E( R) = 1/2, y podemos llegar a.

\frac{1}{2}(E(G(1-A_{1})) + E(GA_{0} )+ 2E(1-G)-E((1-G)(1-A_{1}))-E((1-G)A_{0}))

= \frac{1}{2}E(1+2GA_{0}-2GA_{1}-A_{0}+A_{1}).

También podemos expresar (8.4) en términos de estos bits. De hecho, A(y^{i})=RA_{1}+(1-R)A_{0}, y

P(A(y^{i})=1)=\frac{1}{2}E(A_{0}+A_{1}). Similarmente, A(y^{i+1})=GA_{1}+(1-G)A_{0}, y

P(A(y^{i+1})=1)=E(GA_{1}+(1-G)A_{0}). Esto (8.4) implica que

\frac{1}{2}E(A_{0}+A_{1}-2GA_{1}-2(1-G)A_{0})=\frac{1}{2}E(A_{1}-A_{0}-2GA_{1}+2GA_{0})> \frac{2}{Nn^{k}}. Pero entonces

P(G=X)=\frac{1}{2}E(1+2GA0-2GA1-A0+A1)>\frac{1}{2}+\frac{1}{Nn^{k}} >\frac{1}{2}+\frac{1}{n^{k+c}}, Muestra que nuestra predicción no es ínfimamente mejor que lo trivial.

La existencia de generadores bits seudoaleatorios puede estar derivada de algunas (no probadas) suposiciones teóricas complejas que son no obstante creíbles. Estos son abordados en la siguiente sección. 8.5 Funciones de un solo sentido Una función de un solo sentido es una función que es fácil para computar pero difícil para invertir. La definición exacta es como sigue. (8.1)Definición Una función f : {0,1}^{∗} → {0,1}^{∗} es llamada un función en un solo sentido si

(a) Hay una constante c≥1 tal que |x|^{1/c} < |f(x)| < |x|^{c}.

(b) f (x) es computable en tiempo polinomial.

(c) para cada algoritmo de tiempo polinomial aleatorizado A que computa cadenas 0 - 1 de cadenas 0 - 1, y para una cadena aleatoria y e uniformemente seleccionado de {0,1}^{n}.

P(f(A(f(y)))=f(y))=NEG(n).

126

La tercera condición necesita explicación. Lo podemos leer como sigue: Si recogemos una cadena aleatoria y de largo n, computamos f (y), y entonces tratamos de usar A para computar una pre-imagen de f (y), entonces la probabilidad tenga éxito es ínfima. Noten que no damos por supuesto que f sea invertible, así es que simplemente no podemos escribir A (f (y)) = y.

¿Pero por que no escribimos simplemente

P (f (A (z)) = z) = NEG (n) (8.3)

para un z escogido uniformemente ? El punto es que desde f puede no ir hacia esta, podría ser que la mayoría de las cadenas z no esté en el rango de f . Entonces la probabilidad citada anteriormente sería pequeña, aun si en los casos cuando z estuviera en el rango, entonces una pre-imagen siempre podría ser computada fácilmente. Así (8.2) nos concentramos en los casos cuando una pre-imagen exista, y estipulando eso aun es difícil.

Una permutación de un solo sentido es una función de un solo sentido que es uno a uno y satisface |f(x)|=|x| para todo x. Es claro que bajo esta suposición, (8.3) es equivalentes a (8.2).

(8.4) Teorema Sea g un generador de números aleatorios seguro, y asumimos que |g(x)| ≥ 2|x|. Entonces g es de un solo sentido.

Prueba Suponemos que g no es de un solo sentido, entonces allí existe una constante k > 0, un algoritmo de tiempo polinomial aleatorizado A, e infinitamente muchos valores n tal que para una cadena aleatorizada y uniformemente escogida y de {0,1}^{n},

P(g(A(g(y)))=g(y)) > \frac{1}{n^{k}}.

Ahora considere la siguiente prueba de aleatoriedad B: nosotros declaramos una cadena z ∈ {0, 1}^{N} ño aleatoria’si g(A(z))=z, y áleatoria’por otro lado. Si nosotros nos damos B y suponemos que r=R_{1}...R_{N} o g(x) es una cadena verdaderamente aleatoria (cada una con probabilidad 1/2), la probabilidad de éxito es

\frac{1}{2} P(g(A(r))≠r)+ \frac{1}{2} P(g(A(g(x)))=g(x))

El primer término esta muy cerca de 1/2; Ciertamente, el número total de cadenas en el rango de g es 2n, así la probabilidad que r este en uno de estos es 2^{n−N}<2^{−n} (y sin intervención si r esta en el rango de g, esto puede no ser igual a g(A(r)), el cual no nos ayudaría pero tampoco tendríamos que ocuparlo). El segundo término es por lo menos 1 / n^{k} por la suposición . así la probabilidad de éxito es por lo menos

\frac{1}{2}(1 − \frac{1}{2^{n}}) + \frac{1}{2} \frac{1}{n^{k}} > \frac{1}{2} + \frac{1}{4n^{k}}, lo cuál es ínfimamente más grande que 1/2.

Por otro lado describimos como usar una permutación de un solo sentido f para construir un generador de números aleatorios seguro. Para esto, necesitamos el siguiente lema dado por Goldreich y Levin. Para dos cadenas de 0-1 u = u_{1}...u_{n} y v = v_{1}...v_{n}, se define b(u,v) = u_{1}v_{1} ⊕...⊕u_{n}v_{n}.

(8.5) Lema Sea f una permutación de un sola sentido. Entonces para cada algoritmo de tiempo polinomial aleatorizado A, y para x,y seleccionada en forma aleatoria e uniformemente en {0,1}^{n},

P(A(x,y)=b(f^{−1}x,y))=\frac{1}{2}+NEGL(n).

127

Informalmente, seleccionamos un subconjunto aleatorio de los bits de f^{−1}, Su suma modulo 2 no puede ser computado con una probabilidad de éxito ínfimamente más grande que 1/2 . la prueba de este lema es muy importante, y lo tendremos que aceptarla sin prueba.

(8.6) Teorema Suponga una permutación de un solo sentido existe. Entonces allí existe un generador de números aleatorios seguro.

Prueba Describimos un generador de números aleatorios. Sea f una permutación de un solo sentido y una constante k > 0. Acortamos una secuencia aleatoria x = (x_{1}...x_{2n}) de largo 2n (la paridad del largo es para la conveniencia) para una secuencia pseudoaleatoria de largo N = n^{k} como sigue.

Compute las cadenas.

y 1^{t} ... y n^{t} = f ^{t} ( x _{1} ... x _{n} )

para t= 1,...,N ( aquí f^{t} es la función f iterada t veces), y entonces

g_{t} = y1^{t}x^{n+1} ⊕...⊕yn^{t}x_{2n}.

Mostramos que g(x) = g_{N}g_{N−1}...g_{1} define un generador de números aleatorios seguro (noten el truco de escribir los bits en el orden inverso!). Usando el teorema 8.2, esto es suficiente para que cada 1 ≤ i ≤ N, y para cada algoritmo de tiempo polinomial aleatorizada A computando un bit de g_{N}...g_{i+1}, la probabilidad que este bit es g_{i} es sólo ínfimamente más grande que 1/2. Podemos ser generosos y podemos dar al algoritmo no sólo estos bits sino toda la cadena f^{t}(x_{1}...x_{n}) para t ≥ i+1 y también la cadena x_{n+1}...x_{2n} (del cuál g_{N}....g_{i+1} es fácilmente computado). Pero entonces, no tenemos que dar f^{i+2}(x_{1}...x_{n})..., f^{n}(x_{1}...x_{n}), es fácilmente computado de f^{i+1}(x_{1}...x_{n}). Así podemos asumir que el algoritmo que se obtiene es z= f^{i+1}(x_{1},...,x_{n}) y u=x_{n+1}...x_{2n}, y tiene como g_{i}=b(f^{−1}(z),u). Pero por el lema 8.5, la probabilidad de tener éxito es sólo ínfimamente más grande que 1/2, lo que es muy necesario.

8.5.1 Los candidatos para funciones de una solo sentido

La teoría de número provee a varios candidatos de funciones de un solo sentido. El largo de entradas y salidas no será exactamente n, sólo un polinomio en n.

El problema de factorización Sea x una representación de un par de primos de largo n (es decir, junto con una prueba de su primalidad). Sea f (n, x) su producto. Muchas casos especiales de este problema son solubles en tiempo polinomial pero discretamente, una fracción grande sigue siendo difícil.

El problema de un logaritmo discreto Sea p un numero primo, una raíz primitiva g para p e i un número entero positivo i < p, devolvemos p, g e y= g^{i} mod p. El problema de inversión pues es llamado el problema del logaritmo discreto dado por p, g, y, miren para i el cual es llamado índice, del logaritmo discreto, de y con respecto a p.

El problema raíz cuadrada discreto. Dado m enteros positivos y x < m, la función de salida m e y= x^{2} mod m. El problema de inversión es encontrar una x tal que x^{2} ≡ x (mod m). Esto es soluble en tiempo polinómial por un algoritmo probabilístico si m es un primo pero es considerado difícil en general.

128

8.6 Raíces cuadradas Discretas

En esta sección abordamos el algoritmo de teoría de numero para extraer raíces cuadradas. Llamamos los enteros 0, 1,...,p-1 residuos (modulo p). Sea p un primo impar. Diremos que y es una raíz cuadrada de x ( modulo p), si

y^{2} ≡ x (mod p).

Si x tiene una raíz cuadrada entonces es llamado un residuo cuadrático.

Obviamente, 0 tiene solo una raíz cuadrada modulo p: Si y^{2} ≡ 0 (mod p), entonces p| y^{2}, y desde que p es primo, esto implica que p|y. Para todos los otros enteros x, si y es una raíz cuadrada de x, entonces es p - y = -y (mod p). No hay más raíces cuadradas: Ciertamente, si z^{2} ≡ x para algún residuo z, entonces p|y^{2}-z^{2} = (y-z)(y+z) y tambien p|y - z o p|y +z . Esto z ≡ y o z ≡ -y es exigido.

Esto significa no todo entero tiene una raíz cuadrada modulo p: al trazar un mapa de los residuos que no son cero en un subconjunto de tamaño (p - 1) / 2, y el otro (p - 1) / 2 no tiene raíz cuadrada.

El siguiente lema provee una forma fácil para decidir si un residuo tiene una raíz cuadrada.

(8.1) Lema Un residuo x tiene una raíz cuadrada si y sólo si

x^{(p−1)/2} ≡ 1 (mod p). (8.2)

Prueba El ’solo siés la parte fácil: Si la x tiene una raíz cuadrada y, entonces x^{(p−1)/2} ≡ y^{p−1} ≡ 1 (mod p)

por el Teorema ’pequeño’de Fermat. Inversamente, el polinomio x^{(p−1)/2} - 1 tiene grado (p -1) / 2, y por lo tanto tiene al menos (p- 1)/2 ’raíces’modulo p (éste puede ser probado con el bien conocido teorema que un polinomio de grado n tiene a lo mas n raíces reales) . Así todas las raíces son residuos cuadráticos de x ^{(p−1)/2}-1, ninguno de los residuos puede ser cuadrático. ¿Pero cómo encontrar esta raíz cuadrada? Para algunos primos, esto es fácil:

(8.3) Lema. Asuma que p ≡ 3 (mod 4). Entonces para cada residuo cuadrático x, x^{(p+1)/4} es una raíz cuadrada de x.

Ciertamente,

(x ^{(p+1)/4} )^{2} = x ^{(p+1)/2} = x · x ^{(p−1)/2} ≡ x (mod p).

El caso cuando p ≡ 1 (mod 4) es más difícil, y la solución usa aleatorización. De hecho, la aleatorización es sólo necesitada en el siguiente algoritmo auxiliar:

(8.4) Lema Sea p un primo impar. Entonces podemos encontrar un residuo no cuadrático modulo p en tiempo polinomial aleatorizado.

129

Esto puede estar hecho seleccionando un residuo aleatorio z ≠ 0, y entonces experimentando (usando a lema 8.1) si es un residuo cuadrático. En caso de que no, probamos otro z. Dado que la probabilidad de apuntarle es 1/2, nosotros encontraremos uno en promedio de dos pruebas.

Uno podría, claro está, tratar de evitar aleatorización si uno prueba los residuos 2, 3, 5, 7, ... para ver si tienen una raíz cuadrada. Tarde o temprano encontraremos un residuo no cuadrático. Sin embargo, no es conocido si el residuo no cuadrático menor será encontrado en el tiempo polinomial por este camino. Es conjeturado que uno nunca tiene que probar más que O (log^{2}p) números.

Ahora regresemos al problema de descubrir la raíz cuadrada de un residuo x, en el caso cuando p es primo satisfaciendo p ≡ 1 (mod 4). Podemos escribir p-1=2^{k}q, donde q es impar y k ≥ 2.

Comenzamos con encontrar un residuo no cuadrático z . El truco es encontrar una potencia par z^{2t} algo semejante a x^{q}z^{2t} ≡ 1 (mod p). Entonces podemos tomar a y= x ^{(q+1)/2} z^{t} (mod p). Ciertamente,

y^{2} ≡ x^{q+1} z^{2t} ≡ x ( mod p).

Para construir tal potencia de z, nosotros el construimos para todo j ≤ k - 1 un entero t_{j} > 0 algo semejante a

x^{2^{j}q}z^{2^{j+1}t_{j}} ≡ 1 (mod p) (8.5).

Para j = 0, esto es justo lo que necesitamos. Para j= k-1 , nosotros podemos tomar t_{k−1}=q:

x^{2^{k−1}q} z ^{2^{k}q} = x ^{(p−1)/2} z ^{p−1} ≡ 1 (mod p),

Desde que x es un residuo cuadrático y z^{p−1} ≡ 1 ( mod p) por el teorema ’Pequeño’de Fermat. Esto sugiere que construimos el número t_{j} ’hacia atrás’para j = k-2, k- 3,...

Suponga que tenemos a t_{j}, j > 0, y queremos construir a t _{j−1}. Sabemos que.

P|x^{2^{j}q}z^{2^{j+1}t_{j}} - 1 = ( x^{2^{j−1}q} z^{2^{j}t_{j}} - 1) (x^{2^{j−1}q} z ^{2^{j}t_{j}} + 1)

Probamos cuál de los dos factores es un múltiplo de p. Si es la primera parte, entonces simplemente podemos tomar a t_{j−1} =t _{j}. Sí suponemos que es el segundo. Entonces tomamos

t_{j−1}= t_{j} + 2^{k−j−1} q.

Entonces

X^{2^{j−1}q} z^{2^{j}t_{j−1}} =x^{2^{j−1}q} z ^{2^{j}t_{j}+2^{k−1}q} = x ^{2^{j−1}q} z ^{2^{j}t_{j}} z^{(p−1)/2} ≡ (-1)(-1)=1,

así z sea un residuo no cuadrático.

Esto completa la descripción del algoritmo. Muestra que ese entero cuadrado no es un generador de números aleatorios.

Para una cadena x, sea rev(x) denota la cadena inversa. Sale a la vista que si g(s) es un generador de números aleatorios seguro, entonces tambien es rev(g(s)).

Si P=NP entonces no existen función de un solo sentido.

Alguien propone el siguiente generador de números aleatorios: Toma un entero x con n bits como la semilla, y salida ⌊ x^{3} / 10^{n} ⌋. Muestre que este generador de números aleatorios no es seguro.

130