Algoritmos

articulos

Algoritmos de ordenación.

Bueno, como dice el título de la entrada, voy a hablar sobre los algoritmos de ordenación, vamos a distinguir entre lentos y rápidos. La diferencia mas grande es la eficiencia, es decir, como se comportan al ordenar una gran entrada de datos, los lentos se comportan en un orden cuadrático, es decir, O(n²), mientras que los algoritmos rápidos se comportan, en un caso promedio en un orden logarítmico, osea, O (n log n).

security-now

Lo último en criptografía: Fully Homomorphic Encryption

Me he aficionado a escuchar un programa de radio llamado Security Now!, cuya web puedes consultar en las referencias. Como el nombre del programa indica, hablan sobre seguridad en sistemas informáticos principalmente. El episodio de esta semana iba enfocado a qué se está desarrollando a día de hoy en el mundo de la criptografía.

Pues bien, una de esas cosas en las que los criptógrafos están trabajando a dia de hoy se llama Homomorphic Encryption (Cifrado Homomórfico) ó Fully Homomorphic Encryption (Cifrado totalmente homomórfico).

¿Qué es el cifrado homomórfico ó Homomorphic Encryption?

Los chicos de RSA plantearon la hipótesis de este sistema de cifrado en el año 78. Postularon la posibilidad del cifrado homomórfico o ****Homomorphic Encryption. ****Pero se quedó como una pregunta abierta.

Y hace solo tres años un estudiante de posgrado sorprendió al mundo al demostrar que este sistema es posible. Lo que este estudiante hizo fue demostrar matemáticamente que es posible realizar operaciones de cálculo estándares — como sumar, multiplicar etc — a datos cifrados sin la necesidad de descifrarlos previamente.

Por ejemplo, es posible cifrar datos, enviarlos a la nube y operar sobre estos datos **sin descifrarlos ** . La *nube *no tiene la menor idea del contenido de los datos sobre los que está operando, no vé ningún resultado intermedio. La totalidad de los datos permanecen cifrados durante todo el tiempo. De manera que obtienes el resultado encriptado, y solamente tú puedes desencriptarlo. En eso consiste el cifrado homomórfico o** **Homomorphic Encryption, ** **y funciona.

dev

Optimizando código y evaluando el rendimiento

Hace un més aproximadamente terminó el plazo de entrega de la práctica que voy a hablar hoy, lo que me permite hablaros de la misma.

En concreto, el ejercício consiste en realizar varias versiones de un algoritmo, para ver cómo varía la eficiencia del mismo en función de cómo se plantee el problema, obteniendo resultados sorprendentes en cuanto a tiempo de ejecución.

Se plantean dos ejercicios. El cálculo del número de bits a 1 que tiene un número (PopCount o Peso Hamming) usado para detectar y corregir errores.

El cálculo de la paridad impar de un número.

Empecemos con popCount:

dev

Optimizar sumas en paralelo

Hace unos días leí acerca del procesador de la consola PS3 y su capacidad para realizar varias operaciones aritméticas en una sola instrucción. Es decir, dado que tiene un bus de 128 bits, podría sumar 4 valores de 32 bits en una operación. Me sirvió para darle vueltas a la cabeza e intentar hacer lo mismo en mi ordenador. La anchura del bus de un procesador es equivalente al número de cifras que puede tener la pantalla de una calculadora simple, sólo que en lugar de tratarse de dígitos decimales (del 0 al 9) son dígitos binarios (0 ó 1).