Fermat e Euler (18 min)

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.