algoritmos aritméticos (13 min)

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.