A palavra randômico é sinônimo de aleatório. Algo que acontece de forma imprevista.

Na computação, esta imprevisibilidade é indispensável para criptografia, jogos e aplicações onde não podemos ter determinismo.

Determinismo pode ser considerado como o antônimo de aleatoriedade.

Tudo, tudo nos computadores digitais é determinístico. Computadores digitais não são máquinas eficientes para a geração de números randômicos.

Podemos usar um hardware especial: ruido de transistores e ruídos quânticos. A Intel incluiu um Gerador de Números Randômicos na Arquitetura Ivy Bridge.

Podemos usar sites especializados para gerar números randômicos: Random.org

Nos softwares, tudo que temos são Geradores de Números Pseudorandômicos.

Toda linguagem de programação tem, no mínimo um gerador de números Pseudorandômicos. Algumas têm vários. Outras têm bibliotecas para esta funcionalidade.

A maioria destes geradores se baseiam em uma função de geração que é linear e congruente.

Estes geradores usam a função: $X_{n+1}=(a \times X_n + c)\text{ } (mod \text{ } m)$

1. $m$ e $c$ são primos e muito grandes;
2. $a-1$ é divisível por todos os fatores primos de $m$;
3. $a-1$ é divisível por $4$ se $m$ é divisível por $4$.

Uma relação algébrica que pode ser expressa por uma função.

Dizemos que dois números $x$ e $y$ se eles apresentam o mesmo resto quando divididos por um terceiro $n$.

A Microsoft usa:$X_{n+1}=(214013 \times X_n + 2531011)\text{ } (mod \text{ } 2147483648)$ .

O resultado desta operação é dividido por 16. São gerados números entre 0 e 32767.

Estes números determinam a qualidade do gerador e são definidos matemática e cuidadosamente.

Outra possibilidade: $X_{n+1}=(16807 \times X_n + 2531011)\text{ } (mod \text{ } 2147483647)$ (LEWIS, et. al,1988).

Na prática.... vamos ver um pouco de código.

Geradores lineares Congruentes são falhos, atendem apenas emergências e demonstrações.

O algoritmo chamado de Mersenne Twister foi desenvolvido em 1997 por Makoto Matsumoto e Takuji Nishimura.

Tem um ciclo de repetição que é igual a um dos números primos de Mersenne o $2^{19937}-1$.

De onde tiramos seu nome MT19937. As principais linguagens de programação possuem uma implementação deste algoritmo. Inclusive o C++.

Números primos que são imediatamente anteriores a uma potência de dois, então são representados por $2^m-1$

Recebem este nome em honra de Marin Mersenne, um frade francês que estudou estes números no Século XVII.

A sequência destes números é: $M=\{3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ...\}$.

O número $2^{77232917} - 1$ representa o maior número primo conhecido
(RALEIGH, 2018 ).

Toda a criptografia que usamos hoje, funciona graças a algoritmos baseados em números primos.

Fatorar grandes números custa muito caro, computacionalmente falando.

por exemplo: $2244354$ é fatorado em $(1* 2 * 3 * 7 * 53437)$. Não é óbvio.

Algoritmos de fatoração simples: aproximação da raiz quadrada, Euler...

Na prática.... vamos ver um pouco de código.

Desenvolva no Repl.it, uma implementação do Crivo de Eratóstenes (sieve of eratosthenes).

Em qualquer linguagem de programação.

Vamos direto para o código.

O problema do embaralhamento (shuffle) é o problema inverso da ordenação.

Dado um conjunto de dados $A=\{a_1, a_2, a_3,..,a_4\}$. Queremos produzir um conjunto de dados $E$ tal que não exista uma relação possível entre a posição de um item de $A$ e o item na mesma posição em $E$.

O algoritmo mais simples, definido por Ronald Fischer e Frank Yeats em 1938 ainda está em uso e consiste em:

for i from last downto 1 do:
	let j = random integer in range 0 <= j  <= i
		swap items[i] with items[j]