anais-vjornada2016

Prévia do material em texto

Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Anais da V Jornada da Informação
Evento com apoio da FAPESP e FAPERP
Realizado nos dias 13 e 14 de outubro de 2016
Coordenação: Antonio Aparecido de Andrade
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
O Critério da Diversidade Produto na Construção de Códigos
Carina Alves 1
Departamento de Matemática, IGCE - Unesp, Rio Claro - SP
Eliton Mendonça Moro 2
Mestrando em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 3
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 4
Resumo. Existem vários tipos de códigos de bloco espaço-tempo para duas antenas trans-
missoras [1]. Neste trabalho apresentamos como projetar códigos de bloco espaço-tempo em
termos do critério da diversidade produto e para isso utilizamos os corpos quadráticos.
1 Resultados
Através da Teoria Algébrica dos Números códigos com diversidade máxima e altas
taxas de śımbolos de informação foram propostos em [3], [4] e [6]. Ao mesmo tempo,
outros tipos de códigos com diversidade máxima e altas taxas foram desenvolvidos em [5],
baseados em álgebras de divisão.
No estudo dessa teoria estes dois critérios recebem mais atenção do que o critério da
diversidade produto que é frequentemente chamado na literatura de ganho de codificação
ou distância produto mı́nima. Com isso, outros códigos de bloco espaço-tempo tem sido
desenvolvidos levando em conta esse último critério [7], [8].
Apresentamos códigos ótimos em termos do critério da diversidade produto para canais
MIMO 2×2 usando corpos quadráticos. Esses códigos possuem diversidade máxima, taxa
total e determinante não-nulo.
Referências
[1] G. Wang, J. K. Zhang, M. Amin. Space-Time Block Code Designs Based on Quadratic
Field Extension for Two-Transmitter Antennas. IEEE Transactions on Information
Theory, 58 (6) (2012).
[2] Giraud, X., Boutilon, E., Belfiore, J. C., Algebraic tools to build modulation schemes
for fading channels, IEEE Transacions on Information Theory, 43(2) (1997) 938-952.
1carina@rc.unesp.br
2elitonmoro@hotmail.com
3andrade@ibilce.unesp.br
4Agradecimentos Processo FAPESP: 2013/24956-6
2
[3] M. O. Damen, A. Tewfik, and J.-C. Belfiore, A construction of a spacetime code based
on number theory, IEEE Trans. Inf. Theory, 48 (3) (2002) 753-760.
[4] M. O. Damen and N. C. Beaulieu, On two high-rate algebraic space-time codes, IEEE
Trans. Inf. Theory, 49 (4) (2003) 1059-1063.
[5] S. Galliou and J. C. Belfiore, A new family of full rate, fully diversity space-time codes
based on Galois theory, in Proc. Int. Symp. Inf. Theory, Lausanne, Switzerland, Jul.
5 (2002) 419.
[6] X. Ma and G. B. Giannakis, Full-diversity full rate complex-field space-time coding,
IEEE Trans. Signal Process., 51 (11) (2003) 2917-2930.
[7] H. Yao and G. W. Wornell, Achieving the full MIMO diversity-multiplexing frontier
with rotation-based space-time codes, in Proc. Allerton Conf. Commun., Cont., and
Computing, IL, (2003) 400-409.
[8] G. Wang and X.-. G. Xia, On optimal multi-layer cyclotomic space-time code designs,
in Proc. Int. Symp. Inf. Theory, (2004) 318-322.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Uma nota sobre reticulados
Carlos Roberto Lopes Vicente 1
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 2
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP3
Resumo. Em sistemas de comunicações o objetivo é transmitir dados de uma fonte até o
usuário. O meio usado é chamado de canal, que pode ser com ou sem fio. Na transmissão o
canal pode gerar distorções e o sinal recebido pode não ser o enviado. A teoria dos códigos
corretores de erros surgiu por volta de 1940-48, com os trabalhos de Shannon, mostrando
que encontrar bons códigos é equivalente a encontrar empacotamentos esféricos densos no
espaço euclidiano. Como curiosidade, temos que para as dimensões 2 e 3, os melhores em-
pacotamentos esféricos são conhecidos de todos e aparecem em lugares inusitados. No caso
bidimensional, os favos das colmeias, onde as abelhas depositam o mel, e para o caso tridi-
mensional, o empilhamento de laranjas, que é facilmente encontrado em feiras livres. Nesse
sentido, nesse trabalho apresentamos o conceito de reticulados enfocando seus principais
parâmetros como volume, densidade de empacotamento e densidade de centro. Por fim,
apresentamos alguns exemplos de reticulados e de empacotamentos.
Palavras-chave: Empacotamento esférico, Densidade, Reticulados.
1 Resultados
A teoria de códigos surgiu no ińıcio da década de 50, como parte complementar de um
trabalho teórico do matemático americano Claude E. Shannon (1916 - 2001), que em 1948
publicou uma série de resultados estabelecendo os limites teóricos para uma comunicação
confiável.
Um dos principais problemas quando se deseja transmitir alguma informação é garantir
que esta chegue intacta ao destino, ou seja, que os dados recebidos sejam confiáveis. Como
dependemos de instrumentos eletrônicos para essa transmissão, sempre estamos suscet́ıveis
aos erros e às falhas desses instrumentos ou a erros dos canais em que estas informações
transitam.
Quando se deseja transmitir uma mensagem por um canal de comunicação, este po-
dendo ser um cabo, circuito integrado, canal de radiofrequência, entre outros, os dados
1crlvicente@hotmail.com
2andrade@ibilce.unesp.br
3Agradecimentos a Fapesp - Processos 2015/20595-4 e 2013/25977-7
2
percorrem o seguinte trajeto: sai da fonte, é codificado, passa pelo canal que possui rúıdos,
é recebida e codificada chegando ao destino. Vejamos o diagrama:
Fonte → Codificador de Fonte → Codificador de Canal
↓
Rúıdo → Canal
↓
Destino ← Decodificador de Fonte ← Decodificador de Canal
A Teoria de códigos corretores de erros surgiu da necessidade de detectar e recupe-
rar a mensagem enviada ao receptor e com isso poder construir códigos com pequena
probabilidade de ocorrerem erros.
Um dos bons parâmetros para se encontrar bons códigos corretores de erros está ligado
ao problema do empacotamento de esferas, que surgiu a partir do 18o Problema de Hilbert,
que é uma forma de dispor esferas no espaço euclidiano de modo a cobrir a maior parte
do espaço. Este problema, é denominado de empacotamento esférico e, quando o conjunto
de centros das esferas formam um subgrupo discreto do Rn então estes empacotamentos
passam a se chamar empacotamentos reticulados.
Apresentaremos a definição de reticulado e seus principais parâmetros como volume,
densidade de empacotamento e densidade de centro. Além de apresentarmos alguns exem-
plos de reticulados e de empacotamentos, com foco nos melhores empacotamentos esféricos
para as dimensões 2 e 3.
Referências
[1] [1] J.H. Conway; N.J.A. Sloane, Sphere packing, lattices and groups, Springer-Verlag,
New York, 1999.
[2] P. Samuel, Algebraic theory of numbers, Hermann, Paris, 1970.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Quantização de coeficientes de canal via códigos reticulados
provenientes de corpos ciclotômicos Q(ζ3s)
Edson Donizete de Carvalho 1
Departamento de Matemática, Feis - Unesp, Ilha Solteira - SP
Miller Acosta Osorio 2
Aluno do Programa de pós-graduação em Engenharia Elétrica, Feis - Unesp, Ilha Solteira - SP
Jozué Vieira Filho 3
Engenharia de Telecomunicações -Unesp, São João da Boa Vista - SP
Resumo. Por meio da teoria algébrica dos números propomos um eficiente método de
quantização de coeficientes de um canal de comunicação . A quantização dos coeficientes
de um canal será realizada através de cadeias de códigos reticulados definidos sobre o anel
de inteiros Eisentein-JacobiZ[ζ3], onde ζ3 denota a raiz terceira da unidade. Neste sentido,
construiremos cadeias finitas de versões escalonadas de reticulados do tipo Z[ζ3] através de
reticulados ideais provenientes de corpos de números de corpos ciclotômicos Q(ζ3s) com
s ≥ 2, onde ζ3s denota a raiz 3
s-ésima da unidade.
1 Resultados
Códigos reticulados [1] são constrúıdos por meio da Construção A, isto é, a técnica que
possibilita a construção de reticulados através do mergulho de um código linear definido
sobre um corpo finito Fp em R
N ou em CN .
Nesta plenária focaremos apenas em códigos reticulados que sejam versões escalonadas
do reticulado complexo Z[ω]N . A partir de uma cadeia de partição finita de subreticulados
na forma
Z[ζ3]
N/φZ[ζ3]
N/φ2Z[ζ3]
N/ · · · (1)
Forney [3] mostrou queum subreticulado φkZ[ζ3]
N da partição dada na Equação 1, pode-se
expressar φkZ[ζ3]
N por meio de uma fórmula código complexa
φkZ[ζ3]
N = φk−1Z[ζ3]
N + φk−2Ck−1 + · · ·+ C0, (2)
onde φ é um elemento não nulo em Z[ζ3]. Já Ck−1, . . . , C0 denotam códigos lineares definidos
sobre um corpo finito. Os códigos Cj são obtidos a partir de C
N como sendoo conjunto de
todos as N -uplas de Z[ζ3]
N congruente modulo φjZ[ζ3] em cada uma das N coordenadas,
onde j ∈ {0, . . . , k − 1}.
1edson@feis.unesp.br
2macosta13@gmail.com
3jozue.vieira@sjbv.unesp.br
2
Como consequência de elemento primo 1− ζ3 em Z[ζ3] ser totalmente rafimificado na
extensão de corpos de números Q(ζs
3
)/Q(ζ3) de grau N , mostraremos que os reticulados
ideais Λk associado a ideais (1 − ζ3s)
kZ[ζ3s ] são isomorfos a reticulados (1 − ζ3)
kZ[ζ3]
N
para todo k ∈ {0, . . . , N − 1} e que a partição de reticulados ideais
Λ0/Λ1/ . . . /ΛN−1 (3)
está associada a partição de reticulados complexos dada pela Equação 1.
Por fim, faremos usos dos reticulados ideias dados na partição (3) para propor a quan-
tização de coeficientes de canal de comunicação.
Referências
[1] J.H. Conway and N.J.A. Sloane; Sphere packings, lattices and groups, Springer-Verlag,
New York, 1988.
[2] U. Eres, S. Litsyn and R. Zamir, Lattices which are good for (almost( everything),
IEEE Trans. Inform. Theory, 51(10), (2005) 3401-3416.
[3] G. D. Forney; Coset Codes - Part I: Introduction and geometrical classification, IEEE
Trans. Inform. Theory, 34, 1123-1151, 1988.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Alguns métodos criptográficos
Eliani Magalhães Beloni 1
Graduanda em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 2
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 3
Resumo. A criptografia é uma área da Matemática que estuda os métodos para codificar e
decodificar uma mensagem de modo que só seu destinatário leǵıtimo consiga interpretá-la.
Essa tarefa de escrever mensagens secretas é muito antiga. Nasceu com a diplomacia e com as
transações militares e hoje em dia, o método de Criptografia RSA, que possui chave pública,
é um dos mais utilizados na troca de informações sigilosas, como em transações financeiras
e no uso seguro da internet. Para se utilizar tal método é necessário ter conhecimento
de Teoria dos Números, pois são abordados assuntos como números primos, congruência,
número inverso, teorema de Fermat e teorema Chinês do Resto.
1 Introdução
Criptografia é uma área da Matemática que estuda métodos de codificação e de deco-
dificação de mensagens com objetivo de que apenas o remetente e o destinatário consigam
compreender seu significado. Existe conhecimento do uso (simples) da criptografia desde
a época do imperador romano Julio César. Atualmente sabe-se da inevitável necessidade
do sigilo de informações, por exemplo, em páginas da internet e nas transações bancárias,
o que seria imposśıvel se os métodos de criptografia utilizados hoje em dia não fossem
eficazes. A criptografia se iniciou com a intenção de ocultar simples textos, mas ganhou
uma importância cada vez maior à medida que a história da humanidade era constrúıda
até os nossos dias. Atualmente, métodos mais sofisticados e cheios de uma matemática
muito bem elaborada contribuem para que o objetivo da criptografia seja alcançado, que é
não deixar pessoas “estranhas”acessarem uma mensagem veiculada. Um dos métodos de
Criptografia mais usados atualmente é o RSA. Para conhecer como funciona este e outros
métodos faz-se necessário ter algum conhecimento de teoria elementar dos números, como
certas noções de divisibilidade, congruência modular, máximo divisor comum, números pri-
mos e função de Euler. A Criptografia RSA, por exemplo, funciona por que se fundamenta
em tomarmos dois primos muito grandes para a determinação das chaves de codificação
e de decodificação. No entanto, os métodos de criptografia atuais estão sujeitos a serem
superados, uma vez que computadores cada vez mais potentes são desenvolvidos, o que
1elianimb2010@bol.com.br
2andrade@ibilce.unesp.br
3Agradecimentos a FAPESP: 2013/24956-6 e ao CNPq - PICIME
2
potencializa a quebra dos códigos mantidos em segredo. Por isso, é preciso criar novos
métodos, ainda mais eficazes que os já existentes e que sejam capazes de manter seguras
todas as informações sigilosas entre o remetente e seu destinatário.
2 Resultados
Os principais problemas que envolvem o RSA são de encontrar números primos e
fatorar um número, campo da matemática nomeado por teoria dos números, e neste
caso em espećıfico estudar propriedades algébricas dos números Inteiros. A seguir apre-
sentamos algumas definições e resultados, para uma discussão do método de criptogra-
fia e ainda levando em conta alguns conceitos básicos conhecidos, onde é identificável a
grande importância da teoria dos números elementar nas construções dos algoritmos de
pré-codificação, codificação e decodificação do método RSA, principalmente no que se re-
fere à imprescindibilidade do uso dos números primos, que são fáceis de serem encontrados
e que são infinitos, mas cujo produto de dois deles, quando tomados muito grandes, é dif́ıcil
de ser fatorado, o que impossibilita descobrir uma chave de decodificação mesmo tendo
em mãos a chave de codificação de um usuário.
Definição 2.1. Sejam a, b e m números inteiros tal que m > 1. Dizemos que a divide b
se existe um inteiro c tal que b = ac. Dizemos que a é côngruo b módulo m se m divide
a− b e denotado por a ≡ b(mod m).
Teorema 2.1. (Teorema de Euclides) Existem infinitos números primos.
Teorema 2.2. (Teorema de Fermat) Se p é número primo e a é um inteiro que não é
diviśıvel por p, então ap−1 ≡ 1(mod p).
Teorema 2.3. (Teorema da Fatoração) Se n ≥ 2 é um inteiro, então n pode ser escrito
na forma n = pe1
1
· · · p
ek
k , onde 1 < p1 < p2 < p3 < · · · < pk, são números primos positivos
e e1, · · · , ek são inteiros positivos.
Teorema 2.4. (Teorema Chinês do Resto) Sejam p e q inteiros positivos e primos entre
si. Se a e b são inteiros quaisquer, então o sistema
{
x ≡ a(mod p)
x ≡ b(mod q)
sempre tem solução e qualquer uma de suas soluções, pode ser escrita na forma a+p(r(b−
a) + qt), onde t é um inteiro qualquer e r é o inverso de p módulo q.
3 Criptografia
O método RSA possui três etapas: Pré-codificação, Codificação e Decodificação.
A pré-codificação consiste em convertermos as letras em números, com base na tabela
abaixo.
3
A B C D E F G H I J K L M
10 11 12 13 14 15 16 17 18 19 20 21 22
N O P Q R S T U V W X Y Z
23 24 25 26 27 28 29 30 31 32 33 34 35
Exemplo 3.1. A palavra MATEMÁTICA é convertida no número x dado por x =
22102914221029181210. Vamos agora determinar a chave pública n = pq, onde p e q
são dois primos distintos muito grandes. Fazendo p = 17 e q = 23, segue que n = 391 e o
número x pode ser quebrado nos blocos: 22− 102− 91− 42− 210− 291− 8− 12− 10, que
são menoresque n. Veja que tais blocos não correspondem a nenhuma unidade lingúıstica,
o que torna a decodificação por contagem de frequência imposśıvel.
A codificação consiste em codificar cada bloco b separadamente, obtendo C(b), onde
C(b) é o resto da divisão de b3 por n. No exemplo que estamos considerando, o bloco
22 é codificado como o resto da divisão de 223 por 391, que por congruência, segue que
C(22) = 91. Assim, 223 ≡ 222 · 22 ≡ 484 · 22 ≡ 93 · 22 ≡ 2046 ≡ 91(mod 391). Codificando
todos os blocos, segue que a mensagem codificada é dada por 91− 34− 114− 189− 165−
178− 121− 164− 218.
A decodificação consiste em reconstruir o bloco original antes da codificação. Para isso
precisamos de dois números: n e o inverso d > 0,onde pela definição de inverso segue
que 3d ≡ 1(mod (p − 1)(q − 1)) e o par (n, d) é chamado de chave de decodificação que
deve ser mantido em segredo. Mas como esse método pode ser tão eficaz se para quebrá-
lo basta fatorar o número n? Acontece que n é um número muito grande e não existe
nenhum algoritmo conhecido capaz de fatorar inteiros grandes de modo realmente eficiente.
Assim, se a é um bloco codificado, denotamosD(a) como o resto da divisão de ad por n. No
exemplo, (p−1)(q−1) = 16·22 = 352, com d = 235, já que 3d ≡ 3·235 ≡ 705 ≡ 1(mod 352).
Aplicando o algoritmo para a = 91, segue que 91235 ≡ 6235 ≡ (616)14 · 611 ≡ (62)5 · 6 ≡
25 · 6 ≡ (−2) · 6 ≡ 5(mod 17) e 91235 ≡ 22235 ≡ (−1)235 ≡ −1 = 22(mod 23). Agora,
fazendo x = 91235, segue que x ≡ 5(mod 17) e x ≡ 22(mod 23). Pelo teorema Chinês
do resto, segue que x = 23q + 22. Deste modo, 23q + 22 ≡ 5(mod 17), 6q ≡ 0(mod 17),
6 · 3q ≡ q ≡ 0 · 3 ≡ 0(mod 17). Assim, x = 23 · 0 + 22 = 22, ou seja, D(91) = 22. Fazendo
isso com os demais blocos codificados chegaremos a mensagem inicial.
A complexidade, para quebrar um código RSA envolve, técnicas e artimanhas matemá-
ticas podendo levar anos para quebrá-lo, é algo simples de fazer, mas bem dif́ıcil de des-
fazer.
Referências
[1] Coutinho, S.C.; Criptografia. Rio de Janeiro: OBMEP, 2008.
[2] Domingues, H.H.; Iezzi, G.; Álgebra Moderna. São Paulo: Editora Atual, 1982.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Códigos de Blocos Espaço-Tempo via Corpos Quadráticos
Eliton Mendonça Moro 1
Mestrando em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Carina Alves 2
Departamento de Matemática, IGCE - Unesp, Rio Claro - SP
Antonio Aparecido de Andrade 3
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 4
Resumo. Neste trabalho apresentamos como projetar códigos de bloco espaço-tempo em
termos do critério da diversidade produto e para isso utilizamos os corpos quadráticos.
1 Resultados
Um tipo de sistema que tem sido bastante utilizado e visto como muito promissor é o
MIMO - Multiple Input Multiple Output - que consiste no uso de múltiplas antenas para
envio e recebimento de sinal. Os sistemas de comunicação MIMO estão sendo amplamente
explorados principalmente por fornecer ganhos na transmissão de sinal.
Para maximizar os ganhos tanto de diversidade quanto de multiplexação foi introduzido
o uso dos Códigos de Bloco Espaço-Tempo (STBC, em inglês). Estes códigos possuem
muitas aplicações na área da Teoria da Informação. No caso de um canal MIMO 2× 2 o
sinal recebido é dado por Y = HX +W, X,H, Y,W ∈ M2(C).
Seja K = Q(θ) uma extensão quadrática de Q(
√
d), onde d é um inteiro livre de
quadrados. Definimos o código C como
C =
{[
x1 x2
x3 x4
]
=
[
a+ bθ c+ dθ
γ(c+ dσ(θ)) a+ bσ(θ)
]
: a, b, c, d ∈ Z[
√
d]
}
.
Afim de equilibrar a energia da transmissão de sinais entre antenas é suficiente que
|γ| = 1, mas existem construções de STBC quadráticos onde |γ| 6= 1. Em [2], Wang
traz uma nova forma de construir um STBC que equilibra a energia entre as antenas,
porém essa nova construção não possui a estrutura de uma álgebra dos quatérnios, que
é a estrutura usada na maioria das construções. No entanto, é posśıvel estabelecer uma
bijeção entre entre elas.
Essa nova forma de construir STBC’s utiliza o critério da diversidade produto, apresen-
tado em [3]. Apresentamos códigos ótimos em termos do critério da diversidade produto
1elitonmoro@hotmail.com
2carina@rc.unesp.br
3andrade@ibilce.unesp.br
4Agradecimentos a CAPES
2
para canais MIMO 2× 2 usando corpos quadráticos. Em termos desse critério apresenta-
mos um STBC melhor do que o Código de Ouro [5].
Referências
[1] C. Hollanti, J. Lahtonen, K. Ranto, R. Vehkalahti, E. Viterbo. On the Algebraic
Structure of the Silver Code: a 2 × 2 Perfect Space-Time Block Code. 978-1-4244-
2270-8/08 IEEE 2008.
[2] G. Wang, J. K. Zhang, M. Amin. Space-Time Block Code Designs Based on Quadratic
Field Extension for Two-Transmitter Antennas. IEEE Transactions on Information
Theory, vol. 58, no. 6, June 2012.
[3] H. Yao, G. W. Wornell, Achieving the full MIMO diversity-multiplexing frontier with
rotation-based space-time codes. in Proc. Allerton Conf. Commun., Cont., and Com-
puting, IL, pp. 400-409, October. 2003.
[4] I. Stewart, D. Tall. Algebric Number Theory. Chapman & Hall, New York,1987.
[5] J. C. Belfiore, G. Pekaya, E. Viterbo, The Golden Coden: A 2×2 full rate space-time
code with nonvanishing determinants. in Proc. Int. Symp. Information Theory, pp.
310-313, June. 2004.
[6] T. Unger, N. Markin. Quadratic Forms and Space-Time Block Codes From Gene-
ralized Quaternion and Biquaternion Algebras. IEEE Transactions on information
theory, vol. 57, no. 9, September 2011.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Corpos ciclotômicos e aplicações
Gabriel Fazoli Domingos 1
Graduando em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 2
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 3
Resumo. A Teoria Algébrica dos Números é um ramo da Álgebra em que o conceito de
número é expandido para o de número algébrico, que são ráızes de polinômios com coefici-
entes racionais. O presente trabalho apresenta a estrutura algébrica dos corpos quadráticos,
definições e resultados, caracteriza o anel de inteiros desses corpos e apresenta algumas
aplicações dessa teoria aos reticulados algébricos.
1 Introdução
A teoria algébrica dos números surgiu no século 19, a partir do estudo das ráızes de po-
linômios mônicos em anéis, da teoria de Galois e outras ferramentas modernas de álgebra.
Entre seus colaboradores estão Gauss, Kummer e Dedekind. Viu-se nela uma maneira
muito eficaz de resolver problemas em que o tratamento clássico da teoria dos números
não se adequava. Além disso, a teoria algébrica dos números é capaz de estender, em
certos aspectos, a teoria clássica para outros anéis além dos inteiros. Corpos ciclotômicos
são corpos gerados a partir da inclusão de ráızes da unidade. Um anel de um corpo ci-
clotômico é o subanel desse corpo composto dos inteiros algébricos, isto é, que satisfazem
um polinômio inteiro mônico. Sua aparição e importância vêm das inúmeras tentativas de
provar o Ultimo Teorema de Fermat.
2 Resultados
Um corpo ciclotômico é um corpo gerado da junção dos racionais com uma raiz da
unidade. O anel de inteiros de um corpo qualquer é a intersecção desse corpo com o
anel dos inteiros algébricos(isto é, o conjunto dos reais que são ráızes de um polinômio
inteiro mônico). Para esta definição foi necessário realmente verificar que o conjunto dos
inteiros algébricos forma de fato, um anel. A noção de discriminante tem sua importância
para achar, posteriormente, os primos(inteiros) que associados aos quadrados de elemen-
tos irredut́ıveis de um anel de inteiros. Podemos definir o discriminante de uma n-upla
1gabrielfazoli@hotmail.com
2andrade@ibilce.unesp.br
3Agradecimentos a FAPESP: 2013/24956-6 e ao PICIME - CNPq
2(α1, · · · , αn) ∈ K
n, onde K é uma extensão de grau n, por:
∆(α1, · · · , αn) = det(σi(αj))
2,
onde σ1, · · ·σn são os automorfismos relacionados a extensão Q ⊆ K. Podemos agora
começar a enunciador os resultados dos anéis de inteiros de corpos ciclotômicos.
Primeiro, conclúımos o resultado para um p-ésimo corpo ciclotômico, onde p é um
número primo. Nesse caso, chegamos que Z[ζ], onde ζ onde é uma ráız p-ésima primitiva
da unidade, é o seu anel de inteiros, e que seu discriminante é dado por
∆ = (−1)
p−1
2 pp−2.
Em seguida, desenvolvemos a teoria para n-ésimos corpos ciclotômicos, onde n = pk, com
p um primo e k um inteiro positivo. Aqui, chegamos que o anel de inteiros é dado por
Z[ζn], onde ζ é uma raiz n-ésima primitiva da unidade, e que seu discriminante é dado por
∆ = (−1)
φ(n)
2 pp
k−1(k(p−1)−1),
onde φ é a função de Euler. Finalmente, a partir do caso anterior é posśıvel deduzir para
n-ésimos corpos ciclotômicos onde n é um inteiro positivo qualquer. De fato, seu anel de
inteiros é dado por Z[ζn] e seu discriminante é dado pela expressão
∆ = (−1)
sφ(n)
2
nφ(n)
∏
p|n p
φ(n)
p−1
.
Assim, determinamos as propriedades básicas dos anéis de inteiros correspondentes a qual-
quer corpo ciclotômico.
Referências
[1] Endler, O.; Teoria dos Números algébricos, 2ed, Rio de Janeiro: Impa, 2014.
[2] Stewart,I.; Tall, D.: Algebraic Number Theory, London; New York: Chapman and
Hall, 1987.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
A conjectura de Golomb-Welch para códigos perfeitos na
métrica de Lee
George Absalão Pandino de Morais 1
Instituto de Ciência e Tecnologia - Universidade Federal de São Paulo, São José dos Campos - SP
Grasiele Cristiane Jorge 2
Instituto de Ciência e Tecnologia - Universidade Federal de São Paulo, São José dos Campos - SP 3
Resumo.
A conjectura de Golomb-Welch [2], postulada em 1970, afirma que não existem códigos
perfeitos na métrica de Lee em Zn para n ≥ 3 e raio de empacotamento r ≥ 2. Tal
conjectura tem sido, por muitos anos, uma das principais motivações da pesquisa nesta
área. Embora ainda não tenha sido resolvida, acredita-se na sua veracidade e alguns casos
particulares já foram provados. Inclusive em [2] provou-se a veracidade da conjectura para
n > 4 e r suficientemente grande.
Algumas das técnicas que têm sido usadas para abordar a conjectura utilizam ferramentas
como funções geradoras (como em [4]) e empacotamento de politopos em Rn [2,3]. Também
existem algumas reformulações da conjectura, por exemplo, em termos de grafos circulantes
(como em [1]). Uma das principais técnicas recentes utilizadas para atacar o problema
(introduzida em [3]) faz uso de um invariante relacionado com grupos abelianos finitos. Tal
invariante permite fazer outra reformulação da conjectura e provar alguns de seus casos
particulares, dentre eles, o caso provado por Golomb e Welch em [2] e o caso r = 2 e n ≤ 12.
O foco deste trabalho será o estudo desta técnica e das demonstrações de alguns fatos sobre
a conjectura apresentados em [3].
Referências
[1] S. I. Costa, M. Muniz, E. Agustini, e R. Palazzo, Graphs, tessellations, and perfect
codes on flat tori, IEEE Transactions on Information Theory 50, 2363-2377, 2004.
[2] S. W. Golomb, L. R. Welch, Perfect codes in the Lee metric and the packing of
polyominoes, SIAM Journal on Applied Mathematics, 18(2), 302-317, 1970.
[3] P. Horak, O. Grosek, A new approach towards the Golomb-Welch conjecture, European
Journal of Combinatorics, 38, 12-22, 2014.
[4] K. A. Post, Nonexistence theorem on perfect Lee codes over large alphabets, Informa-
tion and Control, 29, 369-380, 1975.
1georgeapdemorais@yahoo.com.br
2grasiele.jorge@unifesp.br
3Agradecimentos à Fapesp - Processos 2013/25977-7 e 2015/17167-0
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Isomorfismo entre Reticulado de Grupos e Espaço Projetivo
Leandro Bezerra de Lima 1
FEEC - UNICAMP / CPAq - UFMS
Reginaldo Palazzo Junior 2
FEEC - UNICAMP 3
Resumo. Design combinatório é uma importante estrutura combinatória com alto grau de
regularidade e que está relacionada a existência e construção de sistemas de conjuntos de
cardinalidade finita, [2, 8]. Como exemplo, mencionamos a relação existente entre códigos
corretores de erros em espaço de Hamming e design combinatório, onde as palavras-código
de peso 3 do código de Hamming formam um sistema triplo de Steiner STS(7), um plano
projetivo de ordem 2, conhecido como plano de Fano, [4], assim como q-analogs de um código
de peso constante no espaço de Hamming é um código na Grassmanniana do espaço projetivo,
[1,5]. Espaço projetivo de ordem m sobre o corpo finito Fp, denotado por P(F
m
p
), (note que
F
m
p
é isomorfo a Fpm), é o conjunto de todos os subespaços no espaço vetorial F
m
p
. O espaço
projetivo munido com a distância de subespaço d(X,Y ) = dim(X)+dim(Y )−2dim(X∩Y ) é
um espaço métrico. Com isto, um código de subespaço C com parâmetros (n,M, d) no espaço
projetivo é um subconjunto de P(Fm
p
) de tamanho M com a distância de subespaço entre
quaisquer duas palavras código de pelo menos d, [6]. Nesta comunicação apresentaremos
um isomorfismo existente entre o diagrama de Hasse de um reticulado de grupo abeliano
consistindo do produto direto de grupos abelianos finitos multiplicaticos Zm
p
e o diagrama
de Hasse de espaços projetivos P(Fm
p
), com o objetivo, de fornecer elementos que possam
ser úteis para elaboração e construção de bons códigos de subespaços. [3, 7].
Referências
[1] M.Braun, T. Etzion, P.R.J. Östergard, A. Vardy, and A. Warssermann, ”Existence
of q-Analogs of Steiner Systems”, arxiv.org/abs/1304.1462, Apr. 2013.
[2] C. J. Colbourn and J.H. Dinitz, ”Handbook of Combinatorial Designs”, Chapman &
Hall/CRC, Second Edition , 2007.
[3] C.H.A. Costa e M. Guerreiro, ”Automorphisms of finite Abelian groups”, MS thesis,
Mathematics Dept, UFV, Viçosa, Minas Gerais, 2014.(in Portuguese)
[4] T.Etzion and N. Silberstein, ”Error Correcting Codes in Projective Spaces via Rank
Metric Codes and Ferrers Diagrams”, IEEE Trans. on Inform. Theory, vol. 55, n.o7,
pp.2909-2919, Jul. 2009.
1leandro.lima@ufms.br
2palazzo@dt.fee.unicamp.br
3Agradecimentos a Fapesp - Processo 2013/25977-7
2
[5] T. Etzion and A. Vardy, ”Error Correcting Codes in Projective Space”, in Proceedings
of the 2008 IEEE Intl. Symp. on Inform. Theory - ISIT-08, pp. 871-875, Toronto,
Canada, Jul. 2008.
[6] A. Khaleghi, D. Silva, and F.R. Kschischang, ”Subspace Codes”, Lecture Notes in
Computer Science, vol. 5921, pp. 1-21, 2009.
[7] S. Roman, ”Lattices and Ordered Sets”, Springer, vol. 1, 2008.
[8] D.R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer Verlag,
New York, USA, 2004.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Algumas funções aritméticas
Linara Stéfani Facini 1
Graduanda em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 2
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 3
Resumo. A função de Mobius µ(n) é uma função aritmética multiplicativa na Teoria
dos Números e Análise Combinatória, cujo nome é em homenagem ao matemático alemão
August Ferdinand Mobius, que foi o primeiro a defini-la em 1831. De forma surpreendente, a
função de Mobius se relaciona com a teoria das part́ıculas subatômicas e também se envolve
com numerosas identidades matemáticas. Alguns aspectos do seu comportamento ainda não
estão inteiramente esclarecidos.
1 Introdução
Muitos matemáticos desempenharam um papel de destaque no desenvolvimento da
Teoria dos Números sendo que Euclides (cerca de 300 a.C), em Elementos de Geometria,
preservou o conhecimento matemático dos antigos gregos e Diofanto (cercade 250 a.C),
em Arithmetica, apresentou o primeiro tratado sobre álgebra, tornando os fundadores da
Teoria dos Números clássica. Os Elementos de Euclides, especialmente nos livros VII,
VIII e IX, apresentam uma riqueza de informações sobre as propriedades fundamentais da
divisibilidade e conceitos teóricos importantes no estudo da Teoria dos Números, enquanto
que Diofanto desenvolveu métodos para obter soluções racionais para equações polinômiais
chamadas equações diofantinas. A Matemática na Europa teve uma renovação vigorosa
após a Idade Média, onde a Teoria dos Números por representar uma área particular da
Matemática de grande desenvolvimento apresenta matemáticos de destaque, como Pierre
de Fermat, Leonhard Euler, Adrien-Marie Legendre e Carl Friedrich Gauss que através de
suas contribuições significativas aprimoraram a Teoria dos Números.
Os elementos do conjunto {1, · · · , p − 1}, onde p é um primo impar, tem algumas
caracteŕısticas especiais. Por exemplo, os que são reśıduos quadráticos e os que não são
reśıduos quadráticos. Mais especificamente, dizemos que a ∈ Z é um reśıduo quadrático
módulo p se existe x ∈ {0, 1, · · · , p−1} tal que x2 ≡ a(mod p), ou seja, a ∈ Z é um reśıduo
quadrático módulo p se, e somente se, x2 ≡ a(mod p) tem solução, com mdc(a, p) = 1.
Neste caso, metade do conjunto {1, 2, · · · , p − 1} são reśıduos quadráticos. O śımbolo
1linarafacini@gmail.com
2andrade@ibilce.unesp.br
3Agradecimentos a FAPESP: 2013/24956-6 e ao PICME - CNPq
2
de Legendre, o critério de Euler, lei de reciprocidade quadrática e o Lema de Gauss são
ferramentas importantes para procurar soluções das congruências quadráticas.
O primeiro matemático a estudar a lei de reciprocidade quadrática foi Fermat, que
tinha a Matemática como uma atividade de lazer em uma época em que não existiam revis-
tas matemáticas. Fermat tinha um costume curioso de apresentar resultados matemáticos
em margens de livros e em cartas enviadas a outros matemáticos. Ainda assim, esta
forma peculiar de estudar matemática muito contribuiu na direção da demonstração da
reciprocidade quadrática. Sejam p e q são dois números primos distintos, de modo que
p ≡ q ≡ 3(mod 4). Assim, q é um reśıduo quadrático módulo p, se, e somente se, p não é
um reśıduo quadrático módulo q. Além disso, se p ≡ 1(mod 4) ou q ≡ 1(mod 4), então q
é um reśıduo quadrático módulo p se, e somente se, p é um reśıduo quadrático módulo q.
Fermat foi crucial na dedução do caráter quadrático de {−1,±2,±3} e Euler provou
algumas conjecturas de Fermat. Joseph Lagrange teve participação fundamental em in-
spirar Euler a continuar a trabalhar na Teoria dos Números e especialmente na tentativa
em provar a Lei de Reciprocidade Quadrática completa que, com sua morte, Euler não
pode encontrar nenhuma prova concreta. Além disso, o Critério de Euler foi bastante
útil para Legendre e Gauss aprofundarem o problema dos reśıduos quadráticos em con-
texto geral dando um enfoque mais rigoroso. Legendre não ficou satisfeito em estudar
apenas os resultados descobertos por Fermat e Euler e por isso escreveu, em 1798, seu
primeiro trabalho denominado ”Essal sur la Theorie des nombres”que se preocupou em
interligar a Teoria dos Números desde a Arithmetica de Diofanto ao Quadratorum Liber
de Fibonacci. Dessa maneira, inúmeros trabalhos sobre a Lei de Reciprocidade Quadrática
permitiram ao mundo conhecer uma notação ainda usada atualmente para simbolizar a
Lei de Reciprocidade Quadrática de forma moderna, a saber, o śımbolo de Legendre.
Legendre não conseguiu colocar suas provas em um contexto teórico consistente, mas
desenvolveu um śımbolo que levou a uma série de maneiras de provar a Reciprocidade
Quadrática. O śımbolo de Legendre deu origem ao desenvolvimento de Jacobi e śımbolos
de Hilbert. Em 1801, Gauss, o pŕıncipe da Matemática, publicou um trabalho inovador
”Disquisitiones Arithmeticae”introduzindo de forma clara e concisa a notação moderna
de congruência a ≡ b(mod n), onde a, b, n ∈ Z e n > 1, e apresentou uma demonstração
do Teorema Fundamental da Aritmética e uma revisão de tudo que se conhecia em Teoria
dos Números. Na seção IV, Gauss apresenta a primeira demonstração da reciprocidade
quadrática, o tesouro da Matemática do século XVIII e XIX, por meio de indução cuja
prova seguiu o racioćınio da prova de Legendre, sendo descoberta independentemente
do trabalho de Legendre. Com isso, Euler definiu a Lei de Reciprocidade Quadrática,
Legendre apresentou vários resulatados sobre essa lei, mas foi Gauss deu a primeira prova.
Tal teorema recebeu posteriormente a denominação de Theorema Aureum (”teorema de
ouro”).
Gauss provou a Lei de Reciprocidade Quadrática, em 18 de Abril de 1796, no entanto
só conseguiu publicá-la em 1801, através de sua obra ”Disquisitiones Arithmeticae”e por
se sentir atráıdo pela beleza do ”Teorema de Ouro”, encontrou oito demonstrações, sendo
a quinta demonstração a mais elegante e direta. Na seção V, Gauss destaca a teoria
de formas quadráticas binárias através de polinômios homogêneos de grau dois em duas
variáveis. Atualmente, existem mais de 2071 provas da Lei de Reciprocidade Quadrática.
3
Contudo, a prova considerada mais elementar foi dada por Eisenstein, por meio de ar-
gumentos geométricos. Com a demonstração da Lei de Reciprocidade Quadrática, Gauss
alcancçou importantes conquistas que expandiram os horizontes da Teoria dos Números
principalmente quando apresentou a primeira prova, onde considerou que, a partir dessa
lei, haveria reciprocidades com graus superiores. A criptografia e o algoritmo de fatoração
de inteiros fazem uso da lei da reciprocidade quadrática, e além de os reśıduos quadráticos
serem bastante utilizados em acústica.
2 Resultados
As funções aritméticas são funções definidas com domı́nio em N−{0} e imagem em Z
possuindo várias aplicações na aritmética dos números inteiros.
Definição 2.1. Uma função f : N− {0} → Z é chamada uma função aritmética,ou seja,
é uma função onde o domı́nio é os números naturais positivos e seu contradomı́nio é os
inteiros.
Definição 2.2. Uma função aritmética é multiplicativa se f(p1p2 · · · pr) = f(p1)f(p2) · · · f(pr),
onde r ≥ 1, os pi são primos e pi 6= pj sempre que i 6= j, para i = 1, 2, · · · , r.
Definição 2.3. A função σ : N − {0} → N − {0} associa a cada n ∈ N − {0} a soma de
seus divisores.
Definição 2.4. A função τ : N− {0} → N− {0} associa cada n ∈ N− {0} ao número de
divisores de n.
Definição 2.5. A função ϕ : N− {0} → N− {0} associa cada n ∈ N− {0} ao número de
elementos de {k ∈ N− {0}|1 ≤ k ≤ n e mdc(k, n) = 1} é chamada função ϕ de Euler.
A função definida a seguir é chamada de Möbius em homenagem ao matemático A. F.
Möbius (1790-1868) que a introduziu em 1831.
Definição 2.6. A função de Möbius µ é definida por
µ(n) =



1, se n = 1
0, se p2 | n, onde p é um primo
(−1)r, se n = p1p2 · · · pr é um produto de primos distintos.
Definição 2.7. Um caracter módulo n, onde n é um inteiro positivo, é uma função
χ : Z → C satisfazendo
1. χ(k) = 0 quando mdc(k, n) 6= 1;
2. χ(k) = χ(l) quando k ≡ l(mod n);
3. χ(kl) = χ(k)χ(l);
4. χ(1) 6= 0.
4
Definição 2.8. Seja p um primo. O śımbolo de Legendre de m ∈ Z é definido por
(m
p
)
=



0 se p | m
1 se p - m e m é um reśıduo quadrático módulo p
−1 se p - m e m não é um reśıduo quadrático módulo p
Definição 2.9. O caracter principal módulo n é definido como
χ0(m) =
{
0 se mdc(m,n) for diferente de, 1
1 se mdc(m,n) for igual a 1
Definição 2.10. Um caracter χpq módulo q é definido da seguinte forma
χpq(n) =
{
0 se q | n
ξip se q - n e n ≡ g
i(mod q)
onde ξp = e
2πi
p e g é um gerador de Z∗q.
Definição 2.11. Seja ∈ Z. A soma de Gauss associada com χpq é definida como
τ(χtpq) =
∑
i∈Z∗q
χ(i)tξiq.
Definição 2.12. Z[ξp,ξq] = {g(ξp, ξq) : g(x, y) é um polinômio com coeficientes em Z}.
3 Conclusões
A função de Mobius é uma função multiplicativa, indica em qual das seguintes divisões
se encontra o inteiro positivo: 1) os múltiplos de quadrados, ou seja, os da forma mp2,
com m e p em Z,, sendo p um primo. 2) Os não múltiplos de quadrados que são da
forma p1p2 · · · pk, onde os pi são todos primos distintos, que subdividem-se em: (a) Os não
múltiplos de quadrados com k par. (b) Os não múltiplos de quadrados com k ı́mpar. Ou
seja, o inteiro positivo n se encontra em: 2) (b), 1) ou 2) (a), para isso atribui as imagens
µ(n) = −1, µ(n) = 0 ou µ(n) = 1, respectivamente.
Referências
[1] Filho, E. A.; Teoria Elementar dos Números, São Paulo: Editora Nobel, 1987.
[2] 2 Domingues, H.H.; Fundamentos de Aritmética. Editora Moderna, São Paulo, 1984.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Complexidade de comunicação relacionada ao problema do
vetor mais próximo em reticulados
Maiara Francine Bollauf 1
Departamento de Matemática Aplicada, Universidade Estadual de Campinas - SP
Vinay Vaishampayan 2
Departamento de Engenharia Elétrica, City University of New York - NY
3
Resumo. O problema de encontrar o vetor mais próximo a um vetor real x dado em um re-
ticulado é um problem NP-dif́ıcil [2], i.e., para reticulados quaisquer, não é posśıvel resolver
esse problema em tempo polinomial. Contudo, para reticulados espećıficos existem algorit-
mos [1] que resolvem esse problema em tempo polinomial. Nesse trabalho, consideramos
a resolução do problema no vetor mais próximo em uma configuração de rede distribúıda
e estudamos alguns aspectos relacionados à complexidade de comunicação. De modo mais
espećıfico, desenvolvemos uma maneira de mensurar o custo de comunicação e a taxa de
erros do que chamamos de ”problema do vetor mais próximo distribúıdo”.
1 Definição do Problema
Definimos o problema do vetor mais próximo em um reticulado da seguinte maneira:
dado um vetor x = (x1, x2, . . . , xn) ∈ R
n procuramos pelo vetor que está mais próximo à ele
em um determinado reticulado Λ. Adicionamos então uma nova restrição à resolução deste
problema, ou seja, considere que cada coordenada xi, i = 1, . . . , n do vetor x ∈ R
n esteja
dispońıvel em um nó que está fisicamente separado dos demais em uma rede distribúıda
e que temos um limitação no número de bits que podem ser transmitidos entre os nós.
Estamos interessados em encontrar o vetor mais próximo do reticulado em um nó principal
que chamamos de ”nó central” F e tal esquema está ilustrado na figura abaixo.
1maiarabollauf@ime.unicamp.br
2Vinay.Vaishampayan@csi.cuny.edu.br
3Agradecimentos a Fapesp - Processos 2013/25977-7, 2014/14449-2 e 2015/17167-0
2
2 Resultados
2.1 Algoritmo
Nossa ideia para resolver o problema do vetor mais próximo em um sistema distrubúıdo
para um reticulado n−dimensional qualquer Λ com matriz geradora G está brevemente
explicado no algoritmo a seguir.
Algoritmo 1: Estimar o vetor mais próximo em um sistema distribúıdo
1. Calcule a fatoração QR da matriz geradora G para obter uma matriz triangular R
que gera um reticulado equivalente ao reticulado Λ gerado por G;
2. Aplique o preprocessamento dado pelo algoritmo LLL na matriz R para obter uma
nova base nas colunas da nova matriz R̃ cujos vetores são curtos e ortogonais;
3. Envie a partir de cada i−ésimo nó da rede o valor de b 1
r̃ii
xie, i = 1, 2, . . . , n para
o nó central de modo a recuperar o vetor mais próximo ao vetor x resolvendo um
sistema linear.
2.2 Reticulados bidimensionais
Nossos resultados até o presente momento envolvem a análise desse algoritmo em
reticulados bidimensionais, onde conclúımos que:
• no reticulado A2, enviando um bit extra a partir do primeiro nó da rede distribúıda
o erro do algoritmo é de 8.33%.
• para um reticulado bidimensional qualquer, derivamos cotas inferiores e superiores
para a probabilidade de erro do algoritmo proposto;
• o progresso da taxa de erros conforme enviamos um número maior de bits por nó
pode ser descrito por uma função que estima esse erro em termos no número de bits
e tal função decresce exponencialmente;
• a troca de informação entre os nós da rede pode melhorar (ou não) a taxa de erro
encontrada.
Referências
[1] J.H. Conway and N.J.A. Sloane, Fast Quantizing and Decoding Algorithms for Lattice
Quantizers and Codes. IEEE Transactions on Information Theory 28(2) (1982) 227-
232.
[2] P. van Emde Boas, Another NP-Complete Problem and the Complexity of Compu-
ting Short Vectors in a Lattice. Report 81-04, Mathematische Institut, Universiry of
Amsterdam, Amsterdam, 1981.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Modulação codificada baseada na teoria de reticulado
Miller Acosta Osorio 1
Aluno do Programa de Pós-Graduação em Engenharia Elétrica – Unesp, Ilha Solteira - SP
Edson Donizete de Carvalho 2
Departamento de Matemática, Faculdade de Engenharia – Unesp, Ilha Solteira - SP
Jozué Vieira Filho 3
Engenharia de Telecomunicações – Unesp, São João da Boa Vista - SP
Resumo. Os sistemas de comunicações sem fio têm evolúıdo e se difundido de forma
extraordinária nos últimos anos. O crescimento nas aplicações, considerando um espectro
de frequência limitado, requer sistemas eficientes que integrem voz e dados em modernos
links de comunicação digital. Nesse sentido, os problemas de multipercuso continuam sendo
os que mais limitam a capacidade de sistemas sem fio. Sistemas eficientes de codificação de
canal continuam sendo estudados e são, de fato, um dos principais mecanismos que podem
melhorar tal eficiência. Novos esquemas de modulação codificada tem sido propostos na
literatura via reticulados. A ideia inicial da pesquisa visa avaliar a taxa de bits errados
(BER), na transmissão dos dados por um sistema de comunicações sem fio ponto a ponto,
empregando a teoria de reticulados na codificação de canal para compensar os efeito de
multipercurso no canal. Neste seminário, apresentamos a relação que tem os reticulados
com a modulação codificada para a codificação do canal sem fio.
1 Contextualização
O interesse pelos efeitos do canal de comunicações sem fio, como em sistemas de mi-
croondas e sistemas de rádio em alta frequência, existe há mais de 50 anos; efeitos que na
atualidade continuam em vigência. Porém, com fatores adicionais impostas pelas novas
aplicações em comunicações. As estruturas da álgebra abstrata permitiram gerar classes
de códigos de bloco e, o uso de circuitos seqüenciais lineares permitiram gerar a classe
de códigos que hoje chamamos de códigos convolucionais; as duas amplamente utilizados
atualmente nos sistemas de comunicações.
Tradicionalmente, no sistema de comunicações, a codificação de canal e a modulação
foram implementados de forma separada. Porém, a partir do trabalho de Imai e Hira-
kawa [1] surgiu na literatura técnicas de codificação de canal e modulação integradas em
um único bloco do sistema de comunicações [2–4]. Técnicas de modulação eficiente para
canais limitados em largura de banda foram expostas em [3]. Os esquemas de modulação
Block code Modulation (BCM) e Trellis Code Modulation (TCM) levam a um ganho de
1macosta13@gmail.com – Agradecimentos a Capes
2edson@mat.feis.unesp.br – Agradecimentos a Fapesp - Processo 2013/25977-7
3jozue.vieira@sjbv.unesp.br
2
diversidade (no espaço de sinal) no sistema de transmissão; são implementados mediante
códigos de canal lineares para construir esta diversidade. O tratamento dos códigos de clas-
ses laterais obtidos via reticulados por Forney [5] e de reticulados por Zamir [9] fornecem
fundamentos matemáticos para relacionar-lhes com as técnicas de modulação codificada.
Além, de que as estruturas de reticulado permiteminimizar o efeito multipercurso em
sistemas de comunicações [6–8].
2 Resultados
Neste seminário mostraremos a estreita relação entre os esquemas de modulação co-
dificada com a teoria de reticulados. Observaremos que se o esquema tem uma estrutura
de partição (tipo treliça) é posśıvel implementar o algoritmo de decodificação suave de
Viterbi para reduzir a complexidade na decodificação. Estas observações, são resultados
preliminares de nossa pesquisa que permitiram, implementar um modelo de simulação
para avaliar a taxa de bits errados (BER), em um sistema de comunicação sem fio, com
codificação de canal baseada em reticulado desde a visão da engenharia.
Referências
[1] H. Imai, S. Hirakawa, A new multilevel coding method using error-correcting codes,
IEEE Transactions on Information Theory, 23(3) (1977) 371-377.
[2] E.L. Cusack, Error control codes for QAM signalling, Electronics Letters, 20(2) (1984)
62-63.
[3] G. D. Forney, Efficient Modulation for Band-Limited Channels, Selected Areas in
Communications, IEEE Journal on, 2(5) (1984) 632-647.
[4] S.I. Sayegh, A Class of Optimum Block Codes in Signal Space, Communications,
IEEE Transactions on, 34(10) (1986) 1043-1045.
[5] G. D. Forney, Coset codes. I. Introduction and geometrical classification, IEEE Tran-
sactions on Information Theory, 34(5) (1988) 1123-1151.
[6] Giraud, X., Boutilon, E., Belfiore, J. C., Algebraic tools to build modulation schemes
for fading channels, IEEE Transacions on Information Theory, 43(2) (1997) 938-952.
[7] A. J. Goldsmith, S. G. Chua Adaptive coded modulation for fading channels, IEEE
Transactions on Communications, 46(5) (1998) 595-602.
[8] F. Oggier, E. Viterbo Algebraic Number Theory and Code Design for Rayleigh Fading
Channels, Foundations and TrendsTMin Communications and Information Theory,
1(3) (2004) 333-415.
[9] Ram Zamir, Lattice Coding for Signals and Networks, Cambridge University Press,
Cambridge, 2014.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Subcorpos reais maximais de corpos ciclotômicos de grau 8.
Náısa Camila Garcia 1
Mestranda no programa de pós-graduação em matemática da Unesp, São José do Rio Preto - SP2
Trajano Pires da Nóbrega Neto 3
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Resumo Dado um número inteiro positivo n, o n-ésimo corpo ciclotômico Q(ζn), onde
ζn = e
2πi
n , é uma extensão galoisiana de Q, cujo grupo de Galois é isomorfo à (Z/nZ)∗. Este
trabalho tem como foco o corpo Q(ζn)
+ := Q(ζn) ∩ R, quando [Q(ζn) : Q] = 8.
1 Resultados
Os principais resultados deste trabalho são a descrição explicita dos corpos acima
citados e algumas aplicações.
Referências
[1] L.C. Washington, Introduction to ciclotomic fields, Springer-Verlag, New York, 1982.
[2] D. A. Marcus, Number Fields, Springer-Verlag, New York, 1977.
1naisacamila@hotmail.com
2Agradecimentos a Capes
3trajano@ibilce.unesp.br
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Corpos quadráticos e aplicações
Pĺınio Gabriel Sicuti 1
Graduando em Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Antonio Aparecido de Andrade 2
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 3
Resumo. A Teoria Algébrica dos Números é um ramo da Álgebra em que o conceito de
número é expandido para o de número algébrico, que são ráızes de polinômios com coefici-
entes racionais. O presente trabalho apresenta a estrutura algébrica dos corpos quadráticos,
definições e resultados, caracteriza o anel de inteiros desses corpos e apresenta algumas
aplicações dessa teoria aos reticulados algébricos.
1 Introdução
Determinar o anel de inteiros de corpos quadráticos com o objetivo de utilizá-los na
produção de reticulados algébricos, os quais são aplicados à Teoria da Informação e à
Teoria dos Códigos Corretores de Erros.
O estudo sobre corpos de números fornece conceitos para determinar o anel de inteiros
de corpos quadráticos. Via conceitos da teoria algébrica dos números, como homomor-
fismo canônico, é posśıvel construir reticulados em uma dimensão utilizando um corpo de
números de grau. Poderemos analisar alguns dos parâmetros principais de tais reticula-
dos, como volume, distância mı́nima e densidade de centro, através de conceitos como a
estrutura do anel de inteiros do corpo, a norma de um ideal, discriminante do corpo e o
traço.
2 Resultados
Seja K um corpo de números, ou seja, K é uma extensão finita de Q. Se Q ⊆ K é de
grau 2, dizemos que K é um corpo quadrático.
Proposição 2.1. Todo corpo quadrático é da forma Q(
√
d) = {a + b
√
d; a, b ∈ Q}, onde
d é um inteiro livre de quadrados, isto é, o único quadrado que divide d é 1.
Teorema 2.1. Se K = Q(θ) é um corpo de números de grau n, então existem n Q-
monomorfismos distintos, σi : K −→ C, onde σi(θ) = θi são as ráızes distintas em C do
polinômio irredut́ıvel de θ sobre Q, para i = 1, 2, · · · , n.
1pliniosicuti@gmail.com
2andrade@ibilce.unesp.br
3Agradecimentos a FAPESP: 2013/24956-6 e ao PET - Capes
2
Definição 2.1. Seja K um corpo de números de grau n. O discriminante de uma base
{α1, α2, · · · , αn} de K sobre Q é definido como
∆[α1, α2, · · · , αn] = (det[σi(αj)])2,
onde os σi são os monomorfismos de K em C.
Definição 2.2. Seja K um corpo de números de grau n. A norma e o traço de um
elemento α ∈ K, denotados por N (α)|K e T r(α)|K, respectivamente, são definidos como
N (α)|K =
n
∏
i=1
= σi(α) e T r(α)|K =
n
∑
i=1
σi(α).
Em particular, para um corpo quadrático o conjugado, a norma e o traço de um
elemento α = a+ b
√
d ∈ Q(
√
d) são dados, respectivamente, por α = a− b
√
d, N (α)|K =
αα = a2 − b2d e T r(α)|K = α+ α = 2a.
Definição 2.3. Seja Q ⊂ K uma extensão de grau n. Um elemento α ∈ K é dito inteiro
algébrico se existirem ai ∈ Z, i = 1, · · · , n−1, tal que αn+an−1αn−1+ · · ·+a1α+a0 = 0,
isto é, α é raiz de um polinômio mônico com coeficientes inteiros. O conjunto dos inteiros
algébricos OK é um anel, chamado anel de inteiros algébircos de K.
Teorema 2.2. Se Q(
√
d) é um corpo quadrático com d livre de quadrados, então o anel
de inteiros OK é dado por
OK =
{
Z[
√
d], se d ≡ 2, 3(mod 4)
Z[1+
√
d
2
], se d ≡ 1(mod 4).
Proposição 2.2. Seja d um número inteiro livre de quadrados. Se d ≡ 1(mod 4), então o
discriminante de Q(
√
d) é d. Caso contrário, se d 6≡ 1(mod 4), então o seu discriminante
é 4d.
Demonstração: Se d ≡ 1(mod 4), então o conjunto {1, 1+
√
d
2
} é uma base de Q(
√
d).
Assim,
∆
[
1,
1 +
√
d
2
]
= (det[σi(αj)])
2 =
∣
∣
∣
∣
∣
1 1+
√
d
2
1 1−
√
d
2
∣
∣
∣
∣
∣
2
= (−
√
d)2 = d
Por outro lado, se d 6≡ 1(mod 4), então o conjunto {1,
√
d} é uma base para Q(
√
d). Logo,
∆[1,
√
d] = (det[σi(αj)])
2 =
∣
∣
∣
∣
1
√
d
1 −
√
d
∣
∣
∣
∣
2
= (−2
√
d)2 = 4d.
Exemplo 2.1. O corpo quadrático Q(
√
−1) = Q(i) é chamado de corpo gaussiano. Como
−1 ≡ 3(mod 4), pelo Teorema 2, segue que o seu anel de inteiros é Z[i], o qual é chamado
de anel de inteiros de Gauss. Além disso, pela Proposição 2, segue que o discriminante
do corpo gaussiano é −4.
3
Definição 2.4. Seja β = {v1, · · · , vm} um conjunto linearmente independente de Rn
onde m ≤ n. Um reticulado de dimensão m e base β é definido como Λ = {x ∈ Rn;x =
m
∑
i=1
aivi com ai ∈ Z}.
Definição 2.5. Seja Λ ⊆ Rn um reticulado com base β = {v1, · · · , vn}. O conjunto
Ψβ = {x ∈ Rn;x =
n
∑
i=1
λivi, 0 ≤ λi < 1} é chamado região fundamental de Λ.
Exemplo 2.2. Considere o reticulado Λ = {a(1, 0) + b(0, 1); a, b ∈ Z} em R2 cuja base
é a canônica {(1, 0), (0, 1)}. Assim, Λ = Z2 e a região fundamental de Z2 é dada pelo
retângulo de vértices (0, 0), (0, 1), (1, 0) e (1, 1).
Definição 2.6. Seja Λ ⊆ Rn um reticulado com uma Z−base β = {v1, · · · , vn}. A matriz
M formadapelas coordenadas de cada vi colocadas em linha, é chamada matriz geradora
do reticulado.
Definição 2.7. Sejam Λ ⊆ Rn um reticulado com uma Z−base β e Ψβ sua região funda-
mental. Definimos o volume de Ψβ como o módulo do determinante da matriz geradora e
denotamos por V ol(Ψβ). O volume do reticulado é definido como V ol(Λ) = V ol(Ψβ).
Definição 2.8. Um empacotamento no Rn é uma distribuição de esferas n-dimensionais
de mesmo raio de tal modo que a intersecção de duas esferas tenha no máximo um ponto e
que este arranjo ocupe o maior espaço posśıvel. Definimos a densidade de empacotamento
∆(Λ) associado a um reticulado Λ com β uma Z-base como sendo a proporção do espaço
no Rn coberta pela união de esferas.
Definição 2.9. Seja Λ ⊆ Rn um reticulado. A densidade de centro de Λ é definida por
δ(Λ) =
ρn
V ol(Λ)
,
onde ρ é o raio do empacotamento de Λ.
Observação 2.1. Se Λ é um reticulado no Rn e B(ρ) a esfera de centro na origem e raio
ρ, então a densidade do empacotamento de Λ é dada por
∆(Λ) =
V ol(B(ρ))
V ol(Λ)
=
V ol(1)ρn
V ol(Λ)
,
onde V ol(B(1)) é o volume da esfera de raio 1.
Exemplo 2.3. Se Λ ⊆ R2 é um reticulado com base {(1, 0), (0, 2)}, então ρ = 1
2
, V ol(B(1)) =
π e o volume do reticulado é dado pelo determinante
det
[
1 0
0 2
]
= 2.
Além disso, a densidade de empacotamento é dada por ∆(Λ) = V ol(B(1))
ρ2
V ol(Λ)
=
π
8
e
a densidade de centro é dada por δ(Λ) =
1
8
.
4
Definição 2.10. Seja K um corpo de números de grau n. O homomorfismo σ : K −→
Rn definido por σ(a) = (x, y), onde x = (σ1(a), · · · , σr1(a)) são homomorfismo reais e
y = (R(σr1+1(a)), I(σr1+1(a)), · · · , R(σr1+r2(a)), I(σr1+2(a)) e r1 + 2r2 = n, é chamado
homomorfismo canônico ou homomorfismo de Minkowski. Para o caso em que K = Q(
√
d)
o homomorfismo de Minkowski σ : K −→ R2 é definido por σ(α) = (a+ b
√
d, a− b
√
d) se
K é um corpo inteiramente real ou σ(α) = (a, b) se K é um corpo inteiramente imaginário.
Teorema 2.3. Seja K um corpo de números de grau n. Se M ⊆ K é um Z−módulo livre
de posto n e (xj)1≤j≤n é uma base, então σ(M) é um reticulado em Rn com volume dado
por V ol(σ(M)) = 2−r2 |det(σj(xk))|.
Corollary 2.1. Se I é um ideal de OK, ∆K o discriminante do corpo K e N (I) = #OKI
é a norma do ideal I, então σ(OK) e σ(I) são reticulados em Rn com volumes dados,
respectivamente, por V ol(σ(OK)) = 2−r2 |∆K|
1
2 e V ol(σ(I)) = V ol(σK(OK))N (I)
Exemplo 2.4. Considere o corpo quadrático K = Q(
√
−3). Pelo Teorema 2, segue que
seu anel de inteiros é dado por Z
[
1+
√
−3
2
]
com Z-base {1, 1+
√
−3
2
}. O homomorfismo de
Minkowisk aplicado a um elemento α = a + b
(
1+
√
−3
2
)
∈ OK é dado por
(
a + b
2
,
√
−3
2
)
.
Desta forma, σ(OK) é um reticulado em R2 gerado por {(1, 0), (12 ,
√
−3
2
)} e o volume é
dado por
V ol(σ(OK)) =
1
2
·
∣
∣
∣
∣
det
(
1 1+
√
−3
2
1 1−
√
−3
2
)
∣
∣
∣
∣
2
=
4
√
3
2
.
Referências
[1] Samuel, P.; Algebraic theory of numbers, Hermann, Paris, 1967.
[2] Ribenboin, P.; Classical theory of algebraic numbers, Springer Verlag, New York,
2001.
[3] Atiyah, M. F.; MacDonald, I.G., Introduction to Commutative Algebra, AW Pu-
blishing Company, London, 1969.
[4] Marcus, D.A.: Numbers Fields, Springer-Velarg, New York, 1977.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Introduction to lattice-based cryptography
Eduardo Morais 1
Instituto de Computação - Unicamp, Campinas - SP
Ricardo Dahab 2
Instituto de Computação - Unicamp, Campinas - SP
Diego Aranha 3
Instituto de Computação - Unicamp, Campinas - SP
Resumo. Nesta palestra serão apresentados os conceitos fundamentais da criptografia base-
ada em reticulados. Dentre os fatores que tornam interessante o uso deste tipo de criptossis-
tema, podemos destacar a resistência contra algoritmos quânticos, sendo portanto uma das
posśıveis construções da chamada criptografia pós-quântica. Em particular, a criptografia
baseada em reticulados é contemplada por reduções de pior caso, uma condição mais forte
que a usual redução de caso médio de criptossistemas como o RSA por exemplo. Além
disso, com a utilização de reticulados ideais é posśıvel obter construções mais eficientes e
com aplicações muito interessantes, como é o caso de encriptação homomórfica e criptografia
funcional.
1 Resultados
As principais propostas de construção de criptografia baseada em reticulados serão
apresentadas, tomando como ponto de partida o texto de Peikert [6] que mostra a evolução
desta área de pesquisa na última década. O criptossistema NTRU foi proposto em 1996,
mas permaneceu sem demonstração de segurança até 2011, quando Stehlé e Steinfeld [7]
provaram que a segurança do esquema sob a hipótese de que o problema LWE polinomial
é computacionalmente dif́ıcil. Muito ainda precisa ser pesquisado e estudado sobre essas
hipóteses de segurança, mas os recentes resultados obtidos pela comunidade mostram que
de fato as reduções de pior caso são importantes, pois ataques propostos na literatura nos
últimos anos [2–5] são aplicáveis apenas aos casos onde a escolha de parâmetros justamente
não contemplou esta redução de pior caso, onde de forma resumida a norma do erro deve ser
escolhida pelo menos com tamanho O(
√
n), onde n é a dimensão do reticulado subjacente.
Serão apresentados alguns resultados importantes que surgiram recentemente, mos-
trando que é posśıvel utilizar criptografia baseada em reticulados para construir esquemas
de acordo de chaves usando a proposta de Alkim et al [1]. Estes esquemas são peça fun-
damental para o estabelecimento de conexões seguras na internet, por meio do protocolo
TLS [8] e portanto mostram que é fact́ıvel o uso desta tecnologia na prática.
1emorais@lasca.ic.unicamp.br
2rdahab@ic.unicamp.br
3dfaranha@ic.unicamp.br
2
Referências
[1] Erdem Alkim, Léo Ducas, Thomas Poppelmann, and Peter Schwabe. Post-quantum
key exchange - a new hope. Cryptology ePrint Archive, Report 2015/1092, 2015.
http://eprint.iacr.org/2015/1092.
[2] Yara Elias, Kristin E. Lauter, Ekin Ozman, and Katherine E. Stange. Provably weak
instances of ring-lwe. Cryptology ePrint Archive, Report 2015/106, 2015. http:
//eprint.iacr.org/2015/106.
[3] Scott Fluhrer. Quantum cryptanalysis of ntru. Cryptology ePrint Archive, Report
2015/676, 2015. http://eprint.iacr.org/2015/676.
[4] Kristin Lauter Hao Chen and Katherine E. Stange. Attacks on search rlwe. Cryptology
ePrint Archive, Report 2015/971, 2015. http://eprint.iacr.org/2015/971.
[5] Léo Ducas Martin Albrecht, Shi Bai. A subfield lattice attack on overstretched ntru
assumptions: Cryptanalysis of some fhe and graded encoding schemes. Cryptology
ePrint Archive, Report 2016/127, 2016. http://eprint.iacr.org/2016/127.
[6] Chris Peikert. A decade of lattice cryptography. Cryptology ePrint Archive, Report
2015/939, 2015. http://eprint.iacr.org/2015/939.
[7] Damien Stehlé and Ron Steinfeld. Making NTRU as Secure as Worst-Case Problems
over Ideal Lattices, pages 27–47. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
[8] Google webpage, 2016. https://security.googleblog.com/2016/07/
experimenting-with-post-quantum.html?m=1.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
O gerador self-shrinking modificado via o gerador
self-shrinking generalizado
Sara D. Cardell 1
Instituto de Matemática, Estat́ıstica e Computação Cient́ıfica, UNICAMP, Campinas, Brasil
Amparo Fúster-Sabater 2
Instituto de Tecnoloǵıas F́ısicas y de la Información, CSIC, Madrid, Espanha
Resumo. O gerador self-shrinking modificado foi criado recentemente para aplicações de
cifras de fluxo. Este gerador de sequências cifrantes é uma versão nova e melhorada do ge-
rador self-shrinking. Entretanto, podemos provar que as sequências produzidas por ambos
os geradores podem ser obtidas como sequênciasde sáıda do gerador self-shrinking genera-
lizado.
Resultados
O gerador self-shrinking modificado (MSSG), introduzido por Kanso em 2010 [3],
é um caso particular do gerador self-shrinking [4], onde a PN-sequência {ui} gerada por
um LFSR (linear feedback shift register) de comprimento máximo [1] é auto-decimada.
Neste caso, a regra de decimação é muito simples e pode ser descrita como segue: Dados
três bits consecutivos {u2i, u2i+1, u2i+2}, i = 0, 1, 2, . . . a sequência {sj}, conhecida como
sequência self-shrunken modificada, é obtida como
{
Se u2i + u2i+1 = 1 então sj = u2i+2
Se u2i + u2i+1 = 0 então u2i+2 é descartado.
Se L (́ımpar) for o comprimento do máximo LFSR que gera {ui}, então a complexidade
linear LC da sequência self-shrunken modificada correspondente vai satisfazer:
2b
L
3
c−1 ≤ LC ≤ 2L−1 − (L− 2),
e o peŕıodo T desta sequência vai satisfazer:
2b
L
3
c ≤ T ≤ 2L−1
como já foi provado em [3]. Como é usual, a chave deste gerador é o estado inicial do
registro que gera a PN-sequência {ui}.
1sdcardell@ime.unicamp.br
2amparo@iec.csic.es
2
Seja {ai} uma PN-sequência gerada por um LFSR de comprimento máximo de L
estágios. Seja G = (g0, g1, g2, ..., gL−1) ∈ F
L
2 um vetor binário L-dimensional e {vi} uma
sequência definida por: vi = g0ai+ g1ai−1+ g2ai−2+ · · ·+ gL−1ai−L+1 mod(2
L− 1). Para
n ≥ 0, a regra de decimação é determinada como segue:
{
Se ai = 1 então bj = vi
Se ai = 0 então vi é descartado.
A sequência de sáıda {bj}, denotada por b(G), é chamada sequência self-shrunken
generalizada associada a G (vide [2]).
À medida que G percorre FL2 , {vi} corresponde a cada uma das 2
L − 1 posśıveis
translações de {ai}. Além disso, o conjunto de sequências B(a) = {b(G) | G ∈ F
L
2 } é a
famı́lia de sequências self-shrunken generalizadas baseadas na PN-sequência {ai}.
Por outro lado, a sequência self-shrunken modificada obtida com um polinômio pri-
mitivo p(x) ∈ F2[x] de grau L pode ser também obtida a través do gerador self-shrinking
generalizado com um polinômio primitivo q(x) ∈ F2[x] do mesmo grau. Este polinômio é
determinado por: q(x) = (x+ α3)(x+ α6)(x+ α12) · · · (x+ α3·2
L−1
), com α raiz de p(x).
A implementação da sequência self-shrunken modificada via o gerador self-shrinking
modificado é muito mais eficiente, visto que requer um número menor de cálculos e uma
quantidade pequena de bits envolvidos nos cálculos.
Agradecimentos
O trabalho da primeira autora está apoiado pela FAPESP com número de processo
2015/07246-0. O trabalho da segunda autora está apoiado pelo Ministerio de Economı́a
y Competitividad (Espanha), sob o projeto TIN2014-55325-C2-1-R (ProCriCiS), e pela
Comunidad de Madrid (Espanha) sob o projeto S2013/ICE-3095-CM (CIBERDINE). As
autoras também agradecem aos fundos FEDER.
Referências
[1] Solomon W. Golomb. Shift Register-Sequences. Aegean Park Press, Laguna Hill,
California, 1982.
[2] Yupu Hu and Guozhen Xiao. Generalized self-shrinking generator. 50(4):714–719,
2004.
[3] Ali Kanso. Modified self-shrinking generator. Computers and Electrical Engineering,
36(1):993–1001, 2010.
[4] Willi Meier and Othmar Staffelbach. The self-shrinking generator. In Christian Cachin
and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 1994, volume
950, pages 205–214. Springer-Verlag, 1994.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Uma nota sobre códigos corretores de erros via espaços shift
de dimensão finita
Agnaldo José Ferrari 1
Departametno de Matemática, FC - Unesp, Bauru - SP
Tatiana Miguel Rodrigues de Souza 2
Departametno de Matemática, FC - Unesp, Bauru - SP
Resumo. A dinâmica simbólica é uma área em grande crescimento em Sistemas Dinâmicos,
pois as suas técnicas têm encontrado aplicações significativas em armazenamento e trans-
missão de dados. A noção de espaço Shift está implicita em alguns dos primeiros trabalhos
em dinâmica simbólica. Morse usou determinados Espaços Shifts para modelar alguns fluxos
geodésicos em superf́ıcie de curvatura negativa, onde um espaço de sequências foi descrito
como sendo uma lista expĺıcita de restrições sobre as sequências permitidas. Mais tarde, um
espaço de sequências foi descrito declarando os blocos autorizados que devem aparecer em
uma sequência bi-infinita. No entanto, os Espaços Shift foram formalmente definidos por
Smalle, que chamou tais espaços de Sub-Shifts, vendo-os como subconjuntos shift invarian-
tes de shifts completos. Neste trabalho apresentamos os Espaços Shift de dimensão finita
aplicados a Códigos Corretores de Erros utilizados na leitura e gravação de dados, como por
exemplo os utilizados em mı́dias eletrônicas.
Referências
[1] W. H. Gottschalk, G. A. Hedlund, Topological Dynamics, Amer. Math. Soc. Collo-
quium Publ. 36 (1955)
[2] J. Hadamard, Les surfaces a courbures opposées et leurs lignes geodesiques, Journal
de Mathematiques Pures et Appliqué. 4 (1898), 27-73.
[3] D. Lind, B. Marcus, An introduction to symbolic dynamics and coding, Cambridge
University Press. New York, 1995.
[4] M. Morse, A one-to-one representations of geodesics on a surface of negative curva-
ture, Amer. J. Math. 43 (1921) 33-51.
[5] M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math.
Soc. 22 (1921) 84-100.
1ferrari@fc.unesp.br
2tatimi@fc.unesp.br
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Alguns empacotamentos curiosos
Antonio Aparecido de Andrade 1
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Resumo. A teoria de códigos surgiu no ińıcio da década de 50, como parte complemen-
tar de um trabalho teórico do matemático americano Claude E. Shannon (1916 - 2001),
que em 1948 publicou uma série de resultados estabelecendo os limites teóricos para uma
comunicação confiável. Um dos principais problemas quando se deseja transmitir alguma
informação é garantir que esta chegue intacta ao destino, ou seja, que os dados recebidos
sejam confiáveis. Como dependemos de instrumentos eletrônicos para essa transmissão, sem-
pre estamos suscet́ıveis aos erros e às falhas desses instrumentos ou a erros dos canais em
que estas informações transitam. Quando se deseja transmitir uma mensagem por um canal
de comunicação, este podendo ser um cabo, circuito integrado, canal de radiofrequência,
entre outros, os dados percorrem o seguinte trajeto: sai da fonte, é codificado, passa pelo
canal que possui rúıdos, é recebida e codificada chegando ao destino.
1 Introdução
Em sistemas de comunicações o objetivo é transmitir dados de uma fonte até o usuário.
O meio usado é chamado de canal, que pode ser com ou sem fio. Na transmissão o canal
pode gerar distorções e o sinal recebido pode não ser o enviado. A teoria dos códigos
corretores de erros surgiu por volta de 1940-48, com os trabalhos de Shannon, provando
que encontrar bons códigos é equivalente a encontrar empacotamentos esféricos densos no
espaço euclidiano. Como curiosidade, temos que para as dimensões 2 e 3, os melhores
empacotamentos esféricos são conhecidos de todos e aparecem em lugares inusitados. No
caso bidimensional, os favos das colmeias, onde as abelhas depositam o mel, e para o
caso tridimensional, o empilhamento de laranjas, que é facilmente encontrado em feiras
livres. Nesse sentido, nesse trabalho apresentamos o conceito de reticulados enfocando
seus principais parâmetros como volume, densidade de empacotamento e densidade de
centro. Finalmente, apresentamos alguns exemplos de reticulados e de empacotamentos.
2 Resultados
O problema clássico do empacotamento esférico consiste em encontrar um arranjo de
esferas idênticas no espaço n-dimensional de forma que a fração do espaço coberto por essas
esferas seja a maior posśıvel. Ao estudar a densidade de empacotamento, um dos principaisproblemas é a obtenção de reticulados com alta densidade e que sejam ao mesmo tempo
1andrade@ibilce.unesp.br
2
manipuláveis. Dessa forma, estudar os empacotamentos reticulados equivale ao estudo dos
reticulados.
Definição 1. Sejam V um espaço vetorial de dimensão finita n sobre um corpo K, A ⊆ K
um anel e v1, · · · , vm vetores de V linearmente independentes sobre K com m ≤ n. Um
reticulado com base β = {v1, · · · , vm} é o conjunto dos elementos de V da forma
Hβ =
{
x =
m
∑
i=1
aivi, com ai ∈ A
}
.
O conjunto
Pβ =
{
x ∈ R : x =
n
∑
i=1
λivi, 0 ≤ λi < 1
}
,
é chamado de região fundamental de Hβ com relação a base {v1, · · · , vn}.
Definição 2. Seja Hβ ⊂ R
n um reticulado, com β = (v1, .., vn) uma base de Hβ. A
matriz geradora do reticulado Hβ é definida como sendo a matriz
B =





v11 v12 · · · v1n
v21 v22 · · · v2n
...
...
. . .
...
vn1 vn2 · · · vnn





onde vi = (vi1, vi2, · · · , vin),, para i = 1, ..., n.
Definição 3. Sejam um reticulado Hβ e B sua matriz geradora. Definimos a matriz de
Gram associada a matriz geradora por G = BtB.
Definição 4. Definimos o determinante de Hβ como o determinante de uma matriz de
Gram de Hβ e denotamos por det(Hβ), e, este número é o quadrado do volume de uma
região fundamental de Hβ.
Definição 5. Sejam Hβ ⊂ R
n um reticulado, β = (v1, .., vn) uma base de Hβ e Pβ a
região fundamental. Se vi = (vi1, vi2, · · · , vin), para i = 1, 2, · · · , n, definimos o volume da
região fundamental Pβ , como o módulo do determinante da matriz
B =





v11 v12 · · · v1n
v21 v22 · · · v2n
...
...
. . .
...
vn1 vn2 · · · vnn





.
O volume do reticulado Hβ é definido como Vol(Hβ) = Vol(Pβ).
3
Estamos interessados no empacotamento associado a um reticulado Hβ em que as
esferas tenham raio máximo. Para a determinação deste raio, observe que fixado k > 0,
a intersecção do conjunto compacto {x ∈ R; |x| ≤ k} com o reticulado Hβ é um conjunto
finito, de onde segue que o número Hβmin = min{|λ|; λ ∈ Hβ , λ 6= 0} está bem definido e
(Hβmin)
2 é chamado de norma mı́nima.
Observamos que ρ = Hβmin/2 é o maior raio para o qual é posśıvel distribuir esferas
centradas nos pontos de Hβ e obter um empacotamento, assim ρ é chamado raio de
empacotamento do reticulado. Dessa forma, estudar os empacotamentos reticulados
equivale ao estudo dos reticulados.
Denotando por B(ρ) a esfera com centro na origem e raio ρ, temos que a densidade
de empacotamento de Hβ é definida por
∆(Hβ) =
Volume da esfera
Volume da região fundamental
=
Vol(B(ρ))
Vol(Hβ)
=
Vol(B(1))ρn
Vol(Hβ)
.
Portanto, o problema se reduz ao estudo de um outro parâmetro, chamado de densi-
dade de centro, que é dado por
δ(Hβ) =
ρn
Vol(Hβ)
.
Logo, tiramos a seguinte relação
∆(Hβ) = Vol(B(1)) · δ(Hβ).
ou seja, a densidade de empacotamento de Hβ é igual ao produto entre o volume da esfera
com centro na origem e raio 1 e a densidade de centro de Hβ .
Como curiosidade, temos que para as dimensões 2 e 3, os melhores empacotamentos são
conhecidos de todos e aparecem em lugares inusitados. No caso bidimensional, os favos das
colmeias, onde as abelhas depositam o mel, e para o caso tridimensional, o empilhamento
de laranjas, que é facilmente encontrado em feiras livres.
Referências
[1] ] J.H. Conway; N.J.A. Sloane, Sphere packing, lattices and groups, Springer-Verlag,
New York, 1999.
[2] P. Samuel, Algebraic theory of numbers, Hermann, Paris, 1970.
Anais da V Jornada da Informação, 13 e 14 de outubro de 2016, Ibilce -
Unesp, São José do Rio Preto - SP
Potência de Ideais Primos
Trajano Pires da Nóbrega Neto 1
Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP
Resumo Dado um corpo de números abeliano K de grau primo p, no qual p não se ramifica,
os primos que se ramificam são precisamente aqueles que dividem o condutor de K.
1 Resultados
O principal resultado deste trabalho é a descrição das potências dos ideais primos
ramificados em K.
Referências
[1] L.C. Washington, Introduction to ciclotomic fields, Springer-Verlag, New York, 1982.
[2] D. A. Marcus, Number Fields, Springer-Verlag, New York, , 1977.
[3] J. L. N. Valter p-Extensões Galoisianas e Aplicações, Tese de Doutorado - UFC, 2015.
1trajano@ibilce.unesp.br