No segmento anterior falamos sobre inversão modular e nós dissemos a Euclides
algoritmo nos dá uma maneira eficiente de encontrar o inverso de um elemento módulo N.
Neste segmento vamos encaminhar através do tempo e vamos passar para
o século XVII e XVIII, onde nós estamos indo falar sobre
Fermat e contribuições de Euler. Antes disso vamos fazer uma rápida revisão de
o que discutimos no segmento anterior. Então, como de costume, eu vou deixar N denotar o
inteiro positivo e vamos apenas dizer que N passa a ser um número inteiro de n bits, em outro
palavras, entre duas a n e dois para o n +1, como de costume vamos deixar que P
denotar um primo. Agora dissemos que ZN é um conjunto de números inteiros de zero
para N-1 e nós dissemos que podemos somar e multiplicar elementos no conjunto de módulo N. Nós
também disse que ZN estrela é basicamente o conjunto de elementos invertíveis em ZN. E nós
provou um lema simples dizer que, X é inversível se e somente se X é relativamente
privilegiada para N. E não só nós entendemos completamente quais são os elementos
e invertíveis que não são, também mostraram um algoritmo muito eficiente com base no
algoritmo estendido de Euclides, para encontrar o inverso de um elemento X na ZN. E nós dissemos
que o tempo de execução deste algoritmo, é basicamente ordem n quadrado, onde
novamente, n é o número de bits do número de capital N. Assim como disse, agora
vamos passar de tempos dos gregos até o fim do século XVII e
falar de Fermat. Assim, Fermat fez uma série de teoremas importantes. O que eu quero
para mostrar aqui hoje é o seguinte. Então, suponhamos que eu lhe dou um p primo, então em
fato, para qualquer elemento X em ZP estrela, acontece que se eu olhar para X e elevá-la
para o poder da P - 1, eu sou um vai pegar um, na ZP. Então, vamos olhar para uma rápida
exemplo. Suponha que eu definir o número de P a ser cinco. E eu olhar, três para o poder de
P-1. Em outras palavras, três à potência de quatro, três à potência de quatro é de 81,
que, na verdade, é um modulo cinco. Este exemplo satisfaz o teorema de Fermat.
Curiosamente, Fermat, na verdade não provar este teorema si mesmo. A prova
realmente esperou até Euler, que provou que quase 100 anos depois. E em
verdade, ele provou ser uma versão muito mais geral deste teorema. Então, vamos olhar para
uma aplicação simples do teorema de Fermat. Suponha que eu olhar para um elemento X em ZP
estrela. E eu quero lembrar aqui que P [inaudível] deve ser um primo. Bem, então o que nós
sabe? Sabemos que X para o P menos um é igual a um. Bem, podemos escrever X para o
P menos um de X vezes X para o poder de P menos dois. Bem agora que sabemos que X
vezes X para o poder de P menos dois acontece ser igual a um. E o que isso
diz, é que realmente o inverso do modulo X P, é simplesmente X para o P menos dois.
Então isso nos dá um outro algoritmo para encontrar o inverso de X modulo um primo.
Basta levantar o X para o poder de p menos dois, e que nos dará o inverso da
x. Acontece que, na verdade, esta é uma boa maneira de calcular o inverso modulo um primo.
Mas tem duas deficiências em comparação com o algoritmo de Euclides. Em primeiro lugar, ela só
primos obras modulo, Considerando que, o algoritmo de Euclides trabalhou modulo compósitos como
bem. E em segundo lugar, verifica-se este algoritmo é na verdade menos eficiente. Quando
falamos sobre como fazer exponenciações modulares - nós estamos indo fazer isso em
o último segmento neste módulo - você verá que o tempo de execução para computar este
exponenciação é realmente cúbico no tamanho P. Então, isso vai levar cerca de login
cubo de P, enquanto que se você se lembra, o algoritmo de Euclides foi capaz de calcular a
inversa no tempo quadrático na representação de P. Então não é só isso
algoritmo menos geral, funciona apenas para números primos, que também é menos eficiente. Então pontuação
um para Euclides. Mas, no entanto, este fato sobre números primos é extremamente importante,
e nós vamos estar fazendo uso extensivo de que no próximo par de semanas. Então deixe-me
mostrar-lhe uma aplicação rápida e simples para o teorema de Fermat vamos supor que queremos
para gerar um primeiro grande acaso, dizer que a nossa principal precisava ser 1.000 bits ou mais. Assim
principal o que estamos procurando é da ordem de dois para o 1024 [inaudível]. Então aqui está
um algoritmo muito simples probabilística. O que nós fazemos é que escolher um
inteiro aleatório no intervalo que foi especificado. E então poderíamos testar se
inteiro ele satisfaz o teorema de Fermat. Em outras palavras, seria testar por exemplo
utilizando a base dois, iríamos testar se os dois para o poder de p menos um é igual a um
em Z p. Se a resposta for não, então se essa igualdade não existe, então sabemos para
certeza de que o número p que escolhemos não é primo. E se isso acontecer, todos nós
fazemos é voltar a um passo e procuramos outro primo. E fazemos isso de novo e
novo e de novo, até que finalmente encontramos um número inteiro que satisfaz essa condição. E
uma vez que encontramos um número inteiro que satisfaz essa condição, simplesmente imprimir-lo e
de paragem. Agora se vê, esta é realmente uma declaração bastante difícil de provar. Mas
acontece se um número aleatório passar este teste, então é extremamente provável que
ser um primo. Em particular, a probabilidade de que P não é um número primo é muito pequena. É
como menos de dois para a -60 para a gama de números de 1024 bits. À medida que o
número fica maior e maior a probabilidade de que ele passa este teste aqui,
mas não é algumas gotas prime para zero muito rapidamente. Portanto, este é realmente um grande
algoritmo interessante. Você percebe que não está garantido que a saída é na verdade
um primo. Tudo o que sabemos é que ele é muito, muito provável que seja um primo. Em outras palavras
, a única maneira que não é um número primo é que temos muito azar. Na verdade isso
sorte que um evento de probabilidade negligenciável aconteceu. Outra forma de dizer
isto é que se você olhar para o conjunto de todos os 1024 números inteiros, então, bem, há o conjunto
dos números primos. Deixe-me escrever aqui primeiro. E depois há um pequeno número de
compósitos. Isso realmente vai falsificar o teste. Vamos chamá-los F para falsos primos.
Vamos chamá-los de FP, para primos falsos. Há um número muito pequeno de compósitos
que não são primos e ainda vai passar este teste. Mas, como escolher inteiros aleatórios,
você sabe, nós escolhemos um aqui, outro aqui, um aqui, e assim por diante, como escolher aleatoriamente
inteiros, a probabilidade de que caem dentro do conjunto de números primos falsos é tão pequena
Isso é, essencialmente, um acontecimento insignificante que podemos ignorar. Em outras palavras, uma
pode provar que o conjunto dos números primos falsas é extremamente pequena, e uma escolha aleatória é
improvável que tal escolher primeiro um falso. Agora eu devo mencionar, na verdade, isso é muito
algoritmo simples para gerar primos. É, na verdade, de longe, não é o melhor
algoritmo. Temos algoritmos muito melhores agora. E, de fato, uma vez que você tem um
principal candidato, agora temos algoritmos muito eficientes que realmente
provar além de qualquer dúvida que este nobre candidato realmente é um primo. Então, nós nem sequer
tem que confiar nas afirmações probabilísticas. Mas, no entanto, este teste é tão Fermat
simples, que eu só queria mostrar-lhe que é uma maneira fácil de gerar números primos.
Embora, na realidade, não é assim que números primos são gerados. Como último ponto,
eu vou dizer que você deve estar se perguntando quantas vezes esta iteração tem de repetir
até realmente encontrar o primo. E isso é realmente um resultado clássico, é
chamado teorema do número primo, que diz que, depois de algumas centenas de iterações,
na verdade, nós vamos encontrar o primeiro com alta probabilidade. Assim, na expectativa, seria
esperar algumas centenas de iterações e nada mais. Agora que entendemos
teorema de Fermat, a próxima coisa que eu quero falar é sobre o que é chamado a
estrutura de ZP estrela. Então, aqui, nós vamos passar de 100 anos no futuro ...
no século XVIII e olhar para o trabalho de Euler. E um dos primeiros
coisas Euler mostrou é em linguagem moderna é que ZP estrela é o que chamamos de
grupo cíclico. O que significa que ZP estrela é um grupo cíclico? O que significa é
que existe algum elemento em G ZP estrela, de tal forma que se tomarmos G e aumentar a
um monte de poderes G, G quadrado, ao cubo G, G para o quarto. E assim por diante e assim por diante até
até chegarmos ao G P menos dois. Observe que não há ponto de ir além G
ao menos duas p, porque G para o p menos um pelo teorema de Fermat é igual para
um, por isso, então vamos voltar ao ciclo de um. Se voltarmos ao G ao menos um p, então G
para a p será igual a G, G para o p, mais uma será igual a G quadrado, e
assim por diante e assim por diante. Então, nós vamos realmente começar um ciclo se continuarmos elevando para mais e
poderes superiores de G. Assim, poderíamos muito bem parar no poder do G para a p menos dois.
E que Euler mostrou é que na verdade não é um elemento G de tal forma que se você
olhada em todos os seus poderes de todos os seus poderes expandir o Estrela ZP todo o grupo.
Os poderes do G nos dá todos os elementos em ZP estrela. Os elementos deste, deste tipo de
é chamado um gerador. Então G seria dito ser um gerador de ZP estrela. Então, vamos
olhar para um exemplo rápido. Então, vamos olhar, por exemplo, em P é igual a sete. E vamos
olhada em todos os poderes de três. Então, três três cubos quadrado, três para o quarto,
três ao quinto, três a seis, já se sabe, é igual a um modular
sete pelo Teorema de Fermat. Então não há nenhum ponto em olhar para três a seis. Nós
sabemos que só iria começar um. Então aqui, eu calculei todos esses poderes para você, e eu
escreveu-los. E você vê que, na verdade, nós temos todos os números [inaudível] em Z,
em Z7 estrela. Em outras palavras, obtemos um, dois, três, quatro, cinco, seis e. Assim
diríamos que três é um gerador de Z7 estrela. Agora gostaria de salientar que não
cada elemento é um gerador. Por exemplo, se olharmos para todas as potências de dois, bem,
isso não vai gerar todo o grupo. Em particular, se olharmos para dois a
zero a, obtemos um. Dois a um, temos dois. Dois ao quadrado é quatro, e duas
ao cubo é de oito, que é um sete modular. Assim pedalamos de volta e, em seguida, dois a
quarta seria dois, dois para o quinto seria quatro. E assim por diante e assim por diante. Assim
, se olharmos para os poderes dos dois, é só pegar um, dois e quatro. Nós não temos a
grupo todo e, portanto, dizemos que dois não é um gerador de Z7 estrela. Agora, novamente,
algo que nós vamos usar muitas vezes é dado um elemento de G * ZP, se olharmos para um
conjunto de todos os poderes de G, o conjunto resultante vai ser chamado o grupo gerado por
G, ok? Então, esses são todos os poderes de G. Eles dão-nos o que é chamado de
grupo multiplicativo. Mais uma vez, o termo técnico não importa. O ponto é que estamos
vai chamar todos estes poderes de G, o grupo gerado por G. De fato há essa
notação que eu não uso com muita frequência, ângulo ângulo G, para designar esse grupo que é
gerada por G. E então nós chamamos a ordem de G em Z p estrela, simplesmente deixe que seja
do tamanho do grupo que é gerado por G. Assim, em outras palavras, a ordem de G em Z
p estrela é o tamanho deste grupo. Mas outra maneira de pensar sobre o que é
basicamente é o menor número inteiro Um tal que G para o A é igual a um no Z P.
razoável, é basicamente o menor de energia que faz com que o poder de G para ser igual à
um. E é muito fácil ver que essa igualdade aqui, basicamente, se olharmos para todos
os poderes de G e olhamos para um, G, G quadrado, G em cubos e assim por diante e assim por diante até
até chegarmos ao G com a ordem de G menos um. E então se olharmos para a ordem de G
com a ordem de G. Esta coisa é simplesmente vai ser igual a um, por definição.
Ok, então não há nenhum ponto em olhar todas as potências mais elevadas. Nós pode muito bem
parar de aumentar os poderes aqui. E, como resultado do tamanho do conjunto, na verdade, é
a ordem de G. E você pode ver que a ordem é o menor poder de tal forma que
G elevando para que o poder dá-nos um em Z p. Então eu espero que isso está claro, embora
pode levar um pouco de pensar para absorver toda esta notação. Mas no
Enquanto isso vamos olhar para alguns exemplos. Então, novamente, vamos fixar a nossa, a nossa principal a ser
sete. E vamos olhar para a ordem do número de elementos. Então, qual é a ordem
de três módulo de sete? Bem, nós estamos perguntando o que é o tamanho do grupo que
três gera módulo de sete? Bem, nós dissemos que três é um gerador de Z7 estrela.
Então ele gera todos Z7 estrela. Há seis elementos em Z7 estrela. E, portanto,
dizer que a ordem de três é igual a seis. Da mesma forma, eu posso perguntar, bem, o que é
fim de dois modulo sete? E, de fato, já vimos a resposta. Então vamos,
eu vou lhe perguntar, qual é a ordem de dois modulo sete e veja se você consegue f igura
o que esta resposta é. Portanto, a resposta é de três e mais uma vez, a razão é, se olharmos
no conjunto de potências de dois modulo sete, temos um, dois, dois quadrado e, em seguida
cubado dois já é igual a um. Portanto, este é todo o conjunto de potências de dois modulo
sete. Existem apenas três deles e, portanto, da ordem de dois modulo sete
é exatamente três. Agora deixe-me lhe fazer uma pergunta capciosa. Qual é a ordem de um
modulo sete? Bem, a resposta é uma só. Porque se você olhar para o grupo que é
gerada por um, bem, há apenas um número em que o grupo, ou seja, o número
um. Se eu levantar um a um monte de poderes, eu sempre vou ter um, E
, portanto, a ordem de 1 modulo 7 Na verdade, a ordem de 1 modulo qualquer injeção
é sempre vai ser 1. Agora há um importante teorema de Lagrange, que
realmente este é um caso muito, muito especial dele, o que estou afirmando aqui. Mas
teorema de Langrage basicamente implica que, se você olhar para a ordem de G módulo p,
ordem sempre vai dividir P-1. Assim, em nosso exemplo dois você vê,
seis divide sete menos um, seis divide seis, e, similarmente, três divide sete
menos um. Nomeadamente novamente três divide seis. Mas isso é muito geral, o seu fim é
sempre vai ser um fator de P menos um. Na verdade, eu vou te dizer, talvez seja uma
quebra-cabeças para você pensar. É realmente muito fácil deduzir de Fermat
teorema directamente a partir deste fato, a partir do teorema de Lagrange esta de fato. E assim
teorema de Fermat realmente em certo sentido, segue-se diretamente do teorema de Lagrange.
Lagrange, a propósito, que o seu trabalho no século XIX, assim você já pode ver
como estamos a fazer progressos ao longo do tempo. Começamos em tempos gregos, e já que
acabou no século XIX. E eu posso te dizer que a criptografia mais avançada
realmente usa a matemática do século XX é bastante extensa. Agora que entendemos o
estrutura de ZP estrela, vamos generalizar que a compósitos, e olhar para o
estrutura da ZN estrela. Então o que eu quero mostrar aqui é que é chamado Teorema de Euler
, que é uma, uma generalização direta do Teorema de Fermat. Assim, Euler definido o
seguinte função. Portanto, dado um número inteiro N, ele definiu o que é chamado de phi
função, phi de M, a ser basicamente o tamanho do conjunto ZN estrela.
Isso às vezes é chamado, a função de Euler phi. O tamanho do conjunto ZN estrela. Assim
por exemplo, que já olhou Z estrela de doze. Dissemos que Z contém 12 estrelas
estes quatro elementos, um, cinco, sete e onze anos. E por isso dizemos que phi de
12 é simplesmente o número quatro. Então deixe-me perguntar-lhe como um quebra-cabeça, o que é phi de P?
Ela vai ser basicamente o tamanho de ZP estrela. E assim, de fato, dissemos que na ZP
estrela contém todos ZP, exceto para o número zero. E, portanto, phi de P para
qualquer P principal vai ser P menos um. Agora, há um caso especial, que eu vou
estado aqui e nós vamos usar mais tarde para o sistema RSA. Se N passa a ser um
produto de dois primos, então phi de N é simplesmente menos N P Q menos mais um. E deixe-
me mostrar por que isso é verdade. Então, basicamente, N é o tamanho do Z N. E agora nós
necessário remover todos os elementos que não são relativamente primos com m. Bem como pode um
elemento não ser relativamente primos para m? Tem que ser divisível por p, ou que tem que ser
divisível por q. Bem, como muitos elementos entre zero e menos um m estão lá,
lá que são divisíveis por p? Bem, existem exatamente q deles. Quantos elementos
existem que são divisíveis por q. Bem, existem exatamente p deles. Então, nós
subtrair p se livrar daqueles divisível por q. Nós subtrair q se livrar daqueles
divisível por p. E você percebe que subtraído de zero duas vezes, porque zero é
divisível tanto por P e Q. E, portanto, nós adicionamos um apenas para ter certeza de que subtrair
zero apenas uma vez. E por isso não é difícil ver que phi (N) é NP-Q +1. E uma outra maneira
de escrita que é simplesmente (P-1) vezes (Q-1). Ok, então isso é um fato que usaremos mais tarde
, quando voltamos e falar sobre o sistema RSA. Até agora, esta é apenas a definição de
esta função phi de Euler. Mas agora Euler colocar esta função phi de uso muito bom.
E o que ele provou este fato maravilhoso aqui que diz basicamente que se você der
me qualquer elemento X na ZN estrela. Na verdade, e acontece que X ao poder de phi (N)
é igual a um em Z N. Assim, você pode ver que isso é uma generalização de Fermat
teorema, em particular, o teorema de Fermat só é aplicado a números primos. Para primos que conhecemos
que phi (p) é igual a p menos um, e, em outras palavras, se fosse primeiro-N faríamos
simplesmente escrever p menos um aqui, e então nós teríamos exatamente o teorema de Fermat. O
beleza do teorema de Euler é que se aplica a materiais compósitos, e não apenas
primos. Então, vamos olhar para alguns exemplos. Então, vamos olhar para cinco o poder de phi (12).
Assim, cinco é um elemento de Z12 estrela. Se aumentá-lo para o poder de cinco dos
12, que deve estar recebendo uma. Bem, sabemos que phi (12) é de 4, então estamos
levantando 5 à potência de 4. Cinco para o poder de quatro é de 625 e é um simples
cálculo para mostrar que isso é igual a 1 módulo 12. Então esta é a prova
por exemplo, mas é claro que não é uma prova em tudo. É apenas um exemplo. Mas, na verdade
não é difícil de provar o teorema de Euler e na verdade eu vou dizer-lhe que
teorema de Euler é também um caso muito especial do teorema geral de Lagrange.
Ok então dizemos que esta é uma generalização do teorema de Fermat e
, de fato, como veremos este teorema de Euler é a base da criptografia RSA
sistema. Então eu parar por aqui e vamos continuar com modulares equações quadráticas na
próximo segmento.