WEBVTT

00:00:00.000 --> 00:00:04.528
A próxima coisa que vamos olhar é como calcular modulares inteiros grandes. Assim

00:00:04.528 --> 00:00:09.023
a primeira pergunta é: como podemos representar inteiros grandes em um computador? Então, isso é

00:00:09.023 --> 00:00:13.615
na verdade, bastante simples. Então, imagine que estamos em uma máquina de 64 bits, o que

00:00:13.615 --> 00:00:18.361
gostaria de fazer é que iria quebrar o número que deseja representar, em 32 bits e baldes

00:00:18.361 --> 00:00:22.686
, em seguida, iremos basicamente tem esses n/32 baldes de bits, e juntos eles vão

00:00:22.686 --> 00:00:26.906
representam o número que deseja armazenar no computador. Agora, devo mencionar

00:00:26.906 --> 00:00:30.705
que eu só estou dando de 64 bits registra como um exemplo. Na verdade, muitos moderna

00:00:30.705 --> 00:00:34.977
processadores têm 128 registros bits ou mais, e você pode até fazer multiplicações em

00:00:34.977 --> 00:00:38.987
-los. Então, normalmente, você realmente usar blocos muito maiores do que apenas 32 bits. O

00:00:38.987 --> 00:00:42.943
razão, a propósito, você quer limitar-se a 32 bits é assim que você pode

00:00:42.943 --> 00:00:46.952
multiplicar dois blocos juntos, eo resultado será ainda menos de 64 bits,

00:00:46.952 --> 00:00:51.189
menor do que o tamanho de palavra sobre a máquina. Então, agora vamos olhar para aritmética particular

00:00:51.189 --> 00:00:54.788
operações e ver quanto tempo cada um leva. Então, adição e subtração

00:00:54.788 --> 00:00:58.742
basicamente o que você gostaria de fazer é que a adição ou subtração levaria seria

00:00:58.742 --> 00:01:03.000
emprestado e esses são basicamente as operações de tempo linear. Em outras palavras, se você quiser

00:01:03.000 --> 00:01:06.954
adicionar ou subtrair dois números inteiros n pouco o tempo de execução é basicamente

00:01:06.954 --> 00:01:12.626
linear em n. Multiplicação ingenuamente vai levar tempo quadrático. Na verdade,

00:01:12.626 --> 00:01:16.676
isso é que é chamado de algoritmo de ensino médio. Este é o tipo de você

00:01:16.676 --> 00:01:21.114
aprendeu na escola, onde se você pensar sobre isso por um minuto você vai ver que,

00:01:21.114 --> 00:01:25.662
que o algoritmo é basicamente quadrática no comprimento dos números que estão a ser

00:01:25.662 --> 00:01:30.156
multiplicado. Assim, uma grande surpresa na década de 1960 era um algoritmo devido a Karatsuba que

00:01:30.156 --> 00:01:34.150
realmente atinge muito melhor do que o tempo quadrática de facto, ter atingido um

00:01:34.150 --> 00:01:38.567
tempo de execução de n para o 1,585. E não há realmente nenhum ponto em me mostrar

00:01:38.567 --> 00:01:43.166
como o algoritmo efectivamente trabalhadas, vou apenas mencionar a idéia principal que

00:01:43.166 --> 00:01:48.071
Karatsuba percebi, é que na verdade, quando você quer multiplicar dois números, você pode

00:01:48.071 --> 00:01:52.976
gravá-los como, você pode pegar o primeiro número x, escrevê-lo como 2 às vezes b

NOTE Paragraph

00:01:52.976 --> 00:01:57.882
x2 mais x1. Onde X1 X2 e são aproximadamente o tamanho da raiz quadrada de x. Ok, então

00:01:57.882 --> 00:02:02.910
podemos tipo de quebrar o número x em parte esquerda da x ea parte direita de x.

00:02:02.910 --> 00:02:07.654
E, basicamente, você está escrevendo x como se fosse escrito à base 2 b. Então, ele tem

00:02:07.654 --> 00:02:12.398
base de dois dígitos 2 a b. E você faz a mesma coisa com, y. Você escreve de base y

00:02:12.398 --> 00:02:16.911
2 para o b. Mais uma vez, que iria escrever-lo como, a soma de a metade esquerda da adição

00:02:16.911 --> 00:02:21.540
meia direita, e então, normalmente, se você tentar fazer essa multiplicação, quando você abre

00:02:21.540 --> 00:02:27.486
os parênteses. Você vê que, isso exigiria 4 multiplicações, certo?

00:02:27.486 --> 00:02:33.365
Seria necessário x2 vezes y2, x2 vezes y1, y2 x1 vezes e vezes x1 y1. O que

00:02:33.365 --> 00:02:39.879
Karatsuba percebi é que há uma maneira de fazer essa multiplicação de x por y utilizando apenas

00:02:39.879 --> 00:02:45.847
três multiplicações de x1 x2 y1 y2. Então é só uma multiplicação grande de x vezes y

00:02:45.847 --> 00:02:50.214
leva apenas três multiplicações pequenos. Você pode agora recursivamente

00:02:50.214 --> 00:02:55.087
aplicar exactamente o mesmo procedimento para a multiplicação por x2 y2, e x2 por y1, e assim

00:02:55.087 --> 00:02:59.960
sobre e assim por diante. E você teria este algoritmo recursivo. E se você fizer o

00:02:59.960 --> 00:03:05.087
análise recursiva, você vai ver que, basicamente, você tem um tempo de execução de n para o 1,585.

00:03:05.087 --> 00:03:13.640
Este número é, basicamente, a 1,585 é basicamente, faça de 3 de base 2.

00:03:13.640 --> 00:03:17.836
Surpreendentemente, verifica-se que Karatsuba não é mesmo o melhor de multiplicação

00:03:17.836 --> 00:03:23.912
algoritmo lá fora. Acontece que, na verdade, você pode fazer a multiplicação em cerca de n * log do tempo (n).

00:03:23.912 --> 00:03:28.678
Então você pode fazer a multiplicação quase em tempo linear. No entanto, este é um resultados extremamente assintóticas.

00:03:28.678 --> 00:03:31.477
O O grande aqui esconde constantes muito grandes. E como um

00:03:31.477 --> 00:03:35.452
resultado, este algoritmo só se torna prático quando os números são absolutamente

00:03:35.452 --> 00:03:39.152
enorme. E assim este algoritmo não é realmente usado com muita freqüência. Mas

00:03:39.152 --> 00:03:43.183
algoritmo Karatsuba é muito prático. E na verdade a maioria, cripto-bibliotecas

00:03:43.183 --> 00:03:47.885
implementar algoritmo Karatsuba para multiplicação. No entanto, para simplicidade

00:03:47.885 --> 00:03:51.923
aqui, eu só vou ignorar algoritmo Karatsuba, e apenas para simplificar, eu sou

00:03:51.923 --> 00:03:55.960
vou assumir que a multiplicação é executado em tempo quadrático. Mas em sua mente, você

00:03:55.960 --> 00:03:59.893
deve ser sempre pensando que tudo multiplicação realmente é um pouco mais rápido do que quadrático.

00:03:59.893 --> 00:04:04.794
E então a pergunta seguinte, depois de multiplicação é o que acontece com

00:04:04.794 --> 00:04:10.297
divisão com resto e verifica-se que também é um algoritmo de tempo quadrático.

00:04:10.297 --> 00:04:15.420
Assim, a principal operação que permanece, e que nós usamos muitas vezes até agora, e

00:04:15.420 --> 00:04:20.346
Eu nunca, na verdade, nunca, nunca te disse como realmente computá-lo, isso é

00:04:20.346 --> 00:04:26.339
questão de exponenciação. Então, vamos resolver este problema exponenciação um pouco mais

00:04:26.339 --> 00:04:31.558
abstratamente. Então, imagine que temos um grupo cíclico finito G. Tudo isso significa é que

00:04:31.558 --> 00:04:37.115
este grupo é gerada a partir dos poderes de alguns g gerador pouco. Assim, por exemplo

00:04:37.115 --> 00:04:42.673
pensar desse grupo como simplesmente * ZP, e acho que de g pouco como alguns gerador de

00:04:42.673 --> 00:04:48.886
grande G. A razão que eu estou sentado, desta forma, é que eu sou, eu quero que você começar a se acostumar

00:04:48.886 --> 00:04:54.023
para essa abstração onde lidamos com um genérico grupo G e * ZP é realmente apenas

00:04:54.023 --> 00:04:58.915
um exemplo de um tal grupo. Mas, na verdade, existem muitos outros exemplos de finito

00:04:58.915 --> 00:05:03.379
grupos cíclicos. E novamente eu quero ênfase basicamente que o grupo G, tudo o que

00:05:03.379 --> 00:05:08.087
é, é simplesmente este poderes deste gerador até ao fim do grupo.

00:05:08.087 --> 00:05:15.153
vou escrevê-lo como G para o P. Portanto, nossa meta agora é dado este elemento g, e alguns

00:05:15.153 --> 00:05:20.797
expoente x, nosso objetivo é calcular o valor de g para o x. Agora, normalmente o que você

00:05:20.797 --> 00:05:24.810
diria que é, você pensaria bem, você sabe, se x é igual a 3 então eu sou

00:05:24.810 --> 00:05:28.898
vai computar que você sabe, g em cubos. Bem, não há realmente nada a fazer. Tudo o que faço é

00:05:28.898 --> 00:05:32.795
Eu só faço g vezes g g vezes e eu fico g cubo, que é o que eu queria. Então, isso é

00:05:32.795 --> 00:05:36.790
realmente muito fácil. Mas, na verdade, isso não é o caso que nós estamos interessados dentro Em

00:05:36.790 --> 00:05:40.638
nosso caso, os nossos expoentes vão ser enormes. E então se você tentar, você sabe,

00:05:40.638 --> 00:05:45.644
pensar como um número de 500-bit e por isso, se você tentar calcular g para o poder de um

00:05:45.644 --> 00:05:50.710
número 500-bit simplesmente multiplicando g por g por g por g isso vai levar um bom

00:05:50.710 --> 00:05:55.716
enquanto. Na verdade isso vai levar tempo exponencial que não é algo que queremos

00:05:55.897 --> 00:06:00.722
fazer. Portanto, a questão é se ainda que x é enorme, ainda podemos calcular

00:06:00.722 --> 00:06:05.667
g ao x relativamente rápido ea resposta é sim e o algoritmo que faz isso

00:06:05.667 --> 00:06:10.822
é chamado um algoritmo de quadratura repetida. E então deixe-me mostrar-lhe como repetido

00:06:10.822 --> 00:06:15.593
obras esquadria. Então, vamos tomar como exemplo, de 53 anos. Ingenuamente, você teria que fazer

00:06:15.593 --> 00:06:20.295
53 multiplicações de g por g por g por g até chegar ao g por 53, mas eu quero

00:06:20.295 --> 00:06:25.275
mostrar como você pode fazê-lo muito rapidamente. Então o que vamos fazer é que vou escrever 53 em

00:06:25.275 --> 00:06:30.497
binário. Então aqui é a representação binária de 53. E tudo isso significa

00:06:30.497 --> 00:06:36.282
é, você percebe isso, corresponde a 32, esta corresponde a 16, este

00:06:36.282 --> 00:06:41.292
corresponde a 4, e este corresponde a 1. Então, realmente é 32 53

00:06:41.292 --> 00:06:47.038
mais 16 mais 4 mais 1. Mas o que isto significa é que g ao poder de 53 é

NOTE Paragraph

00:06:47.038 --> 00:06:51.801
g para o poder de 32 16 4 1. E nós podemos quebrar essa para cima, usando mais uma vez, as regras de

00:06:51.801 --> 00:06:57.235
exponenciação. Podemos quebrar isso como g para o g 32 vezes para o g 16 vezes para o

00:06:57.235 --> 00:07:02.938
4 vezes g para o 1, agora que deve começar a dar uma idéia de como calcular g para

00:07:02.938 --> 00:07:07.141
a 53 muito rapidamente. O que vamos fazer é, simplesmente, vamos g e vamos começar

00:07:07.141 --> 00:07:11.459
quadratura-lo. Então, o que quer praça, quer para obter g g quadrado. Nós quadrado novamente para

00:07:11.459 --> 00:07:15.778
obter g para o 4, desligue g para o 8. Ligue g para o 16, g para o 32. Assim

00:07:15.778 --> 00:07:20.607
nós computados todos esses quadrados de g. E agora, o que vamos fazer é que estamos simplesmente

00:07:20.607 --> 00:07:25.719
vai multiplicar os poderes adequados para poder nos dar a g para o 53. Portanto, esta é a g

00:07:25.719 --> 00:07:30.390
os um vezes g às 4 vezes g às 16 vezes g para o 32, é basicamente

00:07:30.390 --> 00:07:35.376
vai nos dar o valor que queremos, que é g para o 53. Então aqui você vê que

00:07:35.376 --> 00:07:40.173
tudo o que tínhamos a fazer era apenas calcular, vamos ver, tivemos que fazer um, dois, três, quatro,

00:07:40.173 --> 00:07:49.343
quadratura cinco, além de quatro multiplicações mais com 9 multiplicações nós computadorizada g

00:07:49.343 --> 00:07:53.726
ao 53. Ok então isso é muito interessante. E acontece que este é um

00:07:53.726 --> 00:07:58.253
fenômenos gerais, que nos permite levantar g de poderes muito, muito altas e fazê-lo muito

00:07:58.253 --> 00:08:02.509
rapidamente. Então deixe-me mostrar-lhe o algoritmo, como eu disse isso é chamado de repetidas

00:08:02.509 --> 00:08:06.497
algoritmo de quadratura. Assim, a entrada para o algoritmo é o elemento g eo

00:08:06.497 --> 00:08:10.858
expoente x. Ea saída é g para o x. Então o que vamos fazer é que nós vamos

00:08:10.858 --> 00:08:15.415
x escrever em notação binária. Então vamos dizer que x tem n bits. E esta é a real

00:08:15.415 --> 00:08:19.521
representação de bits de x como um número binário. E então o que vamos fazer é o

00:08:19.521 --> 00:08:24.246
seguinte. Nós vamos ter estes dois registos. y vai ser um registo que é constantemente

00:08:24.246 --> 00:08:28.127
quadrado. E então z vai ser um acumulador que se multiplica no

00:08:28.127 --> 00:08:32.683
poderes apropriados de g, conforme necessário. Então, tudo o que fazemos é o loop através do seguinte

00:08:32.683 --> 00:08:36.526
bits de x a partir dos bits menos significativos e, então, fazer o

00:08:36.526 --> 00:08:41.414
seguinte: em cada iteração estamos simplesmente indo y quadrado. Ok, então y só continua a

00:08:41.414 --> 00:08:45.940
quadratura a cada iteração. E, em seguida, sempre que o bit correspondente do

00:08:45.940 --> 00:08:50.554
expoente x passa a ser um, simplesmente acumular o valor atual de y em

00:08:50.554 --> 00:08:55.173
este z acumulador e, em seguida, no final, simplesmente saída z. É isso aí. Essa é a

00:08:55.173 --> 00:08:59.558
algoritmo inteiro, e isso é o algoritmo de quadratura repetida. Então, vamos ver um

00:08:59.558 --> 00:09:04.060
exemplo, com o G 53. Assim, você pode ver as duas colunas. y é um

00:09:04.060 --> 00:09:08.387
coluna, à medida que evolui através das iterações, e Z é uma outra coluna, de novo

00:09:08.387 --> 00:09:13.064
à medida que evolui através das iterações. Assim, y não é muito interessante. Basicamente, tudo

00:09:13.064 --> 00:09:17.449
que acontece com y é que a cada iteração, ele simplesmente fica quadrado. E assim

00:09:17.449 --> 00:09:22.299
ele só anda pelas potências de dois e os expoentes e é isso. z é a

00:09:22.299 --> 00:09:26.915
registo mais interessante onde o que ele faz é que acumula o adequado

00:09:26.915 --> 00:09:31.882
poderes de g sempre que o bit correspondente ao expoente é um. Assim, por exemplo o

00:09:31.882 --> 00:09:36.031
primeiro bit do expoente é um, portanto, o, no final do primeiro

00:09:36.031 --> 00:09:41.219
iteração do valor de z é simplesmente igual ao g. O segundo bit do expoente é igual a zero

00:09:41.219 --> 00:09:46.473
para que o valor de z não muda após a segunda iteração. E no final do

00:09:46.473 --> 00:09:51.856
terceira iteração bem o terceiro bit do expoente é um modo que se acumulam ao g

00:09:51.856 --> 00:09:56.662
quarto em z. O próximo bit do expoente é zero para z não muda. O

00:09:56.662 --> 00:10:02.109
próximo bit do expoente é um só e agora nós somos supostos para acumular o anterior

00:10:02.109 --> 00:10:07.491
valor de y na z acumulador então deixe-me perguntar-lhe então o que vai ser o valor de z?

00:10:10.868 --> 00:10:14.245
Bem, nós simplesmente acumular g aos 16 em z e assim nós simplesmente calcular a soma

00:10:14.245 --> 00:10:19.594
, de 16 e 5 g de chegarmos a 21. Finalmente, o último bit é também definido como um

00:10:19.594 --> 00:10:24.943
assim que nós acumulá-lo em z, fazemos 32 mais 21 e ficamos com a saída g, finalmente, para o 53.

00:10:24.943 --> 00:10:30.022
Ok, então isso dá uma idéia de como isso funciona algoritmo repetidas esquadria.

00:10:30.022 --> 00:10:35.777
É um algoritmo é bastante interessante e que nos permite calcular enormes poderes de

00:10:35.777 --> 00:10:41.064
g muito, muito, muito rapidamente. Portanto, o número de iterações aqui, essencialmente, seria

00:10:41.064 --> 00:10:46.456
log base 2 de x. Okay. Você percebe o número de iterações simplesmente depende da

00:10:46.456 --> 00:10:51.954
número de dígitos de x, que é basicamente a base 2 log de x. Assim, mesmo se x é um

00:10:51.954 --> 00:10:56.519
bit número 500 em 500 multiplicação, bem, 500 iterações, realmente 1000

00:10:56.519 --> 00:11:01.736
multiplicações porque temos de conciliar e nós temos que acumular. Assim, em 1000

00:11:01.736 --> 00:11:06.627
multiplicações nós vamos ser capazes de levantar g para a potência de um expoente bit 500.

00:11:06.627 --> 00:11:12.760
tipo Ok então agora podemos resumir os tempos de execução para supor que

00:11:12.760 --> 00:11:17.680
ter um pouco de capital módulo N N como dissemos adição e subtração em ZN leva

00:11:17.680 --> 00:11:22.157
tempo linear. Multiplicação de apenas, você sabe, como eu disse, Karatsuba na verdade torna essa

00:11:22.157 --> 00:11:26.897
mais eficiente, mas para simplificar, vamos apenas dizer que é preciso tempo quadrático. E

00:11:26.897 --> 00:11:31.579
exponenciação, então, como eu disse, basicamente leva log de iterações x, e em cada

00:11:31.579 --> 00:11:35.509
iteração, basicamente, fazer duas multiplicações. Então, é O (log (x))

00:11:35.509 --> 00:11:40.307
vezes o tempo para se multiplicar. E digamos que o tempo para multiplicar é quadrática. Assim

00:11:40.307 --> 00:11:44.758
tempo a execução seria, realmente, N x log quadrados. E desde que x é sempre vou

00:11:44.758 --> 00:11:49.168
ser inferior a N, pelo teorema de Fermat não há nenhum ponto em levantar g para uma potência

00:11:49.168 --> 00:11:53.958
que é maior do que o módulo. Assim x vai ser inferior a N. Vamos supor que x

00:11:53.958 --> 00:11:58.570
também é um número inteiro N-bits, então, realmente exponenciação é um algoritmo de cúbico-tempo.

00:11:58.570 --> 00:12:02.970
Ok é isso que eu queria que você se lembre, que a exponenciação é realmente

00:12:02.970 --> 00:12:07.163
uma relativamente lenta. Esses dias, ele realmente leva alguns microssegundos em um moderno

00:12:07.163 --> 00:12:11.259
computador. Mas ainda assim, microssegundos para um, para uma, digamos, um processador de quatro é gigahertz

00:12:11.259 --> 00:12:15.092
um pouco de trabalho. E assim, basta ter em mente que tudo o exponenciação

00:12:15.092 --> 00:12:19.556
operações que falamos. Por exemplo, para determinar se um número é um quadrática

00:12:19.556 --> 00:12:23.600
resíduo ou não, todos aqueles que, todos aqueles exponenciações, basicamente, ter tempo cúbico.

00:12:24.780 --> 00:12:29.677
Ok, então que completa a nossa discussão de algoritmos aritméticos, e depois na

00:12:29.677 --> 00:12:34.078
próximo segmento nós vamos começar a falar de problemas de disco rígido, modulo, primos e compostos.