A próxima coisa que vamos olhar é como calcular modulares inteiros grandes. Assim
a primeira pergunta é: como podemos representar inteiros grandes em um computador? Então, isso é
na verdade, bastante simples. Então, imagine que estamos em uma máquina de 64 bits, o que
gostaria de fazer é que iria quebrar o número que deseja representar, em 32 bits e baldes
, em seguida, iremos basicamente tem esses n/32 baldes de bits, e juntos eles vão
representam o número que deseja armazenar no computador. Agora, devo mencionar
que eu só estou dando de 64 bits registra como um exemplo. Na verdade, muitos moderna
processadores têm 128 registros bits ou mais, e você pode até fazer multiplicações em
-los. Então, normalmente, você realmente usar blocos muito maiores do que apenas 32 bits. O
razão, a propósito, você quer limitar-se a 32 bits é assim que você pode
multiplicar dois blocos juntos, eo resultado será ainda menos de 64 bits,
menor do que o tamanho de palavra sobre a máquina. Então, agora vamos olhar para aritmética particular
operações e ver quanto tempo cada um leva. Então, adição e subtração
basicamente o que você gostaria de fazer é que a adição ou subtração levaria seria
emprestado e esses são basicamente as operações de tempo linear. Em outras palavras, se você quiser
adicionar ou subtrair dois números inteiros n pouco o tempo de execução é basicamente
linear em n. Multiplicação ingenuamente vai levar tempo quadrático. Na verdade,
isso é que é chamado de algoritmo de ensino médio. Este é o tipo de você
aprendeu na escola, onde se você pensar sobre isso por um minuto você vai ver que,
que o algoritmo é basicamente quadrática no comprimento dos números que estão a ser
multiplicado. Assim, uma grande surpresa na década de 1960 era um algoritmo devido a Karatsuba que
realmente atinge muito melhor do que o tempo quadrática de facto, ter atingido um
tempo de execução de n para o 1,585. E não há realmente nenhum ponto em me mostrar
como o algoritmo efectivamente trabalhadas, vou apenas mencionar a idéia principal que
Karatsuba percebi, é que na verdade, quando você quer multiplicar dois números, você pode
gravá-los como, você pode pegar o primeiro número x, escrevê-lo como 2 às vezes b
x2 mais x1. Onde X1 X2 e são aproximadamente o tamanho da raiz quadrada de x. Ok, então
podemos tipo de quebrar o número x em parte esquerda da x ea parte direita de x.
E, basicamente, você está escrevendo x como se fosse escrito à base 2 b. Então, ele tem
base de dois dígitos 2 a b. E você faz a mesma coisa com, y. Você escreve de base y
2 para o b. Mais uma vez, que iria escrever-lo como, a soma de a metade esquerda da adição
meia direita, e então, normalmente, se você tentar fazer essa multiplicação, quando você abre
os parênteses. Você vê que, isso exigiria 4 multiplicações, certo?
Seria necessário x2 vezes y2, x2 vezes y1, y2 x1 vezes e vezes x1 y1. O que
Karatsuba percebi é que há uma maneira de fazer essa multiplicação de x por y utilizando apenas
três multiplicações de x1 x2 y1 y2. Então é só uma multiplicação grande de x vezes y
leva apenas três multiplicações pequenos. Você pode agora recursivamente
aplicar exactamente o mesmo procedimento para a multiplicação por x2 y2, e x2 por y1, e assim
sobre e assim por diante. E você teria este algoritmo recursivo. E se você fizer o
análise recursiva, você vai ver que, basicamente, você tem um tempo de execução de n para o 1,585.
Este número é, basicamente, a 1,585 é basicamente, faça de 3 de base 2.
Surpreendentemente, verifica-se que Karatsuba não é mesmo o melhor de multiplicação
algoritmo lá fora. Acontece que, na verdade, você pode fazer a multiplicação em cerca de n * log do tempo (n).
Então você pode fazer a multiplicação quase em tempo linear. No entanto, este é um resultados extremamente assintóticas.
O O grande aqui esconde constantes muito grandes. E como um
resultado, este algoritmo só se torna prático quando os números são absolutamente
enorme. E assim este algoritmo não é realmente usado com muita freqüência. Mas
algoritmo Karatsuba é muito prático. E na verdade a maioria, cripto-bibliotecas
implementar algoritmo Karatsuba para multiplicação. No entanto, para simplicidade
aqui, eu só vou ignorar algoritmo Karatsuba, e apenas para simplificar, eu sou
vou assumir que a multiplicação é executado em tempo quadrático. Mas em sua mente, você
deve ser sempre pensando que tudo multiplicação realmente é um pouco mais rápido do que quadrático.
E então a pergunta seguinte, depois de multiplicação é o que acontece com
divisão com resto e verifica-se que também é um algoritmo de tempo quadrático.
Assim, a principal operação que permanece, e que nós usamos muitas vezes até agora, e
Eu nunca, na verdade, nunca, nunca te disse como realmente computá-lo, isso é
questão de exponenciação. Então, vamos resolver este problema exponenciação um pouco mais
abstratamente. Então, imagine que temos um grupo cíclico finito G. Tudo isso significa é que
este grupo é gerada a partir dos poderes de alguns g gerador pouco. Assim, por exemplo
pensar desse grupo como simplesmente * ZP, e acho que de g pouco como alguns gerador de
grande G. A razão que eu estou sentado, desta forma, é que eu sou, eu quero que você começar a se acostumar
para essa abstração onde lidamos com um genérico grupo G e * ZP é realmente apenas
um exemplo de um tal grupo. Mas, na verdade, existem muitos outros exemplos de finito
grupos cíclicos. E novamente eu quero ênfase basicamente que o grupo G, tudo o que
é, é simplesmente este poderes deste gerador até ao fim do grupo.
vou escrevê-lo como G para o P. Portanto, nossa meta agora é dado este elemento g, e alguns
expoente x, nosso objetivo é calcular o valor de g para o x. Agora, normalmente o que você
diria que é, você pensaria bem, você sabe, se x é igual a 3 então eu sou
vai computar que você sabe, g em cubos. Bem, não há realmente nada a fazer. Tudo o que faço é
Eu só faço g vezes g g vezes e eu fico g cubo, que é o que eu queria. Então, isso é
realmente muito fácil. Mas, na verdade, isso não é o caso que nós estamos interessados dentro Em
nosso caso, os nossos expoentes vão ser enormes. E então se você tentar, você sabe,
pensar como um número de 500-bit e por isso, se você tentar calcular g para o poder de um
número 500-bit simplesmente multiplicando g por g por g por g isso vai levar um bom
enquanto. Na verdade isso vai levar tempo exponencial que não é algo que queremos
fazer. Portanto, a questão é se ainda que x é enorme, ainda podemos calcular
g ao x relativamente rápido ea resposta é sim e o algoritmo que faz isso
é chamado um algoritmo de quadratura repetida. E então deixe-me mostrar-lhe como repetido
obras esquadria. Então, vamos tomar como exemplo, de 53 anos. Ingenuamente, você teria que fazer
53 multiplicações de g por g por g por g até chegar ao g por 53, mas eu quero
mostrar como você pode fazê-lo muito rapidamente. Então o que vamos fazer é que vou escrever 53 em
binário. Então aqui é a representação binária de 53. E tudo isso significa
é, você percebe isso, corresponde a 32, esta corresponde a 16, este
corresponde a 4, e este corresponde a 1. Então, realmente é 32 53
mais 16 mais 4 mais 1. Mas o que isto significa é que g ao poder de 53 é
g para o poder de 32 16 4 1. E nós podemos quebrar essa para cima, usando mais uma vez, as regras de
exponenciação. Podemos quebrar isso como g para o g 32 vezes para o g 16 vezes para o
4 vezes g para o 1, agora que deve começar a dar uma idéia de como calcular g para
a 53 muito rapidamente. O que vamos fazer é, simplesmente, vamos g e vamos começar
quadratura-lo. Então, o que quer praça, quer para obter g g quadrado. Nós quadrado novamente para
obter g para o 4, desligue g para o 8. Ligue g para o 16, g para o 32. Assim
nós computados todos esses quadrados de g. E agora, o que vamos fazer é que estamos simplesmente
vai multiplicar os poderes adequados para poder nos dar a g para o 53. Portanto, esta é a g
os um vezes g às 4 vezes g às 16 vezes g para o 32, é basicamente
vai nos dar o valor que queremos, que é g para o 53. Então aqui você vê que
tudo o que tínhamos a fazer era apenas calcular, vamos ver, tivemos que fazer um, dois, três, quatro,
quadratura cinco, além de quatro multiplicações mais com 9 multiplicações nós computadorizada g
ao 53. Ok então isso é muito interessante. E acontece que este é um
fenômenos gerais, que nos permite levantar g de poderes muito, muito altas e fazê-lo muito
rapidamente. Então deixe-me mostrar-lhe o algoritmo, como eu disse isso é chamado de repetidas
algoritmo de quadratura. Assim, a entrada para o algoritmo é o elemento g eo
expoente x. Ea saída é g para o x. Então o que vamos fazer é que nós vamos
x escrever em notação binária. Então vamos dizer que x tem n bits. E esta é a real
representação de bits de x como um número binário. E então o que vamos fazer é o
seguinte. Nós vamos ter estes dois registos. y vai ser um registo que é constantemente
quadrado. E então z vai ser um acumulador que se multiplica no
poderes apropriados de g, conforme necessário. Então, tudo o que fazemos é o loop através do seguinte
bits de x a partir dos bits menos significativos e, então, fazer o
seguinte: em cada iteração estamos simplesmente indo y quadrado. Ok, então y só continua a
quadratura a cada iteração. E, em seguida, sempre que o bit correspondente do
expoente x passa a ser um, simplesmente acumular o valor atual de y em
este z acumulador e, em seguida, no final, simplesmente saída z. É isso aí. Essa é a
algoritmo inteiro, e isso é o algoritmo de quadratura repetida. Então, vamos ver um
exemplo, com o G 53. Assim, você pode ver as duas colunas. y é um
coluna, à medida que evolui através das iterações, e Z é uma outra coluna, de novo
à medida que evolui através das iterações. Assim, y não é muito interessante. Basicamente, tudo
que acontece com y é que a cada iteração, ele simplesmente fica quadrado. E assim
ele só anda pelas potências de dois e os expoentes e é isso. z é a
registo mais interessante onde o que ele faz é que acumula o adequado
poderes de g sempre que o bit correspondente ao expoente é um. Assim, por exemplo o
primeiro bit do expoente é um, portanto, o, no final do primeiro
iteração do valor de z é simplesmente igual ao g. O segundo bit do expoente é igual a zero
para que o valor de z não muda após a segunda iteração. E no final do
terceira iteração bem o terceiro bit do expoente é um modo que se acumulam ao g
quarto em z. O próximo bit do expoente é zero para z não muda. O
próximo bit do expoente é um só e agora nós somos supostos para acumular o anterior
valor de y na z acumulador então deixe-me perguntar-lhe então o que vai ser o valor de z?
Bem, nós simplesmente acumular g aos 16 em z e assim nós simplesmente calcular a soma
, de 16 e 5 g de chegarmos a 21. Finalmente, o último bit é também definido como um
assim que nós acumulá-lo em z, fazemos 32 mais 21 e ficamos com a saída g, finalmente, para o 53.
Ok, então isso dá uma idéia de como isso funciona algoritmo repetidas esquadria.
É um algoritmo é bastante interessante e que nos permite calcular enormes poderes de
g muito, muito, muito rapidamente. Portanto, o número de iterações aqui, essencialmente, seria
log base 2 de x. Okay. Você percebe o número de iterações simplesmente depende da
número de dígitos de x, que é basicamente a base 2 log de x. Assim, mesmo se x é um
bit número 500 em 500 multiplicação, bem, 500 iterações, realmente 1000
multiplicações porque temos de conciliar e nós temos que acumular. Assim, em 1000
multiplicações nós vamos ser capazes de levantar g para a potência de um expoente bit 500.
tipo Ok então agora podemos resumir os tempos de execução para supor que
ter um pouco de capital módulo N N como dissemos adição e subtração em ZN leva
tempo linear. Multiplicação de apenas, você sabe, como eu disse, Karatsuba na verdade torna essa
mais eficiente, mas para simplificar, vamos apenas dizer que é preciso tempo quadrático. E
exponenciação, então, como eu disse, basicamente leva log de iterações x, e em cada
iteração, basicamente, fazer duas multiplicações. Então, é O (log (x))
vezes o tempo para se multiplicar. E digamos que o tempo para multiplicar é quadrática. Assim
tempo a execução seria, realmente, N x log quadrados. E desde que x é sempre vou
ser inferior a N, pelo teorema de Fermat não há nenhum ponto em levantar g para uma potência
que é maior do que o módulo. Assim x vai ser inferior a N. Vamos supor que x
também é um número inteiro N-bits, então, realmente exponenciação é um algoritmo de cúbico-tempo.
Ok é isso que eu queria que você se lembre, que a exponenciação é realmente
uma relativamente lenta. Esses dias, ele realmente leva alguns microssegundos em um moderno
computador. Mas ainda assim, microssegundos para um, para uma, digamos, um processador de quatro é gigahertz
um pouco de trabalho. E assim, basta ter em mente que tudo o exponenciação
operações que falamos. Por exemplo, para determinar se um número é um quadrática
resíduo ou não, todos aqueles que, todos aqueles exponenciações, basicamente, ter tempo cúbico.
Ok, então que completa a nossa discussão de algoritmos aritméticos, e depois na
próximo segmento nós vamos começar a falar de problemas de disco rígido, modulo, primos e compostos.