The critical group from a cryptographic perspective

被引：12

作者：

Biggs, Norman ^{[1
]}

机构：

[1] London Sch Econ, Dept Math, London WC2A 2AE, England

来源：

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY | 2007年 / 39卷

关键词：

D O I：

10.1112/blms/bdm070

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The critical group of a graph is an abelian group that arises in several contexts, and there are some similarities with the groups that are used in cryptography. We construct a family of graphs with critical groups that are cyclic, and discuss the associated computational problems using algorithms based on the theory of 'chip-firing'.

引用

页码：829 / 836

页数：8

共 8 条

[1] The lattice of integral flows and the lattice of integral cuts on a finite graph [J].

Bacher, R ;

delaHarpe, P ;

Nagnibeda, T .

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 1997, 125 (02) :167-198

[2] Algebraic potential theory on graphs [J].

Biggs, N .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 1997, 29 :641-682

[3] Chip-firing and the critical group of a graph [J].

Biggs, NL .

JOURNAL OF ALGEBRAIC COMBINATORICS, 1999, 9 (01) :25-45

[4]

CHEN S, 2006, CRITICAL GROUPS HOME

[5] A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS [J].

ELGAMAL, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :469-472

[6]

HONSBERGER R, 1985, DOLCIANI MATH EXPOSI, V9, P102

[7] Jacobian tori associated with a finite graph and its Abelian covering graphs [J].

Kotani, M ;

Sunada, T .

ADVANCES IN APPLIED MATHEMATICS, 2000, 24 (02) :89-110

[8]

Van den Heuvel J, 2001, COMB PROBAB COMPUT, V10, P505, DOI 10.1017/So963548301004886

← 1 →