RSA Encriptación

Es un criptosistema de clave pública que sirve tanto para encriptar mensajes como para autenticación de documentos o transacciones (firma digital).
Fue inventado en 1977 por Rivest Ron, Shamir Adi y Adleman Leonard.
El algoritmo de encriptación RSA es el más utilizado y seguramente el más sencillo tanto como su comprensión, como por su implementación.
La seguridad de este algoritmo se basa en la factorización de números primos. El algoritmo RSA sera seguro  mientras no se conozca una manera de descomponer un número grande en productos primos.

Algoritmo

El algoritmo consta de tres pasos: generación de claves, cifrado y descifrado.

Generación de claves

1. Se obtiene 2 números primos p = 17 y q = 43.
2. Se calcula n = p * q = 731.
3. Se calcula φn = (p - 1)*(q - 1) = 672.
4. Se busca un número e tal que sea primo con φn, mcd(e, φn) = 1.
5. Como e y φn son primos entre si, entonces existe un d tal que d = e^(-1) mod  φn, e = 101, d = 173. Esto se suele calcular con el Algoritmo Extendido de Euclides.

Finalmente obtenemos la clave pública Ce = (e, n) = (101, 731), y la clave privada Cd = (d, n) = (173, 131).

100 - The 3n + 1 problem

Descripción del Problema:

http://uva.onlinejudge.org/external/1/100.html

Solución:

Dado dos números enteros i, j se debe determinar el tamaño del ciclo entre ambos números, la descripción del problema no dice que siempre se cumple que i < j  en todos los casos, por lo que se debe verificar que esa condición sea verdadera. Ademas se asume que ninguna operación excede un entero de 32-bit.
En vez de usar la operación modulo se puede reemplazar por la operación bitwise '&' para determinar si un número es par o impar.
Otra optimización que se puede emplear es aumentar el ciclo en 2 cada vez que se realiza la operación 3n + 1 y en el siguiente paso se debe reducir n  por n / 2  para obtener el resultado.

Entrada:

10 1
210 201
999999 1

Salida:

10 1 20
210 201 89
999999 1 525

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int i, j, max_cycle_length, cycle_length, n;
    while (scanf ("%d%d", &i, &j) == 2) {
  printf("%d %d ", i, j);
        if (j < i) {
   swap (i, j);
  }
        max_cycle_length = 0;
        while (i <= j) {
            n = i;
            cycle_length = 1;
            while (n != 1) {
                if (n&1) {
     n = (3 * n) + 1;
    }
                else {
     n /= 2;
    }
                cycle_length++;
            }
            if (max_cycle_length < cycle_length) {
                max_cycle_length = cycle_length;
   }
            i++;
        }
        printf("%d\n", max_cycle_length);
    }
    return 0;
}