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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:01:16.107,0:01:21.037
vamos passar de tempos dos gregos até o fim do século XVII e

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

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

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

0:01:36.260,0: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

0:01:41.130,0: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

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

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

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

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

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

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

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

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

0:02:24.664,0:02:29.573
P menos um de X vezes X para o poder de P menos dois. Bem agora que sabemos que X

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:04:33.003,0:04:37.284
fazemos é voltar a um passo e procuramos outro primo. E fazemos isso de novo e

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

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

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

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

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

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

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

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

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

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

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

0:05:29.587,0:05:34.298
sorte que um evento de probabilidade negligenciável aconteceu. Outra forma de dizer

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

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

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

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

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

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

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

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

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

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

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

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

0:06:32.654,0:06:36.349
principal candidato, agora temos algoritmos muito eficientes que realmente

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

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

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

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

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

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

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

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

0:07:09.833,0:07:14.771
esperar algumas centenas de iterações e nada mais. Agora que entendemos

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

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

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

0:07:28.576,0:07:33.118
coisas Euler mostrou é em linguagem moderna é que ZP estrela é o que chamamos de

0:07:33.118,0:07:38.014
grupo cíclico. O que significa que ZP estrela é um grupo cíclico? O que significa é

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

0:07:42.734,0: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é

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

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

0:07:57.296,0: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

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

0:08:06.825,0: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

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

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

0:08:21.413,0:08:26.300
olhada em todos os seus poderes de todos os seus poderes expandir o Estrela ZP todo o grupo.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:10:35.663,0:10:40.626
p estrela é o tamanho deste grupo. Mas outra maneira de pensar sobre o que é

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

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

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

0:10:58.566,0: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é

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:13:27.297,0:13:32.100
seis divide sete menos um, seis divide seis, e, similarmente, três divide sete

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0:14:53.881,0: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?

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

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

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

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

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

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

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

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

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

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

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

0:15:55.973,0:16:00.593
subtrair p se livrar daqueles divisível por q. Nós subtrair q se livrar daqueles

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

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

0:16:12.020,0: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

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

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

0:16:30.275,0:16:35.690
esta função phi de Euler. Mas agora Euler colocar esta função phi de uso muito bom.

0:16:35.690,0:16:41.104
E o que ele provou este fato maravilhoso aqui que diz basicamente que se você der

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

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

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

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

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

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

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

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

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

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

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

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

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

0:17:44.555,0:17:48.900
teorema de Euler é também um caso muito especial do teorema geral de Lagrange.

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

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

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

0:18:03.922,0:18:04.740
próximo segmento.