Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 4
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Non existence of almost Moore digraphs of diameter three

  • Conde Colom, Josep
  • Gimbert i Quintilla, Joan
  • Miret, Josep M. (Josep Maria)
  • Moreno Chiral, Ramiro
  • Gonzàlez, J.
Almost Moore digraphs appear in the context of the degree/diameter problem as a class of extremal directed graphs, in the sense that their order is one less than the unattainable Moore bound M(d; k) = 1 + d + + dk, where d > 1 and k > 1 denote the maximum out-degree and diameter, respectively. So far, the problem of their existence has only been solved when d = 2; 3 or k = 2. In this paper, we prove that almost Moore digraphs of diameter k = 3 do not exist for any degree d. The enumeration of almost Moore digraphs of degree d and diameter k = 3 turns out to be equivalent to the search of binary matrices A ful lling that AJ = dJ and I+A+A2+A3 = J +P, where J denotes the all-one matrix and P is a permutation matrix . We use spectral techniques in order to show that such equation has no (0; 1)-matrix solutions. More precisely, we obtain the factorization in Q[x] of the characteristic polynomial of A, in terms of the cycle structure of P, we compute the trace of A and we derive a contradiction on some algebraic multiplicities of the eigenvalues of A. In order to get the factorization of det(xI - A) we determine when the polynomials Fn(x) = n(1 + x + x2 + x3) are irreducible in Q[x], where n(x) denotes the n-th cyclotomic polynomial, since in such case they become `big pieces' of det(xI - A). By using concepts and techniques from algebraic number theory, we prove that Fn(x) is always irreducible in Q[x], unless n = 1; 10. So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory., Partially supported by the Ministry of Science and Technology, Spain, under the projects TIC2003- 09188, MTM2006-15038-C02-02 and MTM2007-66842-C02-02.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Algorithms and cryptographic protocols using elliptic curves

  • Miret, Josep M. (Josep Maria)
  • Moreno Chiral, Ramiro
  • Pujolàs Boix, Jordi
  • Valls Marsal, Magda
En els darrers anys, la criptografia amb corbes el.líptiques ha adquirit una importància creixent, fins a arribar a formar part en la actualitat de diferents estàndards industrials. Tot i que s'han dissenyat variants amb corbes el.líptiques de criptosistemes clàssics, com el RSA, el seu màxim interès rau en la seva aplicació en criptosistemes basats en el Problema del Logaritme Discret, com els de tipus ElGamal. En aquest cas, els criptosistemes el.líptics garanteixen la mateixa seguretat que els construïts sobre el grup multiplicatiu d'un cos finit primer, però amb longituds de clau molt menor. Mostrarem, doncs, les bones propietats d'aquests criptosistemes, així com els requeriments bàsics per a que una corba sigui criptogràficament útil, estretament relacionat amb la seva cardinalitat. Revisarem alguns mètodes que permetin descartar corbes no criptogràficament útils, així com altres que permetin obtenir corbes bones a partir d'una de donada. Finalment, descriurem algunes aplicacions, com són el seu ús en Targes Intel.ligents i sistemes RFID, per concloure amb alguns avenços recents en aquest camp., The relevance of elliptic curve cryptography has grown in recent years, and today represents a cornerstone in many industrial standards. Although elliptic curve variants of classical cryptosystems such as RSA exist, the full potential of elliptic curve cryptography is displayed in cryptosystems based on the Discrete Logarithm Problem, such as ElGamal. For these, elliptic curve cryptosystems guarantee the same security levels as their finite field analogues, with the additional advantage of using significantly smaller key sizes. In this report we show the positive properties of elliptic curve cryptosystems, and the requirements a curve must meet to be useful in this context, closely related to the number of points. We survey methods to discard cryptographically uninteresting curves as well as methods to obtain other useful curves from a given one. We then describe some real world applications such as Smart Cards and RFID systems and conclude with a snapshot of recent developments in the field.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Non existence of almost Moore digraphs of diameter three

  • Conde Colom, Josep
  • Gimbert i Quintilla, Joan
  • Miret, Josep M. (Josep Maria)
  • Moreno Chiral, Ramiro
  • Gonzàlez, J.
Almost Moore digraphs appear in the context of the degree/diameter problem as a class of extremal directed graphs, in the sense that their order is one less than the unattainable Moore bound M(d; k) = 1 + d + + dk, where d > 1 and k > 1 denote the maximum out-degree and diameter, respectively. So far, the problem of their existence has only been solved when d = 2; 3 or k = 2. In this paper, we prove that almost Moore digraphs of diameter k = 3 do not exist for any degree d. The enumeration of almost Moore digraphs of degree d and diameter k = 3 turns out to be equivalent to the search of binary matrices A ful lling that AJ = dJ and I+A+A2+A3 = J +P, where J denotes the all-one matrix and P is a permutation matrix . We use spectral techniques in order to show that such equation has no (0; 1)-matrix solutions. More precisely, we obtain the factorization in Q[x] of the characteristic polynomial of A, in terms of the cycle structure of P, we compute the trace of A and we derive a contradiction on some algebraic multiplicities of the eigenvalues of A. In order to get the factorization of det(xI - A) we determine when the polynomials Fn(x) = n(1 + x + x2 + x3) are irreducible in Q[x], where n(x) denotes the n-th cyclotomic polynomial, since in such case they become `big pieces' of det(xI - A). By using concepts and techniques from algebraic number theory, we prove that Fn(x) is always irreducible in Q[x], unless n = 1; 10. So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory., Partially supported by the Ministry of Science and Technology, Spain, under the projects TIC2003- 09188, MTM2006-15038-C02-02 and MTM2007-66842-C02-02.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Algorithms and cryptographic protocols using elliptic curves

  • Miret, Josep M. (Josep Maria)
  • Moreno Chiral, Ramiro
  • Pujolàs Boix, Jordi
  • Valls Marsal, Magda
En els darrers anys, la criptografia amb corbes el.líptiques ha adquirit una importància creixent, fins a arribar a formar part en la actualitat de diferents estàndards industrials. Tot i que s'han dissenyat variants amb corbes el.líptiques de criptosistemes clàssics, com el RSA, el seu màxim interès rau en la seva aplicació en criptosistemes basats en el Problema del Logaritme Discret, com els de tipus ElGamal. En aquest cas, els criptosistemes el.líptics garanteixen la mateixa seguretat que els construïts sobre el grup multiplicatiu d'un cos finit primer, però amb longituds de clau molt menor. Mostrarem, doncs, les bones propietats d'aquests criptosistemes, així com els requeriments bàsics per a que una corba sigui criptogràficament útil, estretament relacionat amb la seva cardinalitat. Revisarem alguns mètodes que permetin descartar corbes no criptogràficament útils, així com altres que permetin obtenir corbes bones a partir d'una de donada. Finalment, descriurem algunes aplicacions, com són el seu ús en Targes Intel.ligents i sistemes RFID, per concloure amb alguns avenços recents en aquest camp., The relevance of elliptic curve cryptography has grown in recent years, and today represents a cornerstone in many industrial standards. Although elliptic curve variants of classical cryptosystems such as RSA exist, the full potential of elliptic curve cryptography is displayed in cryptosystems based on the Discrete Logarithm Problem, such as ElGamal. For these, elliptic curve cryptosystems guarantee the same security levels as their finite field analogues, with the additional advantage of using significantly smaller key sizes. In this report we show the positive properties of elliptic curve cryptosystems, and the requirements a curve must meet to be useful in this context, closely related to the number of points. We survey methods to discard cryptographically uninteresting curves as well as methods to obtain other useful curves from a given one. We then describe some real world applications such as Smart Cards and RFID systems and conclude with a snapshot of recent developments in the field.