WEBVTT

00:00:00.000 --> 00:00:04.220
No segmento anterior falamos sobre inversão modular e nós dissemos a Euclides

00:00:04.220 --> 00:00:08.238
algoritmo nos dá uma maneira eficiente de encontrar o inverso de um elemento módulo N.

00:00:08.238 --> 00:00:12.256
Neste segmento vamos encaminhar através do tempo e vamos passar para

00:00:12.256 --> 00:00:15.866
o século XVII e XVIII, onde nós estamos indo falar sobre

00:00:15.866 --> 00:00:19.986
Fermat e contribuições de Euler. Antes disso vamos fazer uma rápida revisão de

00:00:19.986 --> 00:00:24.257
o que discutimos no segmento anterior. Então, como de costume, eu vou deixar N denotar o

00:00:24.257 --> 00:00:28.427
inteiro positivo e vamos apenas dizer que N passa a ser um número inteiro de n bits, em outro

00:00:28.427 --> 00:00:32.445
palavras, entre duas a n e dois para o n +1, como de costume vamos deixar que P

00:00:32.445 --> 00:00:36.761
denotar um primo. Agora dissemos que ZN é um conjunto de números inteiros de zero

00:00:36.761 --> 00:00:41.370
para N-1 e nós dissemos que podemos somar e multiplicar elementos no conjunto de módulo N. Nós

00:00:41.370 --> 00:00:46.186
também disse que ZN estrela é basicamente o conjunto de elementos invertíveis em ZN. E nós

00:00:46.186 --> 00:00:51.243
provou um lema simples dizer que, X é inversível se e somente se X é relativamente

00:00:51.243 --> 00:00:55.879
privilegiada para N. E não só nós entendemos completamente quais são os elementos

00:00:55.879 --> 00:01:00.635
e invertíveis que não são, também mostraram um algoritmo muito eficiente com base no

00:01:00.635 --> 00:01:05.572
algoritmo estendido de Euclides, para encontrar o inverso de um elemento X na ZN. E nós dissemos

00:01:05.572 --> 00:01:10.388
que o tempo de execução deste algoritmo, é basicamente ordem n quadrado, onde

00:01:10.388 --> 00:01:16.107
novamente, n é o número de bits do número de capital N. Assim como disse, agora

00:01:16.107 --> 00:01:21.037
vamos passar de tempos dos gregos até o fim do século XVII e

00:01:21.037 --> 00:01:26.276
falar de Fermat. Assim, Fermat fez uma série de teoremas importantes. O que eu quero

00:01:26.276 --> 00:01:31.206
para mostrar aqui hoje é o seguinte. Então, suponhamos que eu lhe dou um p primo, então em

00:01:31.206 --> 00:01:36.260
fato, para qualquer elemento X em ZP estrela, acontece que se eu olhar para X e elevá-la

00:01:36.260 --> 00:01:41.130
para o poder da P - 1, eu sou um vai pegar um, na ZP. Então, vamos olhar para uma rápida

00:01:41.130 --> 00:01:46.061
exemplo. Suponha que eu definir o número de P a ser cinco. E eu olhar, três para o poder de

00:01:46.061 --> 00:01:50.645
P-1. Em outras palavras, três à potência de quatro, três à potência de quatro é de 81,

00:01:50.645 --> 00:01:55.286
que, na verdade, é um modulo cinco. Este exemplo satisfaz o teorema de Fermat.

00:01:55.286 --> 00:01:59.521
Curiosamente, Fermat, na verdade não provar este teorema si mesmo. A prova

00:01:59.521 --> 00:02:04.337
realmente esperou até Euler, que provou que quase 100 anos depois. E em

00:02:04.337 --> 00:02:09.122
verdade, ele provou ser uma versão muito mais geral deste teorema. Então, vamos olhar para

00:02:09.122 --> 00:02:14.154
uma aplicação simples do teorema de Fermat. Suponha que eu olhar para um elemento X em ZP

00:02:14.154 --> 00:02:19.441
estrela. E eu quero lembrar aqui que P [inaudível] deve ser um primo. Bem, então o que nós

00:02:19.441 --> 00:02:24.664
sabe? Sabemos que X para o P menos um é igual a um. Bem, podemos escrever X para o

00:02:24.664 --> 00:02:29.573
P menos um de X vezes X para o poder de P menos dois. Bem agora que sabemos que X

00:02:29.573 --> 00:02:34.087
vezes X para o poder de P menos dois acontece ser igual a um. E o que isso

00:02:34.087 --> 00:02:39.310
diz, é que realmente o inverso do modulo X P, é simplesmente X para o P menos dois.

00:02:39.310 --> 00:02:44.042
Então isso nos dá um outro algoritmo para encontrar o inverso de X modulo um primo.

00:02:44.042 --> 00:02:48.835
Basta levantar o X para o poder de p menos dois, e que nos dará o inverso da

00:02:48.835 --> 00:02:53.508
x. Acontece que, na verdade, esta é uma boa maneira de calcular o inverso modulo um primo.

00:02:53.508 --> 00:02:58.301
Mas tem duas deficiências em comparação com o algoritmo de Euclides. Em primeiro lugar, ela só

00:02:58.301 --> 00:03:02.528
primos obras modulo, Considerando que, o algoritmo de Euclides trabalhou modulo compósitos como

00:03:02.528 --> 00:03:07.017
bem. E em segundo lugar, verifica-se este algoritmo é na verdade menos eficiente. Quando

00:03:07.017 --> 00:03:10.911
falamos sobre como fazer exponenciações modulares - nós estamos indo fazer isso em

00:03:10.911 --> 00:03:15.345
o último segmento neste módulo - você verá que o tempo de execução para computar este

00:03:15.345 --> 00:03:19.792
exponenciação é realmente cúbico no tamanho P. Então, isso vai levar cerca de login

00:03:19.792 --> 00:03:24.266
cubo de P, enquanto que se você se lembra, o algoritmo de Euclides foi capaz de calcular a

00:03:24.266 --> 00:03:30.343
inversa no tempo quadrático na representação de P. Então não é só isso

00:03:30.343 --> 00:03:36.512
algoritmo menos geral, funciona apenas para números primos, que também é menos eficiente. Então pontuação

00:03:36.512 --> 00:03:41.473
um para Euclides. Mas, no entanto, este fato sobre números primos é extremamente importante,

00:03:41.473 --> 00:03:47.506
e nós vamos estar fazendo uso extensivo de que no próximo par de semanas. Então deixe-me

00:03:47.506 --> 00:03:52.155
mostrar-lhe uma aplicação rápida e simples para o teorema de Fermat vamos supor que queremos

00:03:52.155 --> 00:03:57.226
para gerar um primeiro grande acaso, dizer que a nossa principal precisava ser 1.000 bits ou mais. Assim

00:03:57.226 --> 00:04:02.006
principal o que estamos procurando é da ordem de dois para o 1024 [inaudível]. Então aqui está

00:04:02.006 --> 00:04:06.724
um algoritmo muito simples probabilística. O que nós fazemos é que escolher um

00:04:06.724 --> 00:04:11.938
inteiro aleatório no intervalo que foi especificado. E então poderíamos testar se

00:04:12.124 --> 00:04:17.153
inteiro ele satisfaz o teorema de Fermat. Em outras palavras, seria testar por exemplo

00:04:17.153 --> 00:04:22.367
utilizando a base dois, iríamos testar se os dois para o poder de p menos um é igual a um

00:04:22.367 --> 00:04:27.271
em Z p. Se a resposta for não, então se essa igualdade não existe, então sabemos para

00:04:27.271 --> 00:04:33.003
certeza de que o número p que escolhemos não é primo. E se isso acontecer, todos nós

00:04:33.003 --> 00:04:37.284
fazemos é voltar a um passo e procuramos outro primo. E fazemos isso de novo e

00:04:37.284 --> 00:04:41.782
novo e de novo, até que finalmente encontramos um número inteiro que satisfaz essa condição. E

00:04:41.782 --> 00:04:46.009
uma vez que encontramos um número inteiro que satisfaz essa condição, simplesmente imprimir-lo e

00:04:46.009 --> 00:04:51.573
de paragem. Agora se vê, esta é realmente uma declaração bastante difícil de provar. Mas

00:04:51.573 --> 00:04:56.305
acontece se um número aleatório passar este teste, então é extremamente provável que

00:04:56.305 --> 00:05:01.398
ser um primo. Em particular, a probabilidade de que P não é um número primo é muito pequena. É

00:05:01.398 --> 00:05:06.191
como menos de dois para a -60 para a gama de números de 1024 bits. À medida que o

00:05:06.191 --> 00:05:10.744
número fica maior e maior a probabilidade de que ele passa este teste aqui,

00:05:10.744 --> 00:05:15.716
mas não é algumas gotas prime para zero muito rapidamente. Portanto, este é realmente um grande

00:05:15.716 --> 00:05:20.455
algoritmo interessante. Você percebe que não está garantido que a saída é na verdade

00:05:20.455 --> 00:05:25.021
um primo. Tudo o que sabemos é que ele é muito, muito provável que seja um primo. Em outras palavras

00:05:25.021 --> 00:05:29.587
, a única maneira que não é um número primo é que temos muito azar. Na verdade isso

00:05:29.587 --> 00:05:34.298
sorte que um evento de probabilidade negligenciável aconteceu. Outra forma de dizer

00:05:34.298 --> 00:05:40.230
isto é que se você olhar para o conjunto de todos os 1024 números inteiros, então, bem, há o conjunto

00:05:40.230 --> 00:05:45.233
dos números primos. Deixe-me escrever aqui primeiro. E depois há um pequeno número de

00:05:45.233 --> 00:05:50.805
compósitos. Isso realmente vai falsificar o teste. Vamos chamá-los F para falsos primos.

00:05:50.805 --> 00:05:55.653
Vamos chamá-los de FP, para primos falsos. Há um número muito pequeno de compósitos

00:05:55.653 --> 00:06:00.626
que não são primos e ainda vai passar este teste. Mas, como escolher inteiros aleatórios,

00:06:00.626 --> 00:06:05.349
você sabe, nós escolhemos um aqui, outro aqui, um aqui, e assim por diante, como escolher aleatoriamente

00:06:05.349 --> 00:06:10.260
inteiros, a probabilidade de que caem dentro do conjunto de números primos falsos é tão pequena

00:06:10.260 --> 00:06:15.082
Isso é, essencialmente, um acontecimento insignificante que podemos ignorar. Em outras palavras, uma

00:06:15.082 --> 00:06:20.591
pode provar que o conjunto dos números primos falsas é extremamente pequena, e uma escolha aleatória é

00:06:20.591 --> 00:06:25.266
improvável que tal escolher primeiro um falso. Agora eu devo mencionar, na verdade, isso é muito

00:06:25.266 --> 00:06:28.960
algoritmo simples para gerar primos. É, na verdade, de longe, não é o melhor

00:06:28.960 --> 00:06:32.654
algoritmo. Temos algoritmos muito melhores agora. E, de fato, uma vez que você tem um

00:06:32.654 --> 00:06:36.349
principal candidato, agora temos algoritmos muito eficientes que realmente

00:06:36.349 --> 00:06:40.498
provar além de qualquer dúvida que este nobre candidato realmente é um primo. Então, nós nem sequer

00:06:40.498 --> 00:06:44.597
tem que confiar nas afirmações probabilísticas. Mas, no entanto, este teste é tão Fermat

00:06:44.597 --> 00:06:48.595
simples, que eu só queria mostrar-lhe que é uma maneira fácil de gerar números primos.

00:06:48.595 --> 00:06:53.076
Embora, na realidade, não é assim que números primos são gerados. Como último ponto,

00:06:53.076 --> 00:06:57.468
eu vou dizer que você deve estar se perguntando quantas vezes esta iteração tem de repetir

00:06:57.468 --> 00:07:01.536
até realmente encontrar o primo. E isso é realmente um resultado clássico, é

00:07:01.536 --> 00:07:05.820
chamado teorema do número primo, que diz que, depois de algumas centenas de iterações,

00:07:05.820 --> 00:07:09.833
na verdade, nós vamos encontrar o primeiro com alta probabilidade. Assim, na expectativa, seria

00:07:09.833 --> 00:07:14.771
esperar algumas centenas de iterações e nada mais. Agora que entendemos

00:07:14.771 --> 00:07:19.314
teorema de Fermat, a próxima coisa que eu quero falar é sobre o que é chamado a

00:07:19.314 --> 00:07:23.915
estrutura de ZP estrela. Então, aqui, nós vamos passar de 100 anos no futuro ...

00:07:23.915 --> 00:07:28.576
no século XVIII e olhar para o trabalho de Euler. E um dos primeiros

00:07:28.576 --> 00:07:33.118
coisas Euler mostrou é em linguagem moderna é que ZP estrela é o que chamamos de

00:07:33.118 --> 00:07:38.014
grupo cíclico. O que significa que ZP estrela é um grupo cíclico? O que significa é

00:07:38.014 --> 00:07:42.734
que existe algum elemento em G ZP estrela, de tal forma que se tomarmos G e aumentar a

00:07:42.734 --> 00:07:47.681
um monte de poderes G, G quadrado, ao cubo G, G para o quarto. E assim por diante e assim por diante até

00:07:47.681 --> 00:07:52.590
até chegarmos ao G P menos dois. Observe que não há ponto de ir além G

00:07:52.590 --> 00:07:57.296
ao menos duas p, porque G para o p menos um pelo teorema de Fermat é igual para

00:07:57.296 --> 00:08:02.178
um, por isso, então vamos voltar ao ciclo de um. Se voltarmos ao G ao menos um p, então G

00:08:02.178 --> 00:08:06.825
para a p será igual a G, G para o p, mais uma será igual a G quadrado, e

00:08:06.825 --> 00:08:11.825
assim por diante e assim por diante. Então, nós vamos realmente começar um ciclo se continuarmos elevando para mais e

00:08:11.825 --> 00:08:16.590
poderes superiores de G. Assim, poderíamos muito bem parar no poder do G para a p menos dois.

00:08:16.590 --> 00:08:21.413
E que Euler mostrou é que na verdade não é um elemento G de tal forma que se você

00:08:21.413 --> 00:08:26.300
olhada em todos os seus poderes de todos os seus poderes expandir o Estrela ZP todo o grupo.

00:08:26.300 --> 00:08:31.239
Os poderes do G nos dá todos os elementos em ZP estrela. Os elementos deste, deste tipo de

00:08:31.239 --> 00:08:35.997
é chamado um gerador. Então G seria dito ser um gerador de ZP estrela. Então, vamos

00:08:35.997 --> 00:08:40.696
olhar para um exemplo rápido. Então, vamos olhar, por exemplo, em P é igual a sete. E vamos

00:08:40.696 --> 00:08:45.575
olhada em todos os poderes de três. Então, três três cubos quadrado, três para o quarto,

00:08:45.575 --> 00:08:50.130
três ao quinto, três a seis, já se sabe, é igual a um modular

00:08:50.130 --> 00:08:54.917
sete pelo Teorema de Fermat. Então não há nenhum ponto em olhar para três a seis. Nós

00:08:54.917 --> 00:08:59.644
sabemos que só iria começar um. Então aqui, eu calculei todos esses poderes para você, e eu

00:08:59.644 --> 00:09:04.431
escreveu-los. E você vê que, na verdade, nós temos todos os números [inaudível] em Z,

00:09:04.431 --> 00:09:09.313
em Z7 estrela. Em outras palavras, obtemos um, dois, três, quatro, cinco, seis e. Assim

00:09:09.313 --> 00:09:14.599
diríamos que três é um gerador de Z7 estrela. Agora gostaria de salientar que não

00:09:14.599 --> 00:09:19.886
cada elemento é um gerador. Por exemplo, se olharmos para todas as potências de dois, bem,

00:09:19.886 --> 00:09:24.914
isso não vai gerar todo o grupo. Em particular, se olharmos para dois a

00:09:24.914 --> 00:09:29.650
zero a, obtemos um. Dois a um, temos dois. Dois ao quadrado é quatro, e duas

00:09:29.650 --> 00:09:34.455
ao cubo é de oito, que é um sete modular. Assim pedalamos de volta e, em seguida, dois a

00:09:34.455 --> 00:09:39.766
quarta seria dois, dois para o quinto seria quatro. E assim por diante e assim por diante. Assim

00:09:39.766 --> 00:09:44.697
, se olharmos para os poderes dos dois, é só pegar um, dois e quatro. Nós não temos a

00:09:44.697 --> 00:09:49.981
grupo todo e, portanto, dizemos que dois não é um gerador de Z7 estrela. Agora, novamente,

00:09:49.981 --> 00:09:55.831
algo que nós vamos usar muitas vezes é dado um elemento de G * ZP, se olharmos para um

00:09:55.831 --> 00:10:01.901
conjunto de todos os poderes de G, o conjunto resultante vai ser chamado o grupo gerado por

00:10:01.901 --> 00:10:06.947
G, ok? Então, esses são todos os poderes de G. Eles dão-nos o que é chamado de

00:10:06.947 --> 00:10:12.798
grupo multiplicativo. Mais uma vez, o termo técnico não importa. O ponto é que estamos

00:10:12.798 --> 00:10:18.397
vai chamar todos estes poderes de G, o grupo gerado por G. De fato há essa

00:10:18.397 --> 00:10:23.570
notação que eu não uso com muita frequência, ângulo ângulo G, para designar esse grupo que é

00:10:23.570 --> 00:10:30.010
gerada por G. E então nós chamamos a ordem de G em Z p estrela, simplesmente deixe que seja

00:10:30.010 --> 00:10:35.663
do tamanho do grupo que é gerado por G. Assim, em outras palavras, a ordem de G em Z

00:10:35.663 --> 00:10:40.626
p estrela é o tamanho deste grupo. Mas outra maneira de pensar sobre o que é

00:10:40.626 --> 00:10:46.280
basicamente é o menor número inteiro Um tal que G para o A é igual a um no Z P.

00:10:47.380 --> 00:10:52.838
razoável, é basicamente o menor de energia que faz com que o poder de G para ser igual à

00:10:52.838 --> 00:10:58.566
um. E é muito fácil ver que essa igualdade aqui, basicamente, se olharmos para todos

00:10:58.566 --> 00:11:04.024
os poderes de G e olhamos para um, G, G quadrado, G em cubos e assim por diante e assim por diante até

00:11:04.024 --> 00:11:09.887
até chegarmos ao G com a ordem de G menos um. E então se olharmos para a ordem de G

00:11:09.887 --> 00:11:15.420
com a ordem de G. Esta coisa é simplesmente vai ser igual a um, por definição.

00:11:16.080 --> 00:11:22.000
Ok, então não há nenhum ponto em olhar todas as potências mais elevadas. Nós pode muito bem

00:11:22.000 --> 00:11:27.631
parar de aumentar os poderes aqui. E, como resultado do tamanho do conjunto, na verdade, é

00:11:27.631 --> 00:11:33.263
a ordem de G. E você pode ver que a ordem é o menor poder de tal forma que

00:11:33.263 --> 00:11:38.931
G elevando para que o poder dá-nos um em Z p. Então eu espero que isso está claro, embora

00:11:38.931 --> 00:11:43.455
pode levar um pouco de pensar para absorver toda esta notação. Mas no

00:11:43.455 --> 00:11:48.100
Enquanto isso vamos olhar para alguns exemplos. Então, novamente, vamos fixar a nossa, a nossa principal a ser

00:11:48.100 --> 00:11:52.986
sete. E vamos olhar para a ordem do número de elementos. Então, qual é a ordem

00:11:52.986 --> 00:11:57.752
de três módulo de sete? Bem, nós estamos perguntando o que é o tamanho do grupo que

00:11:57.752 --> 00:12:02.759
três gera módulo de sete? Bem, nós dissemos que três é um gerador de Z7 estrela.

00:12:02.759 --> 00:12:07.705
Então ele gera todos Z7 estrela. Há seis elementos em Z7 estrela. E, portanto,

00:12:07.705 --> 00:12:12.758
dizer que a ordem de três é igual a seis. Da mesma forma, eu posso perguntar, bem, o que é

00:12:12.758 --> 00:12:17.421
fim de dois modulo sete? E, de fato, já vimos a resposta. Então vamos,

00:12:17.421 --> 00:12:22.084
eu vou lhe perguntar, qual é a ordem de dois modulo sete e veja se você consegue f igura

00:12:22.084 --> 00:12:28.549
o que esta resposta é. Portanto, a resposta é de três e mais uma vez, a razão é, se olharmos

00:12:28.549 --> 00:12:33.618
no conjunto de potências de dois modulo sete, temos um, dois, dois quadrado e, em seguida

00:12:33.618 --> 00:12:39.077
cubado dois já é igual a um. Portanto, este é todo o conjunto de potências de dois modulo

00:12:39.077 --> 00:12:44.211
sete. Existem apenas três deles e, portanto, da ordem de dois modulo sete

00:12:44.211 --> 00:12:49.215
é exatamente três. Agora deixe-me lhe fazer uma pergunta capciosa. Qual é a ordem de um

00:12:49.215 --> 00:12:54.499
modulo sete? Bem, a resposta é uma só. Porque se você olhar para o grupo que é

00:12:54.499 --> 00:12:58.633
gerada por um, bem, há apenas um número em que o grupo, ou seja, o número

00:12:58.633 --> 00:13:02.608
um. Se eu levantar um a um monte de poderes, eu sempre vou ter um, E

00:13:02.608 --> 00:13:07.060
, portanto, a ordem de 1 modulo 7 Na verdade, a ordem de 1 modulo qualquer injeção

00:13:07.060 --> 00:13:12.518
é sempre vai ser 1. Agora há um importante teorema de Lagrange, que

00:13:12.518 --> 00:13:17.137
realmente este é um caso muito, muito especial dele, o que estou afirmando aqui. Mas

00:13:17.137 --> 00:13:22.309
teorema de Langrage basicamente implica que, se você olhar para a ordem de G módulo p,

00:13:22.309 --> 00:13:27.112
ordem sempre vai dividir P-1. Assim, em nosso exemplo dois você vê,

00:13:27.297 --> 00:13:32.100
seis divide sete menos um, seis divide seis, e, similarmente, três divide sete

00:13:32.100 --> 00:13:37.026
menos um. Nomeadamente novamente três divide seis. Mas isso é muito geral, o seu fim é

00:13:37.026 --> 00:13:41.333
sempre vai ser um fator de P menos um. Na verdade, eu vou te dizer, talvez seja uma

00:13:41.333 --> 00:13:45.177
quebra-cabeças para você pensar. É realmente muito fácil deduzir de Fermat

00:13:45.177 --> 00:13:49.179
teorema directamente a partir deste fato, a partir do teorema de Lagrange esta de fato. E assim

00:13:49.179 --> 00:13:53.340
teorema de Fermat realmente em certo sentido, segue-se diretamente do teorema de Lagrange.

00:13:54.580 --> 00:13:59.375
Lagrange, a propósito, que o seu trabalho no século XIX, assim você já pode ver

00:13:59.375 --> 00:14:04.053
como estamos a fazer progressos ao longo do tempo. Começamos em tempos gregos, e já que

00:14:04.053 --> 00:14:09.376
acabou no século XIX. E eu posso te dizer que a criptografia mais avançada

00:14:09.376 --> 00:14:14.024
realmente usa a matemática do século XX é bastante extensa. Agora que entendemos o

00:14:14.024 --> 00:14:18.416
estrutura de ZP estrela, vamos generalizar que a compósitos, e olhar para o

00:14:18.416 --> 00:14:23.471
estrutura da ZN estrela. Então o que eu quero mostrar aqui é que é chamado Teorema de Euler

00:14:23.471 --> 00:14:28.044
, que é uma, uma generalização direta do Teorema de Fermat. Assim, Euler definido o

00:14:28.044 --> 00:14:32.978
seguinte função. Portanto, dado um número inteiro N, ele definiu o que é chamado de phi

00:14:32.978 --> 00:14:37.190
função, phi de M, a ser basicamente o tamanho do conjunto ZN estrela.

00:14:37.190 --> 00:14:42.686
Isso às vezes é chamado, a função de Euler phi. O tamanho do conjunto ZN estrela. Assim

00:14:42.686 --> 00:14:48.521
por exemplo, que já olhou Z estrela de doze. Dissemos que Z contém 12 estrelas

00:14:48.521 --> 00:14:53.881
estes quatro elementos, um, cinco, sete e onze anos. E por isso dizemos que phi de

00:14:53.881 --> 00:14:59.310
12 é simplesmente o número quatro. Então deixe-me perguntar-lhe como um quebra-cabeça, o que é phi de P?

00:14:59.310 --> 00:15:06.266
Ela vai ser basicamente o tamanho de ZP estrela. E assim, de fato, dissemos que na ZP

00:15:06.266 --> 00:15:12.335
estrela contém todos ZP, exceto para o número zero. E, portanto, phi de P para

00:15:12.335 --> 00:15:18.533
qualquer P principal vai ser P menos um. Agora, há um caso especial, que eu vou

00:15:18.533 --> 00:15:23.282
estado aqui e nós vamos usar mais tarde para o sistema RSA. Se N passa a ser um

00:15:23.282 --> 00:15:28.277
produto de dois primos, então phi de N é simplesmente menos N P Q menos mais um. E deixe-

00:15:28.277 --> 00:15:33.045
me mostrar por que isso é verdade. Então, basicamente, N é o tamanho do Z N. E agora nós

00:15:33.045 --> 00:15:37.838
necessário remover todos os elementos que não são relativamente primos com m. Bem como pode um

00:15:37.838 --> 00:15:42.632
elemento não ser relativamente primos para m? Tem que ser divisível por p, ou que tem que ser

00:15:42.632 --> 00:15:47.079
divisível por q. Bem, como muitos elementos entre zero e menos um m estão lá,

00:15:47.079 --> 00:15:51.757
lá que são divisíveis por p? Bem, existem exatamente q deles. Quantos elementos

00:15:51.757 --> 00:15:55.973
existem que são divisíveis por q. Bem, existem exatamente p deles. Então, nós

00:15:55.973 --> 00:16:00.593
subtrair p se livrar daqueles divisível por q. Nós subtrair q se livrar daqueles

00:16:00.593 --> 00:16:05.776
divisível por p. E você percebe que subtraído de zero duas vezes, porque zero é

00:16:05.776 --> 00:16:12.020
divisível tanto por P e Q. E, portanto, nós adicionamos um apenas para ter certeza de que subtrair

00:16:12.020 --> 00:16:18.264
zero apenas uma vez. E por isso não é difícil ver que phi (N) é NP-Q +1. E uma outra maneira

00:16:18.264 --> 00:16:24.599
de escrita que é simplesmente (P-1) vezes (Q-1). Ok, então isso é um fato que usaremos mais tarde

00:16:24.599 --> 00:16:30.275
, quando voltamos e falar sobre o sistema RSA. Até agora, esta é apenas a definição de

00:16:30.275 --> 00:16:35.690
esta função phi de Euler. Mas agora Euler colocar esta função phi de uso muito bom.

00:16:35.690 --> 00:16:41.104
E o que ele provou este fato maravilhoso aqui que diz basicamente que se você der

00:16:41.104 --> 00:16:46.060
me qualquer elemento X na ZN estrela. Na verdade, e acontece que X ao poder de phi (N)

00:16:46.060 --> 00:16:50.678
é igual a um em Z N. Assim, você pode ver que isso é uma generalização de Fermat

00:16:50.678 --> 00:16:55.239
teorema, em particular, o teorema de Fermat só é aplicado a números primos. Para primos que conhecemos

00:16:55.239 --> 00:16:59.913
que phi (p) é igual a p menos um, e, em outras palavras, se fosse primeiro-N faríamos

00:16:59.913 --> 00:17:04.494
simplesmente escrever p menos um aqui, e então nós teríamos exatamente o teorema de Fermat. O

00:17:04.494 --> 00:17:08.892
beleza do teorema de Euler é que se aplica a materiais compósitos, e não apenas

00:17:08.892 --> 00:17:16.462
primos. Então, vamos olhar para alguns exemplos. Então, vamos olhar para cinco o poder de phi (12).

00:17:16.462 --> 00:17:21.743
Assim, cinco é um elemento de Z12 estrela. Se aumentá-lo para o poder de cinco dos

00:17:21.743 --> 00:17:27.155
12, que deve estar recebendo uma. Bem, sabemos que phi (12) é de 4, então estamos

00:17:27.155 --> 00:17:32.037
levantando 5 à potência de 4. Cinco para o poder de quatro é de 625 e é um simples

00:17:32.037 --> 00:17:36.227
cálculo para mostrar que isso é igual a 1 módulo 12. Então esta é a prova

00:17:36.227 --> 00:17:40.468
por exemplo, mas é claro que não é uma prova em tudo. É apenas um exemplo. Mas, na verdade

00:17:40.468 --> 00:17:44.555
não é difícil de provar o teorema de Euler e na verdade eu vou dizer-lhe que

00:17:44.555 --> 00:17:48.900
teorema de Euler é também um caso muito especial do teorema geral de Lagrange.

00:17:49.880 --> 00:17:53.888
Ok então dizemos que esta é uma generalização do teorema de Fermat e

00:17:53.888 --> 00:17:58.230
, de fato, como veremos este teorema de Euler é a base da criptografia RSA

00:17:58.230 --> 00:18:03.922
sistema. Então eu parar por aqui e vamos continuar com modulares equações quadráticas na

00:18:03.922 --> 00:18:04.740
próximo segmento.