[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.22,Default,,0000,0000,0000,,No segmento anterior falamos sobre inversão modular e nós dissemos a Euclides
Dialogue: 0,0:00:04.22,0:00:08.24,Default,,0000,0000,0000,,algoritmo nos dá uma maneira eficiente de encontrar o inverso de um elemento módulo N.
Dialogue: 0,0:00:08.24,0:00:12.26,Default,,0000,0000,0000,,Neste segmento vamos encaminhar através do tempo e vamos passar para
Dialogue: 0,0:00:12.26,0:00:15.87,Default,,0000,0000,0000,,o século XVII e XVIII, onde nós estamos indo falar sobre
Dialogue: 0,0:00:15.87,0:00:19.99,Default,,0000,0000,0000,,Fermat e contribuições de Euler. Antes disso vamos fazer uma rápida revisão de
Dialogue: 0,0:00:19.99,0:00:24.26,Default,,0000,0000,0000,,o que discutimos no segmento anterior. Então, como de costume, eu vou deixar N denotar o
Dialogue: 0,0:00:24.26,0:00:28.43,Default,,0000,0000,0000,,inteiro positivo e vamos apenas dizer que N passa a ser um número inteiro de n bits, em outro
Dialogue: 0,0:00:28.43,0:00:32.44,Default,,0000,0000,0000,,palavras, entre duas a n e dois para o n +1, como de costume vamos deixar que P
Dialogue: 0,0:00:32.44,0:00:36.76,Default,,0000,0000,0000,,denotar um primo. Agora dissemos que ZN é um conjunto de números inteiros de zero
Dialogue: 0,0:00:36.76,0:00:41.37,Default,,0000,0000,0000,,para N-1 e nós dissemos que podemos somar e multiplicar elementos no conjunto de módulo N. Nós
Dialogue: 0,0:00:41.37,0:00:46.19,Default,,0000,0000,0000,,também disse que ZN estrela é basicamente o conjunto de elementos invertíveis em ZN. E nós
Dialogue: 0,0:00:46.19,0:00:51.24,Default,,0000,0000,0000,,provou um lema simples dizer que, X é inversível se e somente se X é relativamente
Dialogue: 0,0:00:51.24,0:00:55.88,Default,,0000,0000,0000,,privilegiada para N. E não só nós entendemos completamente quais são os elementos
Dialogue: 0,0:00:55.88,0:01:00.64,Default,,0000,0000,0000,,e invertíveis que não são, também mostraram um algoritmo muito eficiente com base no
Dialogue: 0,0:01:00.64,0:01:05.57,Default,,0000,0000,0000,,algoritmo estendido de Euclides, para encontrar o inverso de um elemento X na ZN. E nós dissemos
Dialogue: 0,0:01:05.57,0:01:10.39,Default,,0000,0000,0000,,que o tempo de execução deste algoritmo, é basicamente ordem n quadrado, onde
Dialogue: 0,0:01:10.39,0:01:16.11,Default,,0000,0000,0000,,novamente, n é o número de bits do número de capital N. Assim como disse, agora
Dialogue: 0,0:01:16.11,0:01:21.04,Default,,0000,0000,0000,,vamos passar de tempos dos gregos até o fim do século XVII e
Dialogue: 0,0:01:21.04,0:01:26.28,Default,,0000,0000,0000,,falar de Fermat. Assim, Fermat fez uma série de teoremas importantes. O que eu quero
Dialogue: 0,0:01:26.28,0:01:31.21,Default,,0000,0000,0000,,para mostrar aqui hoje é o seguinte. Então, suponhamos que eu lhe dou um p primo, então em
Dialogue: 0,0:01:31.21,0:01:36.26,Default,,0000,0000,0000,,fato, para qualquer elemento X em ZP estrela, acontece que se eu olhar para X e elevá-la
Dialogue: 0,0:01:36.26,0:01:41.13,Default,,0000,0000,0000,,para o poder da P - 1, eu sou um vai pegar um, na ZP. Então, vamos olhar para uma rápida
Dialogue: 0,0:01:41.13,0:01:46.06,Default,,0000,0000,0000,,exemplo. Suponha que eu definir o número de P a ser cinco. E eu olhar, três para o poder de
Dialogue: 0,0:01:46.06,0:01:50.64,Default,,0000,0000,0000,,P-1. Em outras palavras, três à potência de quatro, três à potência de quatro é de 81,
Dialogue: 0,0:01:50.64,0:01:55.29,Default,,0000,0000,0000,,que, na verdade, é um modulo cinco. Este exemplo satisfaz o teorema de Fermat.
Dialogue: 0,0:01:55.29,0:01:59.52,Default,,0000,0000,0000,,Curiosamente, Fermat, na verdade não provar este teorema si mesmo. A prova
Dialogue: 0,0:01:59.52,0:02:04.34,Default,,0000,0000,0000,,realmente esperou até Euler, que provou que quase 100 anos depois. E em
Dialogue: 0,0:02:04.34,0:02:09.12,Default,,0000,0000,0000,,verdade, ele provou ser uma versão muito mais geral deste teorema. Então, vamos olhar para
Dialogue: 0,0:02:09.12,0:02:14.15,Default,,0000,0000,0000,,uma aplicação simples do teorema de Fermat. Suponha que eu olhar para um elemento X em ZP
Dialogue: 0,0:02:14.15,0:02:19.44,Default,,0000,0000,0000,,estrela. E eu quero lembrar aqui que P [inaudível] deve ser um primo. Bem, então o que nós
Dialogue: 0,0:02:19.44,0:02:24.66,Default,,0000,0000,0000,,sabe? Sabemos que X para o P menos um é igual a um. Bem, podemos escrever X para o
Dialogue: 0,0:02:24.66,0:02:29.57,Default,,0000,0000,0000,,P menos um de X vezes X para o poder de P menos dois. Bem agora que sabemos que X
Dialogue: 0,0:02:29.57,0:02:34.09,Default,,0000,0000,0000,,vezes X para o poder de P menos dois acontece ser igual a um. E o que isso
Dialogue: 0,0:02:34.09,0:02:39.31,Default,,0000,0000,0000,,diz, é que realmente o inverso do modulo X P, é simplesmente X para o P menos dois.
Dialogue: 0,0:02:39.31,0:02:44.04,Default,,0000,0000,0000,,Então isso nos dá um outro algoritmo para encontrar o inverso de X modulo um primo.
Dialogue: 0,0:02:44.04,0:02:48.84,Default,,0000,0000,0000,,Basta levantar o X para o poder de p menos dois, e que nos dará o inverso da
Dialogue: 0,0:02:48.84,0:02:53.51,Default,,0000,0000,0000,,x. Acontece que, na verdade, esta é uma boa maneira de calcular o inverso modulo um primo.
Dialogue: 0,0:02:53.51,0:02:58.30,Default,,0000,0000,0000,,Mas tem duas deficiências em comparação com o algoritmo de Euclides. Em primeiro lugar, ela só
Dialogue: 0,0:02:58.30,0:03:02.53,Default,,0000,0000,0000,,primos obras modulo, Considerando que, o algoritmo de Euclides trabalhou modulo compósitos como
Dialogue: 0,0:03:02.53,0:03:07.02,Default,,0000,0000,0000,,bem. E em segundo lugar, verifica-se este algoritmo é na verdade menos eficiente. Quando
Dialogue: 0,0:03:07.02,0:03:10.91,Default,,0000,0000,0000,,falamos sobre como fazer exponenciações modulares - nós estamos indo fazer isso em
Dialogue: 0,0:03:10.91,0:03:15.34,Default,,0000,0000,0000,,o último segmento neste módulo - você verá que o tempo de execução para computar este
Dialogue: 0,0:03:15.34,0:03:19.79,Default,,0000,0000,0000,,exponenciação é realmente cúbico no tamanho P. Então, isso vai levar cerca de login
Dialogue: 0,0:03:19.79,0:03:24.27,Default,,0000,0000,0000,,cubo de P, enquanto que se você se lembra, o algoritmo de Euclides foi capaz de calcular a
Dialogue: 0,0:03:24.27,0:03:30.34,Default,,0000,0000,0000,,inversa no tempo quadrático na representação de P. Então não é só isso
Dialogue: 0,0:03:30.34,0:03:36.51,Default,,0000,0000,0000,,algoritmo menos geral, funciona apenas para números primos, que também é menos eficiente. Então pontuação
Dialogue: 0,0:03:36.51,0:03:41.47,Default,,0000,0000,0000,,um para Euclides. Mas, no entanto, este fato sobre números primos é extremamente importante,
Dialogue: 0,0:03:41.47,0:03:47.51,Default,,0000,0000,0000,,e nós vamos estar fazendo uso extensivo de que no próximo par de semanas. Então deixe-me
Dialogue: 0,0:03:47.51,0:03:52.16,Default,,0000,0000,0000,,mostrar-lhe uma aplicação rápida e simples para o teorema de Fermat vamos supor que queremos
Dialogue: 0,0:03:52.16,0:03:57.23,Default,,0000,0000,0000,,para gerar um primeiro grande acaso, dizer que a nossa principal precisava ser 1.000 bits ou mais. Assim
Dialogue: 0,0:03:57.23,0:04:02.01,Default,,0000,0000,0000,,principal o que estamos procurando é da ordem de dois para o 1024 [inaudível]. Então aqui está
Dialogue: 0,0:04:02.01,0:04:06.72,Default,,0000,0000,0000,,um algoritmo muito simples probabilística. O que nós fazemos é que escolher um
Dialogue: 0,0:04:06.72,0:04:11.94,Default,,0000,0000,0000,,inteiro aleatório no intervalo que foi especificado. E então poderíamos testar se
Dialogue: 0,0:04:12.12,0:04:17.15,Default,,0000,0000,0000,,inteiro ele satisfaz o teorema de Fermat. Em outras palavras, seria testar por exemplo
Dialogue: 0,0:04:17.15,0:04:22.37,Default,,0000,0000,0000,,utilizando a base dois, iríamos testar se os dois para o poder de p menos um é igual a um
Dialogue: 0,0:04:22.37,0:04:27.27,Default,,0000,0000,0000,,em Z p. Se a resposta for não, então se essa igualdade não existe, então sabemos para
Dialogue: 0,0:04:27.27,0:04:33.00,Default,,0000,0000,0000,,certeza de que o número p que escolhemos não é primo. E se isso acontecer, todos nós
Dialogue: 0,0:04:33.00,0:04:37.28,Default,,0000,0000,0000,,fazemos é voltar a um passo e procuramos outro primo. E fazemos isso de novo e
Dialogue: 0,0:04:37.28,0:04:41.78,Default,,0000,0000,0000,,novo e de novo, até que finalmente encontramos um número inteiro que satisfaz essa condição. E
Dialogue: 0,0:04:41.78,0:04:46.01,Default,,0000,0000,0000,,uma vez que encontramos um número inteiro que satisfaz essa condição, simplesmente imprimir-lo e
Dialogue: 0,0:04:46.01,0:04:51.57,Default,,0000,0000,0000,,de paragem. Agora se vê, esta é realmente uma declaração bastante difícil de provar. Mas
Dialogue: 0,0:04:51.57,0:04:56.30,Default,,0000,0000,0000,,acontece se um número aleatório passar este teste, então é extremamente provável que
Dialogue: 0,0:04:56.30,0:05:01.40,Default,,0000,0000,0000,,ser um primo. Em particular, a probabilidade de que P não é um número primo é muito pequena. É
Dialogue: 0,0:05:01.40,0:05:06.19,Default,,0000,0000,0000,,como menos de dois para a -60 para a gama de números de 1024 bits. À medida que o
Dialogue: 0,0:05:06.19,0:05:10.74,Default,,0000,0000,0000,,número fica maior e maior a probabilidade de que ele passa este teste aqui,
Dialogue: 0,0:05:10.74,0:05:15.72,Default,,0000,0000,0000,,mas não é algumas gotas prime para zero muito rapidamente. Portanto, este é realmente um grande
Dialogue: 0,0:05:15.72,0:05:20.46,Default,,0000,0000,0000,,algoritmo interessante. Você percebe que não está garantido que a saída é na verdade
Dialogue: 0,0:05:20.46,0:05:25.02,Default,,0000,0000,0000,,um primo. Tudo o que sabemos é que ele é muito, muito provável que seja um primo. Em outras palavras
Dialogue: 0,0:05:25.02,0:05:29.59,Default,,0000,0000,0000,,, a única maneira que não é um número primo é que temos muito azar. Na verdade isso
Dialogue: 0,0:05:29.59,0:05:34.30,Default,,0000,0000,0000,,sorte que um evento de probabilidade negligenciável aconteceu. Outra forma de dizer
Dialogue: 0,0:05:34.30,0:05:40.23,Default,,0000,0000,0000,,isto é que se você olhar para o conjunto de todos os 1024 números inteiros, então, bem, há o conjunto
Dialogue: 0,0:05:40.23,0:05:45.23,Default,,0000,0000,0000,,dos números primos. Deixe-me escrever aqui primeiro. E depois há um pequeno número de
Dialogue: 0,0:05:45.23,0:05:50.80,Default,,0000,0000,0000,,compósitos. Isso realmente vai falsificar o teste. Vamos chamá-los F para falsos primos.
Dialogue: 0,0:05:50.80,0:05:55.65,Default,,0000,0000,0000,,Vamos chamá-los de FP, para primos falsos. Há um número muito pequeno de compósitos
Dialogue: 0,0:05:55.65,0:06:00.63,Default,,0000,0000,0000,,que não são primos e ainda vai passar este teste. Mas, como escolher inteiros aleatórios,
Dialogue: 0,0:06:00.63,0:06:05.35,Default,,0000,0000,0000,,você sabe, nós escolhemos um aqui, outro aqui, um aqui, e assim por diante, como escolher aleatoriamente
Dialogue: 0,0:06:05.35,0:06:10.26,Default,,0000,0000,0000,,inteiros, a probabilidade de que caem dentro do conjunto de números primos falsos é tão pequena
Dialogue: 0,0:06:10.26,0:06:15.08,Default,,0000,0000,0000,,Isso é, essencialmente, um acontecimento insignificante que podemos ignorar. Em outras palavras, uma
Dialogue: 0,0:06:15.08,0:06:20.59,Default,,0000,0000,0000,,pode provar que o conjunto dos números primos falsas é extremamente pequena, e uma escolha aleatória é
Dialogue: 0,0:06:20.59,0:06:25.27,Default,,0000,0000,0000,,improvável que tal escolher primeiro um falso. Agora eu devo mencionar, na verdade, isso é muito
Dialogue: 0,0:06:25.27,0:06:28.96,Default,,0000,0000,0000,,algoritmo simples para gerar primos. É, na verdade, de longe, não é o melhor
Dialogue: 0,0:06:28.96,0:06:32.65,Default,,0000,0000,0000,,algoritmo. Temos algoritmos muito melhores agora. E, de fato, uma vez que você tem um
Dialogue: 0,0:06:32.65,0:06:36.35,Default,,0000,0000,0000,,principal candidato, agora temos algoritmos muito eficientes que realmente
Dialogue: 0,0:06:36.35,0:06:40.50,Default,,0000,0000,0000,,provar além de qualquer dúvida que este nobre candidato realmente é um primo. Então, nós nem sequer
Dialogue: 0,0:06:40.50,0:06:44.60,Default,,0000,0000,0000,,tem que confiar nas afirmações probabilísticas. Mas, no entanto, este teste é tão Fermat
Dialogue: 0,0:06:44.60,0:06:48.60,Default,,0000,0000,0000,,simples, que eu só queria mostrar-lhe que é uma maneira fácil de gerar números primos.
Dialogue: 0,0:06:48.60,0:06:53.08,Default,,0000,0000,0000,,Embora, na realidade, não é assim que números primos são gerados. Como último ponto,
Dialogue: 0,0:06:53.08,0:06:57.47,Default,,0000,0000,0000,,eu vou dizer que você deve estar se perguntando quantas vezes esta iteração tem de repetir
Dialogue: 0,0:06:57.47,0:07:01.54,Default,,0000,0000,0000,,até realmente encontrar o primo. E isso é realmente um resultado clássico, é
Dialogue: 0,0:07:01.54,0:07:05.82,Default,,0000,0000,0000,,chamado teorema do número primo, que diz que, depois de algumas centenas de iterações,
Dialogue: 0,0:07:05.82,0:07:09.83,Default,,0000,0000,0000,,na verdade, nós vamos encontrar o primeiro com alta probabilidade. Assim, na expectativa, seria
Dialogue: 0,0:07:09.83,0:07:14.77,Default,,0000,0000,0000,,esperar algumas centenas de iterações e nada mais. Agora que entendemos
Dialogue: 0,0:07:14.77,0:07:19.31,Default,,0000,0000,0000,,teorema de Fermat, a próxima coisa que eu quero falar é sobre o que é chamado a
Dialogue: 0,0:07:19.31,0:07:23.92,Default,,0000,0000,0000,,estrutura de ZP estrela. Então, aqui, nós vamos passar de 100 anos no futuro ...
Dialogue: 0,0:07:23.92,0:07:28.58,Default,,0000,0000,0000,,no século XVIII e olhar para o trabalho de Euler. E um dos primeiros
Dialogue: 0,0:07:28.58,0:07:33.12,Default,,0000,0000,0000,,coisas Euler mostrou é em linguagem moderna é que ZP estrela é o que chamamos de
Dialogue: 0,0:07:33.12,0:07:38.01,Default,,0000,0000,0000,,grupo cíclico. O que significa que ZP estrela é um grupo cíclico? O que significa é
Dialogue: 0,0:07:38.01,0:07:42.73,Default,,0000,0000,0000,,que existe algum elemento em G ZP estrela, de tal forma que se tomarmos G e aumentar a
Dialogue: 0,0:07:42.73,0:07:47.68,Default,,0000,0000,0000,,um monte de poderes G, G quadrado, ao cubo G, G para o quarto. E assim por diante e assim por diante até
Dialogue: 0,0:07:47.68,0:07:52.59,Default,,0000,0000,0000,,até chegarmos ao G P menos dois. Observe que não há ponto de ir além G
Dialogue: 0,0:07:52.59,0:07:57.30,Default,,0000,0000,0000,,ao menos duas p, porque G para o p menos um pelo teorema de Fermat é igual para
Dialogue: 0,0:07:57.30,0:08:02.18,Default,,0000,0000,0000,,um, por isso, então vamos voltar ao ciclo de um. Se voltarmos ao G ao menos um p, então G
Dialogue: 0,0:08:02.18,0:08:06.82,Default,,0000,0000,0000,,para a p será igual a G, G para o p, mais uma será igual a G quadrado, e
Dialogue: 0,0:08:06.82,0:08:11.82,Default,,0000,0000,0000,,assim por diante e assim por diante. Então, nós vamos realmente começar um ciclo se continuarmos elevando para mais e
Dialogue: 0,0:08:11.82,0:08:16.59,Default,,0000,0000,0000,,poderes superiores de G. Assim, poderíamos muito bem parar no poder do G para a p menos dois.
Dialogue: 0,0:08:16.59,0:08:21.41,Default,,0000,0000,0000,,E que Euler mostrou é que na verdade não é um elemento G de tal forma que se você
Dialogue: 0,0:08:21.41,0:08:26.30,Default,,0000,0000,0000,,olhada em todos os seus poderes de todos os seus poderes expandir o Estrela ZP todo o grupo.
Dialogue: 0,0:08:26.30,0:08:31.24,Default,,0000,0000,0000,,Os poderes do G nos dá todos os elementos em ZP estrela. Os elementos deste, deste tipo de
Dialogue: 0,0:08:31.24,0:08:35.100,Default,,0000,0000,0000,,é chamado um gerador. Então G seria dito ser um gerador de ZP estrela. Então, vamos
Dialogue: 0,0:08:35.100,0:08:40.70,Default,,0000,0000,0000,,olhar para um exemplo rápido. Então, vamos olhar, por exemplo, em P é igual a sete. E vamos
Dialogue: 0,0:08:40.70,0:08:45.58,Default,,0000,0000,0000,,olhada em todos os poderes de três. Então, três três cubos quadrado, três para o quarto,
Dialogue: 0,0:08:45.58,0:08:50.13,Default,,0000,0000,0000,,três ao quinto, três a seis, já se sabe, é igual a um modular
Dialogue: 0,0:08:50.13,0:08:54.92,Default,,0000,0000,0000,,sete pelo Teorema de Fermat. Então não há nenhum ponto em olhar para três a seis. Nós
Dialogue: 0,0:08:54.92,0:08:59.64,Default,,0000,0000,0000,,sabemos que só iria começar um. Então aqui, eu calculei todos esses poderes para você, e eu
Dialogue: 0,0:08:59.64,0:09:04.43,Default,,0000,0000,0000,,escreveu-los. E você vê que, na verdade, nós temos todos os números [inaudível] em Z,
Dialogue: 0,0:09:04.43,0:09:09.31,Default,,0000,0000,0000,,em Z7 estrela. Em outras palavras, obtemos um, dois, três, quatro, cinco, seis e. Assim
Dialogue: 0,0:09:09.31,0:09:14.60,Default,,0000,0000,0000,,diríamos que três é um gerador de Z7 estrela. Agora gostaria de salientar que não
Dialogue: 0,0:09:14.60,0:09:19.89,Default,,0000,0000,0000,,cada elemento é um gerador. Por exemplo, se olharmos para todas as potências de dois, bem,
Dialogue: 0,0:09:19.89,0:09:24.91,Default,,0000,0000,0000,,isso não vai gerar todo o grupo. Em particular, se olharmos para dois a
Dialogue: 0,0:09:24.91,0:09:29.65,Default,,0000,0000,0000,,zero a, obtemos um. Dois a um, temos dois. Dois ao quadrado é quatro, e duas
Dialogue: 0,0:09:29.65,0:09:34.46,Default,,0000,0000,0000,,ao cubo é de oito, que é um sete modular. Assim pedalamos de volta e, em seguida, dois a
Dialogue: 0,0:09:34.46,0:09:39.77,Default,,0000,0000,0000,,quarta seria dois, dois para o quinto seria quatro. E assim por diante e assim por diante. Assim
Dialogue: 0,0:09:39.77,0:09:44.70,Default,,0000,0000,0000,,, se olharmos para os poderes dos dois, é só pegar um, dois e quatro. Nós não temos a
Dialogue: 0,0:09:44.70,0:09:49.98,Default,,0000,0000,0000,,grupo todo e, portanto, dizemos que dois não é um gerador de Z7 estrela. Agora, novamente,
Dialogue: 0,0:09:49.98,0:09:55.83,Default,,0000,0000,0000,,algo que nós vamos usar muitas vezes é dado um elemento de G * ZP, se olharmos para um
Dialogue: 0,0:09:55.83,0:10:01.90,Default,,0000,0000,0000,,conjunto de todos os poderes de G, o conjunto resultante vai ser chamado o grupo gerado por
Dialogue: 0,0:10:01.90,0:10:06.95,Default,,0000,0000,0000,,G, ok? Então, esses são todos os poderes de G. Eles dão-nos o que é chamado de
Dialogue: 0,0:10:06.95,0:10:12.80,Default,,0000,0000,0000,,grupo multiplicativo. Mais uma vez, o termo técnico não importa. O ponto é que estamos
Dialogue: 0,0:10:12.80,0:10:18.40,Default,,0000,0000,0000,,vai chamar todos estes poderes de G, o grupo gerado por G. De fato há essa
Dialogue: 0,0:10:18.40,0:10:23.57,Default,,0000,0000,0000,,notação que eu não uso com muita frequência, ângulo ângulo G, para designar esse grupo que é
Dialogue: 0,0:10:23.57,0:10:30.01,Default,,0000,0000,0000,,gerada por G. E então nós chamamos a ordem de G em Z p estrela, simplesmente deixe que seja
Dialogue: 0,0:10:30.01,0:10:35.66,Default,,0000,0000,0000,,do tamanho do grupo que é gerado por G. Assim, em outras palavras, a ordem de G em Z
Dialogue: 0,0:10:35.66,0:10:40.63,Default,,0000,0000,0000,,p estrela é o tamanho deste grupo. Mas outra maneira de pensar sobre o que é
Dialogue: 0,0:10:40.63,0:10:46.28,Default,,0000,0000,0000,,basicamente é o menor número inteiro Um tal que G para o A é igual a um no Z P.
Dialogue: 0,0:10:47.38,0:10:52.84,Default,,0000,0000,0000,,razoável, é basicamente o menor de energia que faz com que o poder de G para ser igual à
Dialogue: 0,0:10:52.84,0:10:58.57,Default,,0000,0000,0000,,um. E é muito fácil ver que essa igualdade aqui, basicamente, se olharmos para todos
Dialogue: 0,0:10:58.57,0:11:04.02,Default,,0000,0000,0000,,os poderes de G e olhamos para um, G, G quadrado, G em cubos e assim por diante e assim por diante até
Dialogue: 0,0:11:04.02,0:11:09.89,Default,,0000,0000,0000,,até chegarmos ao G com a ordem de G menos um. E então se olharmos para a ordem de G
Dialogue: 0,0:11:09.89,0:11:15.42,Default,,0000,0000,0000,,com a ordem de G. Esta coisa é simplesmente vai ser igual a um, por definição.
Dialogue: 0,0:11:16.08,0:11:22.00,Default,,0000,0000,0000,,Ok, então não há nenhum ponto em olhar todas as potências mais elevadas. Nós pode muito bem
Dialogue: 0,0:11:22.00,0:11:27.63,Default,,0000,0000,0000,,parar de aumentar os poderes aqui. E, como resultado do tamanho do conjunto, na verdade, é
Dialogue: 0,0:11:27.63,0:11:33.26,Default,,0000,0000,0000,,a ordem de G. E você pode ver que a ordem é o menor poder de tal forma que
Dialogue: 0,0:11:33.26,0:11:38.93,Default,,0000,0000,0000,,G elevando para que o poder dá-nos um em Z p. Então eu espero que isso está claro, embora
Dialogue: 0,0:11:38.93,0:11:43.46,Default,,0000,0000,0000,,pode levar um pouco de pensar para absorver toda esta notação. Mas no
Dialogue: 0,0:11:43.46,0:11:48.10,Default,,0000,0000,0000,,Enquanto isso vamos olhar para alguns exemplos. Então, novamente, vamos fixar a nossa, a nossa principal a ser
Dialogue: 0,0:11:48.10,0:11:52.99,Default,,0000,0000,0000,,sete. E vamos olhar para a ordem do número de elementos. Então, qual é a ordem
Dialogue: 0,0:11:52.99,0:11:57.75,Default,,0000,0000,0000,,de três módulo de sete? Bem, nós estamos perguntando o que é o tamanho do grupo que
Dialogue: 0,0:11:57.75,0:12:02.76,Default,,0000,0000,0000,,três gera módulo de sete? Bem, nós dissemos que três é um gerador de Z7 estrela.
Dialogue: 0,0:12:02.76,0:12:07.70,Default,,0000,0000,0000,,Então ele gera todos Z7 estrela. Há seis elementos em Z7 estrela. E, portanto,
Dialogue: 0,0:12:07.70,0:12:12.76,Default,,0000,0000,0000,,dizer que a ordem de três é igual a seis. Da mesma forma, eu posso perguntar, bem, o que é
Dialogue: 0,0:12:12.76,0:12:17.42,Default,,0000,0000,0000,,fim de dois modulo sete? E, de fato, já vimos a resposta. Então vamos,
Dialogue: 0,0:12:17.42,0:12:22.08,Default,,0000,0000,0000,,eu vou lhe perguntar, qual é a ordem de dois modulo sete e veja se você consegue f igura
Dialogue: 0,0:12:22.08,0:12:28.55,Default,,0000,0000,0000,,o que esta resposta é. Portanto, a resposta é de três e mais uma vez, a razão é, se olharmos
Dialogue: 0,0:12:28.55,0:12:33.62,Default,,0000,0000,0000,,no conjunto de potências de dois modulo sete, temos um, dois, dois quadrado e, em seguida
Dialogue: 0,0:12:33.62,0:12:39.08,Default,,0000,0000,0000,,cubado dois já é igual a um. Portanto, este é todo o conjunto de potências de dois modulo
Dialogue: 0,0:12:39.08,0:12:44.21,Default,,0000,0000,0000,,sete. Existem apenas três deles e, portanto, da ordem de dois modulo sete
Dialogue: 0,0:12:44.21,0:12:49.22,Default,,0000,0000,0000,,é exatamente três. Agora deixe-me lhe fazer uma pergunta capciosa. Qual é a ordem de um
Dialogue: 0,0:12:49.22,0:12:54.50,Default,,0000,0000,0000,,modulo sete? Bem, a resposta é uma só. Porque se você olhar para o grupo que é
Dialogue: 0,0:12:54.50,0:12:58.63,Default,,0000,0000,0000,,gerada por um, bem, há apenas um número em que o grupo, ou seja, o número
Dialogue: 0,0:12:58.63,0:13:02.61,Default,,0000,0000,0000,,um. Se eu levantar um a um monte de poderes, eu sempre vou ter um, E
Dialogue: 0,0:13:02.61,0:13:07.06,Default,,0000,0000,0000,,, portanto, a ordem de 1 modulo 7 Na verdade, a ordem de 1 modulo qualquer injeção
Dialogue: 0,0:13:07.06,0:13:12.52,Default,,0000,0000,0000,,é sempre vai ser 1. Agora há um importante teorema de Lagrange, que
Dialogue: 0,0:13:12.52,0:13:17.14,Default,,0000,0000,0000,,realmente este é um caso muito, muito especial dele, o que estou afirmando aqui. Mas
Dialogue: 0,0:13:17.14,0:13:22.31,Default,,0000,0000,0000,,teorema de Langrage basicamente implica que, se você olhar para a ordem de G módulo p,
Dialogue: 0,0:13:22.31,0:13:27.11,Default,,0000,0000,0000,,ordem sempre vai dividir P-1. Assim, em nosso exemplo dois você vê,
Dialogue: 0,0:13:27.30,0:13:32.10,Default,,0000,0000,0000,,seis divide sete menos um, seis divide seis, e, similarmente, três divide sete
Dialogue: 0,0:13:32.10,0:13:37.03,Default,,0000,0000,0000,,menos um. Nomeadamente novamente três divide seis. Mas isso é muito geral, o seu fim é
Dialogue: 0,0:13:37.03,0:13:41.33,Default,,0000,0000,0000,,sempre vai ser um fator de P menos um. Na verdade, eu vou te dizer, talvez seja uma
Dialogue: 0,0:13:41.33,0:13:45.18,Default,,0000,0000,0000,,quebra-cabeças para você pensar. É realmente muito fácil deduzir de Fermat
Dialogue: 0,0:13:45.18,0:13:49.18,Default,,0000,0000,0000,,teorema directamente a partir deste fato, a partir do teorema de Lagrange esta de fato. E assim
Dialogue: 0,0:13:49.18,0:13:53.34,Default,,0000,0000,0000,,teorema de Fermat realmente em certo sentido, segue-se diretamente do teorema de Lagrange.
Dialogue: 0,0:13:54.58,0:13:59.38,Default,,0000,0000,0000,,Lagrange, a propósito, que o seu trabalho no século XIX, assim você já pode ver
Dialogue: 0,0:13:59.38,0:14:04.05,Default,,0000,0000,0000,,como estamos a fazer progressos ao longo do tempo. Começamos em tempos gregos, e já que
Dialogue: 0,0:14:04.05,0:14:09.38,Default,,0000,0000,0000,,acabou no século XIX. E eu posso te dizer que a criptografia mais avançada
Dialogue: 0,0:14:09.38,0:14:14.02,Default,,0000,0000,0000,,realmente usa a matemática do século XX é bastante extensa. Agora que entendemos o
Dialogue: 0,0:14:14.02,0:14:18.42,Default,,0000,0000,0000,,estrutura de ZP estrela, vamos generalizar que a compósitos, e olhar para o
Dialogue: 0,0:14:18.42,0:14:23.47,Default,,0000,0000,0000,,estrutura da ZN estrela. Então o que eu quero mostrar aqui é que é chamado Teorema de Euler
Dialogue: 0,0:14:23.47,0:14:28.04,Default,,0000,0000,0000,,, que é uma, uma generalização direta do Teorema de Fermat. Assim, Euler definido o
Dialogue: 0,0:14:28.04,0:14:32.98,Default,,0000,0000,0000,,seguinte função. Portanto, dado um número inteiro N, ele definiu o que é chamado de phi
Dialogue: 0,0:14:32.98,0:14:37.19,Default,,0000,0000,0000,,função, phi de M, a ser basicamente o tamanho do conjunto ZN estrela.
Dialogue: 0,0:14:37.19,0:14:42.69,Default,,0000,0000,0000,,Isso às vezes é chamado, a função de Euler phi. O tamanho do conjunto ZN estrela. Assim
Dialogue: 0,0:14:42.69,0:14:48.52,Default,,0000,0000,0000,,por exemplo, que já olhou Z estrela de doze. Dissemos que Z contém 12 estrelas
Dialogue: 0,0:14:48.52,0:14:53.88,Default,,0000,0000,0000,,estes quatro elementos, um, cinco, sete e onze anos. E por isso dizemos que phi de
Dialogue: 0,0:14:53.88,0:14:59.31,Default,,0000,0000,0000,,12 é simplesmente o número quatro. Então deixe-me perguntar-lhe como um quebra-cabeça, o que é phi de P?
Dialogue: 0,0:14:59.31,0:15:06.27,Default,,0000,0000,0000,,Ela vai ser basicamente o tamanho de ZP estrela. E assim, de fato, dissemos que na ZP
Dialogue: 0,0:15:06.27,0:15:12.34,Default,,0000,0000,0000,,estrela contém todos ZP, exceto para o número zero. E, portanto, phi de P para
Dialogue: 0,0:15:12.34,0:15:18.53,Default,,0000,0000,0000,,qualquer P principal vai ser P menos um. Agora, há um caso especial, que eu vou
Dialogue: 0,0:15:18.53,0:15:23.28,Default,,0000,0000,0000,,estado aqui e nós vamos usar mais tarde para o sistema RSA. Se N passa a ser um
Dialogue: 0,0:15:23.28,0:15:28.28,Default,,0000,0000,0000,,produto de dois primos, então phi de N é simplesmente menos N P Q menos mais um. E deixe-
Dialogue: 0,0:15:28.28,0:15:33.04,Default,,0000,0000,0000,,me mostrar por que isso é verdade. Então, basicamente, N é o tamanho do Z N. E agora nós
Dialogue: 0,0:15:33.04,0:15:37.84,Default,,0000,0000,0000,,necessário remover todos os elementos que não são relativamente primos com m. Bem como pode um
Dialogue: 0,0:15:37.84,0:15:42.63,Default,,0000,0000,0000,,elemento não ser relativamente primos para m? Tem que ser divisível por p, ou que tem que ser
Dialogue: 0,0:15:42.63,0:15:47.08,Default,,0000,0000,0000,,divisível por q. Bem, como muitos elementos entre zero e menos um m estão lá,
Dialogue: 0,0:15:47.08,0:15:51.76,Default,,0000,0000,0000,,lá que são divisíveis por p? Bem, existem exatamente q deles. Quantos elementos
Dialogue: 0,0:15:51.76,0:15:55.97,Default,,0000,0000,0000,,existem que são divisíveis por q. Bem, existem exatamente p deles. Então, nós
Dialogue: 0,0:15:55.97,0:16:00.59,Default,,0000,0000,0000,,subtrair p se livrar daqueles divisível por q. Nós subtrair q se livrar daqueles
Dialogue: 0,0:16:00.59,0:16:05.78,Default,,0000,0000,0000,,divisível por p. E você percebe que subtraído de zero duas vezes, porque zero é
Dialogue: 0,0:16:05.78,0:16:12.02,Default,,0000,0000,0000,,divisível tanto por P e Q. E, portanto, nós adicionamos um apenas para ter certeza de que subtrair
Dialogue: 0,0:16:12.02,0:16:18.26,Default,,0000,0000,0000,,zero apenas uma vez. E por isso não é difícil ver que phi (N) é NP-Q +1. E uma outra maneira
Dialogue: 0,0:16:18.26,0:16:24.60,Default,,0000,0000,0000,,de escrita que é simplesmente (P-1) vezes (Q-1). Ok, então isso é um fato que usaremos mais tarde
Dialogue: 0,0:16:24.60,0:16:30.28,Default,,0000,0000,0000,,, quando voltamos e falar sobre o sistema RSA. Até agora, esta é apenas a definição de
Dialogue: 0,0:16:30.28,0:16:35.69,Default,,0000,0000,0000,,esta função phi de Euler. Mas agora Euler colocar esta função phi de uso muito bom.
Dialogue: 0,0:16:35.69,0:16:41.10,Default,,0000,0000,0000,,E o que ele provou este fato maravilhoso aqui que diz basicamente que se você der
Dialogue: 0,0:16:41.10,0:16:46.06,Default,,0000,0000,0000,,me qualquer elemento X na ZN estrela. Na verdade, e acontece que X ao poder de phi (N)
Dialogue: 0,0:16:46.06,0:16:50.68,Default,,0000,0000,0000,,é igual a um em Z N. Assim, você pode ver que isso é uma generalização de Fermat
Dialogue: 0,0:16:50.68,0:16:55.24,Default,,0000,0000,0000,,teorema, em particular, o teorema de Fermat só é aplicado a números primos. Para primos que conhecemos
Dialogue: 0,0:16:55.24,0:16:59.91,Default,,0000,0000,0000,,que phi (p) é igual a p menos um, e, em outras palavras, se fosse primeiro-N faríamos
Dialogue: 0,0:16:59.91,0:17:04.49,Default,,0000,0000,0000,,simplesmente escrever p menos um aqui, e então nós teríamos exatamente o teorema de Fermat. O
Dialogue: 0,0:17:04.49,0:17:08.89,Default,,0000,0000,0000,,beleza do teorema de Euler é que se aplica a materiais compósitos, e não apenas
Dialogue: 0,0:17:08.89,0:17:16.46,Default,,0000,0000,0000,,primos. Então, vamos olhar para alguns exemplos. Então, vamos olhar para cinco o poder de phi (12).
Dialogue: 0,0:17:16.46,0:17:21.74,Default,,0000,0000,0000,,Assim, cinco é um elemento de Z12 estrela. Se aumentá-lo para o poder de cinco dos
Dialogue: 0,0:17:21.74,0:17:27.16,Default,,0000,0000,0000,,12, que deve estar recebendo uma. Bem, sabemos que phi (12) é de 4, então estamos
Dialogue: 0,0:17:27.16,0:17:32.04,Default,,0000,0000,0000,,levantando 5 à potência de 4. Cinco para o poder de quatro é de 625 e é um simples
Dialogue: 0,0:17:32.04,0:17:36.23,Default,,0000,0000,0000,,cálculo para mostrar que isso é igual a 1 módulo 12. Então esta é a prova
Dialogue: 0,0:17:36.23,0:17:40.47,Default,,0000,0000,0000,,por exemplo, mas é claro que não é uma prova em tudo. É apenas um exemplo. Mas, na verdade
Dialogue: 0,0:17:40.47,0:17:44.56,Default,,0000,0000,0000,,não é difícil de provar o teorema de Euler e na verdade eu vou dizer-lhe que
Dialogue: 0,0:17:44.56,0:17:48.90,Default,,0000,0000,0000,,teorema de Euler é também um caso muito especial do teorema geral de Lagrange.
Dialogue: 0,0:17:49.88,0:17:53.89,Default,,0000,0000,0000,,Ok então dizemos que esta é uma generalização do teorema de Fermat e
Dialogue: 0,0:17:53.89,0:17:58.23,Default,,0000,0000,0000,,, de fato, como veremos este teorema de Euler é a base da criptografia RSA
Dialogue: 0,0:17:58.23,0:18:03.92,Default,,0000,0000,0000,,sistema. Então eu parar por aqui e vamos continuar com modulares equações quadráticas na
Dialogue: 0,0:18:03.92,0:18:04.74,Default,,0000,0000,0000,,próximo segmento.