1
00:00:00,000 --> 00:00:04,220
No segmento anterior falamos sobre inversão modular e nós dissemos a Euclides

2
00:00:04,220 --> 00:00:08,238
algoritmo nos dá uma maneira eficiente de encontrar o inverso de um elemento módulo N.

3
00:00:08,238 --> 00:00:12,256
Neste segmento vamos encaminhar através do tempo e vamos passar para

4
00:00:12,256 --> 00:00:15,866
o século XVII e XVIII, onde nós estamos indo falar sobre

5
00:00:15,866 --> 00:00:19,986
Fermat e contribuições de Euler. Antes disso vamos fazer uma rápida revisão de

6
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

7
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

8
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

9
00:00:32,445 --> 00:00:36,761
denotar um primo. Agora dissemos que ZN é um conjunto de números inteiros de zero

10
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

11
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

12
00:00:46,186 --> 00:00:51,243
provou um lema simples dizer que, X é inversível se e somente se X é relativamente

13
00:00:51,243 --> 00:00:55,879
privilegiada para N. E não só nós entendemos completamente quais são os elementos

14
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

15
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

16
00:01:05,572 --> 00:01:10,388
que o tempo de execução deste algoritmo, é basicamente ordem n quadrado, onde

17
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

18
00:01:16,107 --> 00:01:21,037
vamos passar de tempos dos gregos até o fim do século XVII e

19
00:01:21,037 --> 00:01:26,276
falar de Fermat. Assim, Fermat fez uma série de teoremas importantes. O que eu quero

20
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

21
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

22
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

23
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

24
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,

25
00:01:50,645 --> 00:01:55,286
que, na verdade, é um modulo cinco. Este exemplo satisfaz o teorema de Fermat.

26
00:01:55,286 --> 00:01:59,521
Curiosamente, Fermat, na verdade não provar este teorema si mesmo. A prova

27
00:01:59,521 --> 00:02:04,337
realmente esperou até Euler, que provou que quase 100 anos depois. E em

28
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

29
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

30
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

31
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

32
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

33
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

34
00:02:34,087 --> 00:02:39,310
diz, é que realmente o inverso do modulo X P, é simplesmente X para o P menos dois.

35
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.

36
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

37
00:02:48,835 --> 00:02:53,508
x. Acontece que, na verdade, esta é uma boa maneira de calcular o inverso modulo um primo.

38
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ó

39
00:02:58,301 --> 00:03:02,528
primos obras modulo, Considerando que, o algoritmo de Euclides trabalhou modulo compósitos como

40
00:03:02,528 --> 00:03:07,017
bem. E em segundo lugar, verifica-se este algoritmo é na verdade menos eficiente. Quando

41
00:03:07,017 --> 00:03:10,911
falamos sobre como fazer exponenciações modulares - nós estamos indo fazer isso em

42
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

43
00:03:15,345 --> 00:03:19,792
exponenciação é realmente cúbico no tamanho P. Então, isso vai levar cerca de login

44
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

45
00:03:24,266 --> 00:03:30,343
inversa no tempo quadrático na representação de P. Então não é só isso

46
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

47
00:03:36,512 --> 00:03:41,473
um para Euclides. Mas, no entanto, este fato sobre números primos é extremamente importante,

48
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

49
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

50
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

51
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á

52
00:04:02,006 --> 00:04:06,724
um algoritmo muito simples probabilística. O que nós fazemos é que escolher um

53
00:04:06,724 --> 00:04:11,938
inteiro aleatório no intervalo que foi especificado. E então poderíamos testar se

54
00:04:12,124 --> 00:04:17,153
inteiro ele satisfaz o teorema de Fermat. Em outras palavras, seria testar por exemplo

55
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

56
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

57
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

58
00:04:33,003 --> 00:04:37,284
fazemos é voltar a um passo e procuramos outro primo. E fazemos isso de novo e

59
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

60
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

61
00:04:46,009 --> 00:04:51,573
de paragem. Agora se vê, esta é realmente uma declaração bastante difícil de provar. Mas

62
00:04:51,573 --> 00:04:56,305
acontece se um número aleatório passar este teste, então é extremamente provável que

63
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. É

64
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

65
00:05:06,191 --> 00:05:10,744
número fica maior e maior a probabilidade de que ele passa este teste aqui,

66
00:05:10,744 --> 00:05:15,716
mas não é algumas gotas prime para zero muito rapidamente. Portanto, este é realmente um grande

67
00:05:15,716 --> 00:05:20,455
algoritmo interessante. Você percebe que não está garantido que a saída é na verdade

68
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

69
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

70
00:05:29,587 --> 00:05:34,298
sorte que um evento de probabilidade negligenciável aconteceu. Outra forma de dizer

71
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

72
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

73
00:05:45,233 --> 00:05:50,805
compósitos. Isso realmente vai falsificar o teste. Vamos chamá-los F para falsos primos.

74
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

75
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,

76
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

77
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

78
00:06:10,260 --> 00:06:15,082
Isso é, essencialmente, um acontecimento insignificante que podemos ignorar. Em outras palavras, uma

79
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 é

80
00:06:20,591 --> 00:06:25,266
improvável que tal escolher primeiro um falso. Agora eu devo mencionar, na verdade, isso é muito

81
00:06:25,266 --> 00:06:28,960
algoritmo simples para gerar primos. É, na verdade, de longe, não é o melhor

82
00:06:28,960 --> 00:06:32,654
algoritmo. Temos algoritmos muito melhores agora. E, de fato, uma vez que você tem um

83
00:06:32,654 --> 00:06:36,349
principal candidato, agora temos algoritmos muito eficientes que realmente

84
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

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

86
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.

87
00:06:48,595 --> 00:06:53,076
Embora, na realidade, não é assim que números primos são gerados. Como último ponto,

88
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

89
00:06:57,468 --> 00:07:01,536
até realmente encontrar o primo. E isso é realmente um resultado clássico, é

90
00:07:01,536 --> 00:07:05,820
chamado teorema do número primo, que diz que, depois de algumas centenas de iterações,

91
00:07:05,820 --> 00:07:09,833
na verdade, nós vamos encontrar o primeiro com alta probabilidade. Assim, na expectativa, seria

92
00:07:09,833 --> 00:07:14,771
esperar algumas centenas de iterações e nada mais. Agora que entendemos

93
00:07:14,771 --> 00:07:19,314
teorema de Fermat, a próxima coisa que eu quero falar é sobre o que é chamado a

94
00:07:19,314 --> 00:07:23,915
estrutura de ZP estrela. Então, aqui, nós vamos passar de 100 anos no futuro ...

95
00:07:23,915 --> 00:07:28,576
no século XVIII e olhar para o trabalho de Euler. E um dos primeiros

96
00:07:28,576 --> 00:07:33,118
coisas Euler mostrou é em linguagem moderna é que ZP estrela é o que chamamos de

97
00:07:33,118 --> 00:07:38,014
grupo cíclico. O que significa que ZP estrela é um grupo cíclico? O que significa é

98
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

99
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é

100
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

101
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

102
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

103
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

104
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

105
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.

106
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ê

107
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.

108
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

109
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

110
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

111
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,

112
00:08:45,575 --> 00:08:50,130
três ao quinto, três a seis, já se sabe, é igual a um modular

113
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

114
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

115
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,

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

117
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

118
00:09:14,599 --> 00:09:19,886
cada elemento é um gerador. Por exemplo, se olharmos para todas as potências de dois, bem,

119
00:09:19,886 --> 00:09:24,914
isso não vai gerar todo o grupo. Em particular, se olharmos para dois a

120
00:09:24,914 --> 00:09:29,650
zero a, obtemos um. Dois a um, temos dois. Dois ao quadrado é quatro, e duas

121
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

122
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

123
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

124
00:09:44,697 --> 00:09:49,981
grupo todo e, portanto, dizemos que dois não é um gerador de Z7 estrela. Agora, novamente,

125
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

126
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

127
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

128
00:10:06,947 --> 00:10:12,798
grupo multiplicativo. Mais uma vez, o termo técnico não importa. O ponto é que estamos

129
00:10:12,798 --> 00:10:18,397
vai chamar todos estes poderes de G, o grupo gerado por G. De fato há essa

130
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 é

131
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

132
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

133
00:10:35,663 --> 00:10:40,626
p estrela é o tamanho deste grupo. Mas outra maneira de pensar sobre o que é

134
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.

135
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 à

136
00:10:52,838 --> 00:10:58,566
um. E é muito fácil ver que essa igualdade aqui, basicamente, se olharmos para todos

137
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é

138
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

139
00:11:09,887 --> 00:11:15,420
com a ordem de G. Esta coisa é simplesmente vai ser igual a um, por definição.

140
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

141
00:11:22,000 --> 00:11:27,631
parar de aumentar os poderes aqui. E, como resultado do tamanho do conjunto, na verdade, é

142
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

143
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

144
00:11:38,931 --> 00:11:43,455
pode levar um pouco de pensar para absorver toda esta notação. Mas no

145
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

146
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

147
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

148
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.

149
00:12:02,759 --> 00:12:07,705
Então ele gera todos Z7 estrela. Há seis elementos em Z7 estrela. E, portanto,

150
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 é

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

152
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

153
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

154
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

155
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

156
00:12:39,077 --> 00:12:44,211
sete. Existem apenas três deles e, portanto, da ordem de dois modulo sete

157
00:12:44,211 --> 00:12:49,215
é exatamente três. Agora deixe-me lhe fazer uma pergunta capciosa. Qual é a ordem de um

158
00:12:49,215 --> 00:12:54,499
modulo sete? Bem, a resposta é uma só. Porque se você olhar para o grupo que é

159
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

160
00:12:58,633 --> 00:13:02,608
um. Se eu levantar um a um monte de poderes, eu sempre vou ter um, E

161
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

162
00:13:07,060 --> 00:13:12,518
é sempre vai ser 1. Agora há um importante teorema de Lagrange, que

163
00:13:12,518 --> 00:13:17,137
realmente este é um caso muito, muito especial dele, o que estou afirmando aqui. Mas

164
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,

165
00:13:22,309 --> 00:13:27,112
ordem sempre vai dividir P-1. Assim, em nosso exemplo dois você vê,

166
00:13:27,297 --> 00:13:32,100
seis divide sete menos um, seis divide seis, e, similarmente, três divide sete

167
00:13:32,100 --> 00:13:37,026
menos um. Nomeadamente novamente três divide seis. Mas isso é muito geral, o seu fim é

168
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

169
00:13:41,333 --> 00:13:45,177
quebra-cabeças para você pensar. É realmente muito fácil deduzir de Fermat

170
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

171
00:13:49,179 --> 00:13:53,340
teorema de Fermat realmente em certo sentido, segue-se diretamente do teorema de Lagrange.

172
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

173
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

174
00:14:04,053 --> 00:14:09,376
acabou no século XIX. E eu posso te dizer que a criptografia mais avançada

175
00:14:09,376 --> 00:14:14,024
realmente usa a matemática do século XX é bastante extensa. Agora que entendemos o

176
00:14:14,024 --> 00:14:18,416
estrutura de ZP estrela, vamos generalizar que a compósitos, e olhar para o

177
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

178
00:14:23,471 --> 00:14:28,044
, que é uma, uma generalização direta do Teorema de Fermat. Assim, Euler definido o

179
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

180
00:14:32,978 --> 00:14:37,190
função, phi de M, a ser basicamente o tamanho do conjunto ZN estrela.

181
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

182
00:14:42,686 --> 00:14:48,521
por exemplo, que já olhou Z estrela de doze. Dissemos que Z contém 12 estrelas

183
00:14:48,521 --> 00:14:53,881
estes quatro elementos, um, cinco, sete e onze anos. E por isso dizemos que phi de

184
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?

185
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

186
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

187
00:15:12,335 --> 00:15:18,533
qualquer P principal vai ser P menos um. Agora, há um caso especial, que eu vou

188
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

189
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-

190
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

191
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

192
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

193
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á,

194
00:15:47,079 --> 00:15:51,757
lá que são divisíveis por p? Bem, existem exatamente q deles. Quantos elementos

195
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

196
00:15:55,973 --> 00:16:00,593
subtrair p se livrar daqueles divisível por q. Nós subtrair q se livrar daqueles

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

198
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

199
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

200
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

201
00:16:24,599 --> 00:16:30,275
, quando voltamos e falar sobre o sistema RSA. Até agora, esta é apenas a definição de

202
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.

203
00:16:35,690 --> 00:16:41,104
E o que ele provou este fato maravilhoso aqui que diz basicamente que se você der

204
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)

205
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

206
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

207
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

208
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

209
00:17:04,494 --> 00:17:08,892
beleza do teorema de Euler é que se aplica a materiais compósitos, e não apenas

210
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).

211
00:17:16,462 --> 00:17:21,743
Assim, cinco é um elemento de Z12 estrela. Se aumentá-lo para o poder de cinco dos

212
00:17:21,743 --> 00:17:27,155
12, que deve estar recebendo uma. Bem, sabemos que phi (12) é de 4, então estamos

213
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

214
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

215
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

216
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

217
00:17:44,555 --> 00:17:48,900
teorema de Euler é também um caso muito especial do teorema geral de Lagrange.

218
00:17:49,880 --> 00:17:53,888
Ok então dizemos que esta é uma generalização do teorema de Fermat e

219
00:17:53,888 --> 00:17:58,230
, de fato, como veremos este teorema de Euler é a base da criptografia RSA

220
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

221
00:18:03,922 --> 00:18:04,740
próximo segmento.