A note on cyclic groups, finite fields, and the discrete logarithm problem
type: Item
instance of: scholarly article
title: A note on cyclic groups, finite fields, and the discrete logarithm problem
zbMATH Open document ID: 0749.11056
DOI: 10.1007/BF01189025
author: Alfred Menezes
author: Scott A. Vanstone
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1992-12-14T00:00:00Z
review text: Let \(F_ q\) denote the finite field of order \(q\) and \(E(F_ q)\) and elliptic curve over \(F_ q\). Previous work showed how the discrete logarithm problem in the additive group of \(E(F_ q)\) can be reduced to the discrete logarithm problem in \(F_{q^ k}\) for some integer \(k\) in the case \(gcd(\# E(F_ q),q)=1\). It is shown here how the logarithm problem in the curve of the Pell equation \(x^ 2-Dy^ 2=1\) can be reduced to the logarithm problem \(F_ q\) or \(F_{q^ 2}\), \(q\) odd. It is also shown that the logarithm problem in certain cyclic subgroups of \(GL(n,q)\), the group of nonsingular \(n\times n\) matrices over \(F_ q\), can be reduced to the logarithm problem in an extension of \(F_ q\). The results indicate the group \(G\) must be carefully chosen for cryptographic purposes.
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 79159
zbMATH Keywords: cryptography
zbMATH Keywords: finite field
zbMATH Keywords: elliptic curve
zbMATH Keywords: discrete logarithm
zbMATH Keywords: cyclic subgroups
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: A key-exchange system based on imaginary quadratic fields
cites work: Fast evaluation of logarithms in fields of characteristic two
cites work: Discrete logarithms in \(\mathrm{GF}(p)\)
cites work: New directions in cryptography
cites work: A subexponential-time algorithm for computing discrete logarithms over&lt;tex&gt;GF(p^2)&lt;/tex&gt;
cites work: Q5614003
cites work: Elliptic Curves
cites work: Elliptic Curve Cryptosystems
cites work: Hyperelliptic cryptosystems
cites work: Q3360980
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Approximate formulas for some functions of prime numbers
cites work: Q3710637
Recommended article: A note on discrete logarithms in finite fields
Recommended article: The discrete logarithm problem in some groups
Recommended article: On the discrete logarithm problem in finite fields of fixed characteristic
Recommended article: Q3032345
Recommended article: Discrete logarithms for finite groups
Recommended article: On the discrete logarithm problem in class groups of curves
Recommended article: The discrete logarithm problem in the group of non-singular circulant matrices
Recommended article: Q5150656
Recommended article: ON THE COMPLEXITY OF DISCRETE LOGARITHM PROBLEM IN AN INTERVAL IN A FINITE CYCLIC GROUP WITH EFFICIENT INVERSION
Recommended article: Q4279568
description: scientific article; zbMATH DE number 79159