Introdução a FFT - Core Program Brasil 2025

Transcript

polinômio né? Um polinômio é basicamente um cara desse jeito. É uma função que pode ser de uma de uma variável ou de mais. Aqui a gente vai considerar só uma variável. Ahã. Essa função vai ter potências dessa variável do x e na e para cada para cada uma das potências você vai ter um coeficiente. E essa é a expressão da e desse desse desse crinômio. A gente chama esse polinômio de um polinômio de grau dois. Porque a maior potência é dois.

Ah, o que importa desse polinômio pra gente, eh, na verdade são os os coeficientes. A gente não quer igualar isso a zero, a gente não quer encontrar uma raiz, a gente só quer que ele exista. Então, é p dex igual a isso. Eh, e o sueficiente, nesse caso, é 2 271. Eh, aqui eu tô sempre eh representando eles do do coeficiente do coeficiente de grau mais baixo pro pro maior. Ah, e usualmente para eh para simplificar, para economizar espaço, a gente vai escrever o polinômio como uma somatória, tipo essa daqui, em que tem a variável das potências e os coeficientes. E eu vou armazenar esses esses esses

coeficientes em algum lugar. Ah, então de forma geral, como eu falei, o um, o polômetro de grau n vai ter um eh uma uma potência n aparecendo em algum lugar com com o coeficiente que não é zero. Ah, e dentre os problemas tem alguns que são interessantes pra gente. Um deles, um tipo de de polinômio é o o é interessante é o polinômio irredutível. A ideia de de um polinômio irredutível é é um polinômio que você não consegue fator.

Então, lembrando, eh, quando a gente eh trabalha com inteiros, né? Você tem lá, sei lá, eh, quatro, você pode pode faturar 4 em 2 x 2, certo? Com polinômios, isso existe, é o mesmo conceito. Você tem um certo polinômio, você e se ele foi redutido, você não consegue encontrar dois polinômios de de grau menor, que quando multiplicar você vai contar pro original. Eh, você pode pensar nesses nesses problemas e como se fossem os primos dos, né? Isso é é é uma forçação barra. Não, não se fala isso no lugar, mas essa ideia.

Eh, eh, dentre os problemas irredutíveis, existe um eh, que é muito legal, que é são os os problemas ciclotômicos. Eh, o problema ciclotômico é é ter essa definição que você eh ele consegue dividir, tipo, então um polinômio o o enésimo polinômio ciclotônico é um polinômio que consegue dividir eh x a n - 1, mas não divide eh x k - 1 para nenhum k menor que n. Então, se você tem esse N, por exemplo, 10, eh, e você for testando o CAS, eh, de zero até, nenhum deles pode dividir, eh,

pode ser dividido por esse polinômio. Ah, um caso especial que a gente gosta muito é quando o n é uma potência de dois, porque nesse caso todos os cicotômicos vão ter esse formato aqui, vai ser o a variável de maior grau mais 1. O o legal o legal disso daqui é porque você consegue ter operações muito eficientes e em particular você casa isso aqui muito muito bem com a FFT. Eu vou eu vou explicar isso mais para frente, mas enfim, isso é é algo bem legal.

Outra outro assunto importante é números complexos. Então a gente entende que existe eh eh eu eu eu gosto de pensar nisso como uma brincadeira que que fica séria, né? Então a gente entende que existe um um certo número i que ao quadrado vai dar -1 certo? E eu escrevo um número que eu chamo de complexo, eh, que tem esse formato, o A + I x o b, onde o a e o b pode podem ser reais, são reais, né? Eh, isso daqui é uma representação simbólica. Você não quer multiplicar o I pelo B, você não quer somar nada com nada, você escreve assim, eh, porque esse é o formato que você vai,

>> mas ele não é um número >> não é minúsculo. E pô, >> brincadeira, não deu para resumir. >> Ai, ai. Enfim, continuando. Ah, o que você importa? O você você se importa aqui com uma coisa que é o A e o B. Então o A a gente chama de parte real do número complexo. O B a gente chama de parte imaginária do do número complexo. Na prática, quando você brinca com essas coisas, você implementa isso, você implementa você guarda essas duas informações certo?

A e Bs é o que importa. Ah, existem algumas operações que você define para números complexos. Eu não vou apresentar todas, eu vou mostrar adição e multiplicação quase que por curiosidade mesmo. Ah, se você tiver dois números complexos, eh, ah, então uma coisa importante, A + e B é um, um número complexo, não são dois, é um número complexo. Então, se você tiver dois números completos, A + I B e C + I D, uma adição é simplesmente você soma a parte real, o o e da parte real e soma a parte imaginária para ser a parte imaginária.

Uma multiplicação é só fazer a distributiva e agrupar cada um dos termos. Então você vai ter essa expressão pra parte real e essa expressão pra parte magnária. E é isso daí. Ahã. E ok, deos complexos, acho que é isso que é importante por enquanto, só essas definições. Dois tipos de definições que também é legal lembrar, eh, que para mim, pelo menos, é sempre muito difícil de de memorizar, então eu gosto sempre de, tipo, passar para ela de novo. Uma delas é o que que é uma uma eh uma propriedade de associatividade. O que que é uma

operação que é associativa? Então, eh, uma operação que é associativa, se você conseguir fazer esse esse esse esse esse negócio aqui, eh, A operação B e depois a operação C, é vai ser a mesma coisa do que fazer B, a operação C e depois A. Eh, por exemplo, na adição 2 + 3 e depois mais 4 é a mesma coisa de 2 eh somado com resultado de 3 + 4. Então aqui a gente tem uma associatividade. Paraa multiplicação, mesma coisa. 2 x 3 e depois xes 4 é igual a 3 x 4 depois x 2.

A outra opera o outra outra propriedade é comutatividade. Uma operação é chamada comutativa. Se você puder inverter a ordem dos dos operamos. Então, a operação b = b, operação a novo, adição. 2 + 3 = 3 3 + 2. 2 x 4 = 4 x 2. Então, associatividade e computatividade. Ah, um outro conceito que é importante são os elementos neutros, que também pode chamar de elementos de de identidade.

Um elemento é de neutro-se para um certo conjunto. Então isso é importante. o elemento ele é neutro para um certo conjunto. Se para um certo conjunto eh e ir para uma certa operação, você eh voltar pro o outro cara. Então, a o elemento neutro nessa operação é igual ao A. Ele não agrega nada, ele não muda nada, você fica sempre no A. Na adição é o zero. Eh, na na adição de reais de inteiros é o zero. Na área multiplicação é o 1. Porque a + 0 é a, a x é a.

Então, zero não são os branutos aqui. Eh, você pode ter elementos neutros completamente diferente disso para certos conjuntos. Para outros casos você pode ter elementos neutros para polinômios, por exemplo, pode ser bem maluco. Ah, e o último, a última, a última definição que eu vou mostrar é são o as inversas, né? Então, de novo, para uma certa operação, um certo conjunto, um elemento é dito eh é é chamado de inverso. Se um a vezes esse elemento você chega no elemento neutro.

Então, pra adição, se você tiver o a, a inversa vai ser o - a, o elemento neutro que é zero, né? Para a multiplicação a inversa vai ser 1 sobre a. Eh, sendo aqui, na verdade, eu tô me deixando ser bem pouco formal, porque esse 1 sobre a pode ser coisas diferentes. Eh, mas existe uma inversa que vou explicar pelo ar. Eh, no caso aqui seriam seus reais, né? Se for centro vai ser é outro assunto. Mas enfim, os reais. Ah sim.

Legal. Sabendo essas coisas, agora eu vou definir quatro estruturas. que são são importantes de lembrar. A primeira mais básica é um grupo. Eh, um grupo ele é uma um conjunto que é relacionado com uma uma operação. Então, um conjunto um grupo não existe processó, ele tem que tá associado com uma uma operação e ele tem que ser associativo, tem que ter um elemento neutro e todos os elementos desse grupo tê que ter um inversa. Se você tiver isso, eh, isso é um grupo. Se além disso, eh, você tiver eh, a, a, a comutatividade, então esse grupo

é chamado de abeliano, né? Um exemplo são eh o os inteiros com adição. Eh tem tendo um grupo, você consegue construir um chamado anel. Eh, o anel é um grupo abeliano para adição, que além da adição também tem uma uma multiplicação associativa. Eh, você tem a o o elemento neutro para multiplicação, né? E você tem essa propriedade aqui da da distributiva, estamos inteiros. Então, percebe para eh

paraa adição eu preciso ter mais coisas do que para para multiplicação. Para pra adição eu tenho um grupo abeliano para para multiplicação não necessariamente, isso é um anel. Isso. Ã, outros dois ou quase, sei lá, 1 e meio estruturas que são interessantes é o corpo. Em inglês eu chamo de fo. Eh, o corpo ele é um conjunto que eh é é um grupo abeliano para adição com um certo elemento eh neutro, pradição.

Ah, tirando o elemento neutro, você também é você também tem o também é grupo abiliano pra multiplicação, para multiplicação, certo? É com um setor eletrônito neutro e a I, sei lá como chama isso, né? Ah, e isso implica que todos os elementos, tirando o neutro, tirando o neutro aditivo, tem uma inversa, né? e a distributiva se mantém. Então, então você vê um corpo é um um anel mais restrito, né? Você também condições para a modificação além dessa associatividade.

Se esse corpo ele tiver o número eh finito de elementos, a gente chama ele de corpo finito, né? ou de corpo de galoço, você vai encontrar em ambos lugares. >> Eh, os os corpos finos eles são muito usados em em criptografia porque eh para você provar certas certas certas propriedades, você tem que ter ali um certo limite de range, né? Ah, em particular para FFT. a a FFT você você você constrói ela usando cartos finitos ou ou pode ou pode pelo menos construí.

>> Ah, tendo isso, um outro eh o agora a gente começa a brincar com coisas mais negativas. Então, existe um conceito chamado raízes raízes primitivas, né, que elas são eh calculadas em cima de um certo P. Aqui eu vou considerar só primos, né? Então, se P for um número primo, né, existe um certo número G no corpo finito ZP. Z aqui são os números inteiros que vão de 0 até p - 1. Então vai ter 0 1 P - 1. Isso forma o corpo finito. G é chamado de uma raiz primitiva de P.

Se você você se a hora que você começar a calcular as potências de G de eh um até até p - 1, eh você vai acabar encontrando todos os inteiros de zer de de 1 até p - 1 nessa e nessa conta. Então, por exemplo, se eu considerar o primo sete, certo? Ia pegar o número 3. 3 elevado a dar 1 vai ser 3. 3 elevado 2 vai ser 2. 6 4 5. Então eu tenho aqui 1 2 3 4 5 6. Eu encontrei todos os inteiros de um até seis nessa nessa exponiciação.

>> Pedro, eh, um uma raiz primitiva e um gerador são a mesma coisa ou mesma coisa? são são sinônimos, mesma coisa. P que eu acho que não são sinônimos, eu acho que eh a responsiva pode assumir pode eh ser um pouco mais mais flexiva, mas nesse contexto acabam sendo sendo sinônimos, >> tá? Obrigado. >> O que você encontra é isso daqui, é o que chama de um subgrupo cíclico. Eu como que isso é é traduzido você consegue ir caminhando, sabe por todos os esses inteiros de uma T-1. E se você continuar e essa exponenciação, você volta pro pro primeiro caso, você

tem um ciclo, certo? Ah, por obesidade, a gente chama isso aqui de um círculo de ordem seis, porque você vai ter que eh porque você volta pro um depois que você eh depois que você chegar na eh em três elevado a 6, depois 6 a 12, por aí, né? vai gerar por TR. Se você pegar esse conceito de uma raiz primitiva e você levar ele pro eh para um anel ou um corpo, pelo menos, você consegue definir um certo elemento ômega, eh, que ele é chamado de uma raiz enésima, eh, uma raiz enésima da unidade.

Se esse elemento ômega, depois que você multiplicar ele n vezes, ou seja, calcular ô elevado a n, você encontra um. E esse e um no caso sendo um um elemento desse desse anel ou desse corpo. Então o ômega vai ser uma raiz, desculpa, vai ser uma raiz enésima da unidade, se isso for verdade. E ela vai ser uma raiz uma raiz uma raiz enésima primitiva da unidade. Se além disso eh isso aqui não for verdade para nenhum K menor do que n. Então você pega o ômega, você eleva n, você tem um, você testa todos os elementos eh de 1 até n - 1 e nenhum deles dá um.

Então, então ele é equitivo. Ah, uma uma curiosidade é que se você encontra isso, esse ômega, você tem como resultado que necessariamente eh o o ômega ele vai ser um gerador, vai gerar um subgrupo cíclico. Então, todas as as potências de de ômega de 0 até n - 1 vão ter aqui essa cara. Ah sim sim necessariamente. Ah, você pode construir essa essa essa raiz.

Eh, isso é é uma que eu acho bem importante. Você você não uma única maneira de você construir essa raiz. Você pode construir essa raiz usando qualquer corpo. Ah, a FFT vai trabalhar com os complexos, mas você pode construir com números com com cortes finetas, você pode construir de outras maneiras. Eh, então isso e generaliza muito o que o que a gente vai ver daqui paraa frente. >> Eu digo, necessariamente ele é cíclico, né? Necessariamente ele é um subgrupo cíclico, >> tá? Se essas duas condições for forem satisfeitas, >> tá?

>> Legal. Agora agora no e no mais para frente. Então, na escola a gente aprende fazer eh multiplicação eh polinomial, né? Então, para uns eh para dois polinômios aqui, eu vou sempre considerar polinômios que t o mesmo grau. Você pode considerar que se você quer fazer uma uma multiplicação do polinomio de grau de um polinômio que tem grau que tem graus diferentes, uma sei lá 10, outro é cinco, você pode pôr um pading aí no cinco e chegando no 10, tá? Eh, ao menos na representação de coeficientes, você vai encher de zeros e também você vai ter lá 10 elementos de um lado e do outro.

Eh, o produto desses dois polinômios, né, vai ter essa cara, né? Então, o grau vai aumentar de de n vai para 2n - 1. 2n - 1. É isso? Acho que sim. Fica confusivinho. O grau vai se somar, certo? Eh, isso vai ser 2 e - 1. Ah, e os coeficientes desse desse produto vão eh cada um desse, desses CS vai ser calculado como essa somatória aqui. Então, se você imaginar que esse K eh vai de 0 até 2n - 2, isso aqui tem uma uma complexidade quadrática da que eu

falei. Isso é muito ruim, né? Porque o pode ser muito grande e você vai levar um ano para para essa conta. E você tem que que pensar que uma uma multiplação uma multiplicação polinomial não é a não é a atividade fim. Você tem ela como um step no meio de um monte de coisas. Você quer que aquilo seja muito rápido, né? Eh, para pra gente lidar com isso de uma maneira mais eficiente, a gente usa o conceito de uma transformado. Uma transformado é simplesmente um processo que vai converter uma coisa em outra.

Eh, de forma que quando convertido essa outra coisa vai você vai expor uma uma estrutura que tá que tá ali dentro matemática, que pode escondida no no original. Ah, isso isso pode ter vários significados. pode ter um significado matemático, pode ter um um significado físico. Eh, eu já ouvi falar sobre gente usando esse esse tipo de coisa para processar sinal de áudio. Enfim, eu não vou me importar com nada físico aqui. Eh, eu só vou vou me importar com o que eu consigo obter usando eh e eh esse conceito para para polinômios, né?

Então, existe um certo tipo de de transformada que a gente gosta, que é a transformada discreta de Furrier, a DFT, né? E a DFT tem a a eh tem a seguinte estrutura. Então, suponho que eu tenho um ômega, que é uma raiz enésima primitiva da unidade, certo? Ah, eu se eh e eu tenho um certo vetor y certo que vai de que tem n tem n elementos tô contando de zer até n - 1. Ahã. Se eu construir essa matriz que chama a matriz de Vandemonte, em que cada elemento dela é é uma potência de ômega, então a primeira raiz, a primeira

linha é são as potências zero, né? A segunda e vai ter zero, vai ter ô elevado a 0, ô elevado a 1, ô elevado 2 até n - 1. A terceira linha você vai dobrar essa esse esse essação. Vai de 0 2 4 vai até o último elemento que é o ôga elevado a n - 1². Eu pego essa matriz e eu multiplico pela minha entrada, né? Então, lembrando, uma m uma multiplicação polinomial, nesse caso, você vai pegar a linha da da da matriz nesse formato, né? vai multiplicar pela sua entrada elemento

elemento e somando o resultado. Isso vai te dar x0 depois x1 elevar. Eh, se você faz isso, você vai ter eh você vai tá efetivamente eh eh fazendo a avaliação do seu polinômio para potência de ômega. Então você vai eh pegar cada uma das n potências de ômega, você vai eh colocar no você você vai avaliar o seu polinômio para essa potência e esse vai ser o seu vai ser aqui o vai ser o certo que vai ser eh desculpa, então eh pro jésimo pro pro

jficiente da sua saída, eh ele vai ser calculado a partir do da avaliação do seu pronômio pro jimo, potência de ômega. Certo? Então, então você vê, tipo, são várias adições, várias eh adições também, várias várias várias bem caro. Eh, isso e essa vai ser sua sua saída. Nesse contexto você vai ter eh você vai construir o ômega geralmente, como aqui esse cara que é o e que é o número nepeliano elevado a 2 pi I sobre m.

Então isso aqui é umação, uma exponênciação complexa. Eh, você como que você calcular isso? Não importa. Eh, mas isso e esse e e você pensa nisso como um número, ele existe. Você vai armazenar ele em algum lugar. Na prática, você vai armazenar essas essas potências. Eh, e quando você for ler sobre implementações baseadas nisso, ess ess essas potências são o que chamam de twidles, são os twidles factors. Ah, então um exemplo prático para quem gosta de números, né?

Suponha que você tem aqui essa esse vetor de entrada 1 2 3 4. >> Ah, o M aqui vai ser 4. Então o seu ômega vai ser I, certo? Essa é a sua matriz de o essa essa multipção que nem expliquei, né? Então, pro primeiro elemento, o x0 vai ser simplesmente quando eu coloquei todo mundo é um, você soma todo mundo 10. Depois tem esse i -1 - i muda um pouquinho. Tem que lembrar aquela aquelas quantidades de adição e e multiplação que eu falei.

Você agrupou o a parte real, agrupa o parte imaginário, -2 + 1 e foi aí vai. Pronto. Então, tendo esses essa entrada que você pode pensar que são coeficientes de um polinômio, essa vai ser esse vai ser o formato do seu do eh daquele polinômio no domínio de forrire. E o que que é legal nisso? Suponha que eu tenho dois polinômios A e B, que estão no que a gente chama de domínio padrão, é o jeito que eles chegam para você. E você quer multiplicar esses dois.

Isso. E isso bem que você quer multiplicar esses dois. Eh, a primeira etapa seria você aplicar a a a DFT em A e depois em B. Eu vou ter aqui agora A expresso no domínio de furriero e B expresso no também no domínio de furriiro. Como eu falei, nesse domínio você consegue calcular uma o equivalente a essa multiplicação polineial simplesmente fazendo uma multiplicação coeficiente a a coeficiente muito mais simples, muito mais rápido.

Pronto, você fez. Agora você tem que ser no domínio de carreira. você aplica matriz chamada inversa da FT, que é basicamente você eh calcular a inversa da matriz de valor longe. Ah, e pronto, o resultado vai ser C, que é exatamente A x B, certo? Ah, o problema disso daqui é que, como dá para imaginar, eh, ADFT é como você tem que construir aquela matriz, né, N por n, ela é muito cara, você paga eh n quadrado para você para você fazer a aquela conta, além de que seria

extremamente caro para você armazenar todas aquelas aquelas potências. Eh, então, na prática, você não usa isso em em lugar nenhum. O que você faz? Você usa a FFT. A FFT eh, eu penso mais nela como um algoritmo mais do que uma transformada, porque ela, na verdade, tá aplicando a área FT internamente. E ela é chamada de rápida porque em vez dela eh ter esse custo eh quadrado, ela vai ter uma uma complexidade muito menor de OGM.

E ela faz isso quebrando o seu problema em tipo em tipo problemas menores. Então você tem o seu problema grandão que você quer aplicar de FT nele, você vai quebrar ele tipo em dois, depois recursivamente quebrar cada parte em dois de novo, em dois de novo, de novo, até que você chega embaixo com pequenos, de grau muito pequeno, e aí sim você aplica afft em cima deles. Ah, a geralmente a gente gosta de fazer isso quando o n é uma potência de dois, porque quebrar o sobrenome em partes menores de dois em dois, se se não for dois, vai ser mais difícil. Eh, isso não é isso não perde generalidade, porque de novo você pode sempre pôr um pad no final e aumentar os seus os seus

coeficientes né? Eh, e isso é o que faz o toda essa vendadeira ser relevante, porque se a gente tivesse que trabalhar com o DFT, não faria nenhum sentido, porque se você tiver que calcular uma DFT ou só fazer aquela scolbook e multiplication, você faria só aquela multiplicação porque é mais fácil aí. Isso é eh essa essa estratégia aqui eu só dei uma uma ilustrada é é a famosa dividir para conquistar, né? Então você tem aqui o seu polinômio P de grau N e E e e N - 1 na verdade, desculpa.

Você vai usualmente quebrar ele em partes eh eh pegando o primeiro eh pegando os coeficientes, os coeficientes de potências pares e os coeficientes de potências ímpares. Então, nesse caso, você teria dois polinômios eh com os coficientes a 0, A2, A4, por aí vai. e um outro polinômio com com coeficientes A1, A3, A5, certo? É, é fácil ver que que essa essa somatória aqui vai voltar para B original, certo? Mas aí você chega aqui e você aplica a DFT aqui, ou melhor a a FFB aqui e depois aqui de novo e repete.

Até aqui você termina com o polinômio que é que tem grau um, né? Tem só tem só o o coeficiente de zero. AFT desse cara é esse cara não muda. E aí você volta o nível e aí você vai você vai aplicar a FTM de de de grau um, certo? E aí você, se você conseguir um algoritmo que eh eh faça essa volta de forma eficiente, você você vai chegar naquela naquela complexidade de de n que eu falei. Por que que é x² e ped p dex = p even de x² + x p de x²? O que que é x qu? Eu não consegui ver.

Ainda tem o X antes multiplicando, né? >> Sim. Eh, >> tá, mas tem uma ordem três. >> É, é porque você eh, OK. Esses, >> o que que é amarrado? >> Você tem esse esses esses esses dois esses dois problemas, mas você tá trabalhando com P para você e se você pega aqui e o Pivan e você avalia ele para x², aqui vai ficar a0 A2 x² a 4 x x, certo? >> Uhum. Uhum. E o mesmo pro e e no caso do ódio, você vai ter o A1 + A3 x², certo? Só que aqui você tá multiplicando o ódio, por x de novo. Então você vai ter a 3 x x³.

>> Uhum. É para te dar o zero. >> E aí você volta pro P, >> tá? >> Tá. Eh, enfim, essa essa é a ideia. Eu não vou apresentar esse algoritmo, acho que o o Bartosa vai ter esse prazer. Eh, mas quando você eh enfim, eu queria mostrar da onde que isso vem, como que isso isso isso construído e para que isso existe. Agora, coisas legais que você pode fazer com isso. Eh, não sei quem quem que tá familiarizado com eh criptosistemas baseados em reticulados, mas isso é o basicamente o que a gente usa em FHI hoje em dia. Tipo, todo o o os principais esquemas são são baseados

nisso, né? E esses esquemas geralmente definem um RQ, que é essa coisa aqui, tipo e o corpo finito eh eh zqu, então inteiros. de 0 até que -1 para um certo q primo. Ah, e esse cara aqui é o enésimo ciclotômico que eu eh que eu que eu citei lá atrás. Então é um polinômio irredutível que não vai dividir ninguém, eh, nada que tenha uma potência melhor do que n, enfim, a há aquela definição.

Eh, isso, esse RQ é um eh um anel ah de polinômios em que os coeficientes estão em ZQ e o grau máximo do polinômio é R -1, tá? Então, e RQ tem tem polinômios. Ah, quando você faz uma uma sempre verdade que o esse polinômico esquilofônico, ele vai dividir o o polinômio de ZQ, porque ZQ é são os inteiros do zero de zer a a a -1. Eh, ZQ vai ser você você você pode pensar como ZQ como o corpo duas dos coeficientes.

>> Sim, sim. É, mas aí você tá, >> é uma divisão isso só para >> É uma divisão. Você não faz essa conta, mas é uma divisão. >> Sim, mas a gente então a gente tá assumindo que vai ser sempre divisível. Isso é verdade, >> não? Eh, eh, e isso, isso daqui é acaba sendo simbólico, você não vai dividir conjuntos tá? >> Eh, isso e isso aqui tá te dizendo o o corpo dos coeficientes e o corpo do dos polinômios. É como fosse um racional nesse sentido. É, tá, tá mais como eh uma maneira de escrever, tal. É, é uma, é, tá mais para uma uma maneira de escrever quando você faz ou para exemplo modulares, você eh

sempre tem que calcular o módulo dos resultados, certo? É porque é uma modular. Aqui o módulo você vai calcular o módulo RQ e aí você vai ter que dividir eh o RQ tem polinômios. Então você então você vai ter um polinômio que você vai ter que dividir pelo prototômio. E >> isso você vai fazer. >> Uhum. >> Certo? Ah, e os coeficientes você vai ter que calcular o módulo de is aqui. Mas é isso, é isso que tu fala. É isso que essa que essa locação fala. Ah, é do mesmo modo, né? >> Ã, o L, o L e a gente gosta dele como como potas colotônicos tenha essa cara. Existem outros colônicos para outros ns. O modo de calcular eles é uma malquice e

ninguém faz isso, mas eles existem. Mas aqui ele vai só sóar o n de dois. Ah, então então então então então então como disse, você tem as suas operações, você vai calcular a sua multiplicação polinomial em RQ, o seu, os operadores em RQ e a saída você teria que calcular o módulo eh o seu ciclotômico. Ah, mas o seu o seu ciclotico tem essa cara. E se você usar a AFFT, você tem uma uma vantagem que é a saída da AFFT já tá eh módulo RQ. Opa, que que eu fiz aqui? Socorro. Isso já tá o módulo RPQ.

Você consegue essa redução de graça, você não gasta nada para isso dentro do dentro do domínio de fora. >> Uhum. >> Então eh existem várias maneiras de você várias maneiras de você fazer umação colamial. Você pode usar os cobux, você pode usar FFT, você pode usar caratsuba. Existem certos graus eh que você pode que que certos graus de produtos que fica mais caro você fazer uma FFT do que você usar caratsuba, por exemplo. Mas caruba não vai dar isso, que é essa essa redução de graça.

Ah, e é por isso que o que FHI adora usar FFT nas suas nas suas nas suas explicações, tá? Abri, tá? Ó, calma. Eh, eu tenho duas dúvidas. A primeira talvez fuja um pouquinho do tema, mas é o um esquema de FT é tipo um oke é um grow 16 plonk ou porque esquema, esquemas em ZQES não tem esses esquemas certo?

>> Eu não conheço eh falou, >> tá? O o que que é um um esquema assim sem que >> ó >> o que eu sei aqui, ó, falta tem que descer muito. >> Eu eu vou te responder que eu acho que sim. Eu acho que que é a minha ideia. Eh, FHE é um conceito, né? Eh, o esquema é uma maneira de você implementar esse conceito. É um é um algoritmo, >> é o que faz tornar criptografado uma antena de propriedades de só uma multiplicação. Isso é o que esquema faz ou >> sim? Sim, tipo, eh, por exemplo, o o AES é um esquema, é um esquema criptográfico, o RSA é um esquema criptográfico, >> né? Eh, esquemas que têm a a propriedade homomórfica são esquemas FH, mas são

esquemas criptográficos. >> Ah, >> o, na verdade, RSA é um esquema que pode ser um esquema homórfico, não é FHE. >> Isso é tipo, não necessariamente é F, né? >> Não, não, F, >> porque tem o he part ali, não sei o quê, Sam, não sei o quê. Tá beleza. E esse lets B base base, ele tem alguma relação com post, certo? >> Sim. >> Ah, >> tá aí na na no contexto? Não, >> não. >> Tá. Então, beleza. Não, beleza. Então, sim, sim. Não, assim, tipo, eh eh e e esquemas LS baseados em particular, eh eu não sei dizer se todos são, mas os esquemas que

que a gente trabalha hoje são todos resistentes a ataxônicos. Justo, justo. >> Resistente aqui, desculpa, >> a ataques quânticos, ataques de de computadores quânticos, né? Eh, então isso é um é um é um trabal deles e além disso eles também são FE, por isso que a gente gosta deles. Existe existem existem eh existem esquemas eh baseados em reticulados que não são FH isso, >> mas o RQ >> a vantagem então do FHE é justamente isso de ser rápido >> e eficiente por conta da transformar.

>> Não, eles não eles eles não são rápidos. Eles olha, esse esse tipo de coisa faz eles serem mais rápidos. >> Em geral é é que FHE, tipo, não, eu não tô falando sobre sobre FHE aqui, mas eh em geral esquemas FHE são menos. >> Ah, tá. Tipo, >> acho que o F de FH é de full. >> É de fúri. É, é o melhor, é o melhor que tem. É o melhor group, né? Não >> é, é, é. Então é isso, isso tá, isso tá bem fora do escope, mas sim, sim, sim, sim. É o o F vem de fúx que significa que você tem um esquema que você consegue aplicar adição e multiplicação quantas vezes você quiser na naquele naquele criptograma. Os esquemas hoje são plentes.

>> Eh, a gente tá brigando para fazer isso porque ficarem mais rápidos, né? O Mas eu diria que a parte de tipo baseado em reticulados aqui é um é um bônus. Entendi. >> Top. Beleza. É, não, essa par de H aí a gente vai discutir hoje 4 horas da tarde. 4 hor. >> Beleza. Beleza. >> Boa. >> Joia. >> Boa. >> Então, legal. Agora, eh, duas últimas curiosidades aqui que eu acho que é legal citar. Como eu disse, o, eh, o a gente constrói a DFT usando aquele ômega, que é uma raiz enésima primitiva, na verdade. O, você não precisa usar só os complexos para construir aquela raiz genés nutriade. Você pode usar outros corpos, outros anuais. né? E existe um

negócio que chama MTT number transforms então em vez de você usar os complexos, você usa eh ZQ. Então você tem de novo ZQ, corpo finito. Você eh e e do COQ você vai encontrar uma uma raiz eh em ZQ, né? E uma maneira de fazer isso é suponha que que tem esse formato, então para um certo n, que é o tamanho desse polinômico que você vai aplicar na transformada, >> existe um K tal que isso aqui é verdade, né?

E existe um um R, eh, que é uma raiz primitiva, não é nésia, mas é uma raiz primitiva, que eu não vou falar como que você encontra esse cara, mas ele existe, né? você e consegue definir a que uma uma generalização da FFT em ZQ. Então você eh tendo o esse R e esse K, você consegue construir a raiz enésima, o ô n simplesmente calculando essa experiência R elevado a a K modulo Q. Agora você tem a sua raiz enésima e você consegue eh definir a TTT. AT funciona exatamente igual a FFT, as mesmas operações, mesmo conceito. Você você pode inclusive definir uma o uma défesse jeito. Não sei

porque faria isso, mas você pode fazê-lo, né? Eh, e a e a vantagem, vou dizer assim, é de que em vez de você trabalhar com complexos, você você você agora trabalha comos para critografia. Isso pode ser legal porque, como vocês sabem, eh, complexos, quando a gente, né, trabalha com com contadores, você usa ponto flutuante. Ponto flutuante tem um erro intrínseco. Quando você usa FFT no esquema criptográfico, você tá inserindo ruído dentro do seu do seu criptograma, você tá inserindo e eh um erro ali que pode ser significativo, você pode não querer fazer isso. Ah, eh, no caso, por exemplo, e um exemplo, eu eu trabalho

muito com TFHE, que é um esquema FHE. Em TFHE você tem que, eh, se você usar a a a FFT, você perde você perde a precisão. Você precisa ajustar os parâmetros para você recuperar uma uma precisão bits, você perde a informação por conta da FFT, por conta do tanto de erro que que acumula ali com a EDT. Isso não acontece. Eh, se você pensar aqui o em uma multiplição polinomial de inteiro de de polios com coeficientes inteiros, se você quer que os estados sejam inteiro, mas se você fez a conta em concreto, você vai ter que fazer sempre um rounding com NDT. Você não tem que fazer isso, >> né? Uhum. Ah, isso pode ser bom se o seu hardware eh for conveniente. Então,

tipo, eh, existem hardwares em que eh a as instruções pflutuantes são muito mais eficientes do que inteiro. Então, você então você não vai querer usar inteiros. Existe hardware que vai ser a mesma coisa. Existe hardware que inteiro, na verdade é, pode ser bom. Ah, enfim. E aí, e aí nesses casos pode ser interessante utilizar o DT. >> Isso é o caso, trabalhar com cuda. >> Sim, >> né? com eh com cudo, não >> é? Cuda, >> é. Tá bom. O que que é mais interessante para você trabalhar com qual tipo de transformado?

>> Depende. >> Depende do domínio. >> Depende. Eh, isso, isso, isso eu ia comentar daqui de um minuto, mas desculpa. >> Eh, continuar. É, deixa só eu eu falar o pass slide, tá? Eu eu eu con isso em zero. >> Se você for generalizar ainda mais, você consegue fazer você consegue encontrar esse aquele ômega em um corpo de galoá nesse formato >> aqui. Eh, então você e isso aqui é o inteiro de galo o um inteiro de galoá eh tem um formato muito parecido com o número complexo também uso o I. Só que agora no interior de galá você tem o A e o B e elementos

de um ZQ. >> Não é um número complexo. >> Não é um número complexo, é o inteiro de gal. Ah, >> caramba. A a maioria da tá cheirando neutro. >> Todas as todas aquelas aquelas operações que eu cometei valem aqui. Eh, isso é legal. Eu não vou faço preço, mas isso que existe. >> Esse aí é é o quant? Ah, meu Deus. Esse aí é o quê? >> É um complexo. Não, judí >> é complexo.

>> É um é um é você pode você pode pensar no interá como como um subconjunto do duas complexos. O A e B aqui são inteiros. Ele nunca nunca vai ser, por exemplo, o múltiplo da raiz da uma raiz anes daagem, mas >> não, ele ele não vai ser o múltiplo da raiz 10 modalidade. >> É isso. >> É tipo e nisso aqui você vai ter você vai usar os mesmos e bem, >> não é? É, >> mas o Z, o ZQ não é ali.

>> O ZQ não tem um I ali dentro não. Não. ZQ são inteiros de zer aqui- 1. >> A e B são menor esses inteiros. >> O I é complexo. O Z é o integral A. >> Tá. Qual que complexo? >> Ah, o A e B tem que ser núos complexos. OB pode ser eh o IP são perfeitamente. >> Então você é é mais limitado, mas a vantagem falando sério. >> Isso aqui acaba sendo uma uma curiosidade. Por quê? Imagina que você tá aplicando a sua transformada em em cronômetro de grau 1024.

>> Na NTT você teria que que calcular umaada de 24. Na BGT para você construir o você dobra o seu polinômeto. Então às vezes você trabalha com 1024, você trabalha 151. >> E isso pode ser interessante >> de novo. Depende do hard, porque você agora vai agora quando quando você for carregar o coeficiente, você vai você vai carregar A e B, >> né? Se você tiver banda para isso, pode ser interessante. >> Aí vem a a pergunta que você fez, quando quando que isso, tipo, qual deles é melhor? E a resposta é depende.

Ah, eu vejo, tipo, artigos discutindo FFT, NTT e até DGT faz muitos anos. E na minha opinião nunca realmente alguém eh fez uma comparação real, tipo, muito válida sobre qual que é melhor. Tem gente que assume que é FFT, tem gente que assume que Ntt, >> eu não consigo apostar em nenhum deles tipo de de caso geral. O dinheiro depende idealmente, se você tiver tempo e dinheiro, você vai implementar sua solução usando FFT e nttamente DGT. Ah, e ver qual que é mais rápido. Na prática, o que o que se faz é é acabar sendo quase que religião. Você tem além alguns que que implementam RFT e fala que é mais rápida, alguns implementam NPT que falam mais rápida.

Eu faz duas semanas que eu revisei um paper e o pessoal falando que tinha implementado a eh eh FFT porque ela é claramente mais rápida. Eu falei, >> assumiu isso. Assumiu. >> Claramente trivial. É fácil ver que é fácil ver. >> É fácil ver que é >> depende. Como exercício para exercício. E era isso daí. Eu espero que eu tenha espero que eu tenha ajudado um pouquinho aí. Agora vou passar a bola para aqui não apareceu, não sei por, mas eu eu mandei esses slides no Discord, eu coloquei como referência algumas coisas que interessantes, entre elas minha tese de minha minhação de mestrado

[Música] joia. Ah.