Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On computing logarithms over GF(2p)

Herlestam, Tore and Johannesson, Rolf LU (1981) In BIT Numerical Mathematics 21(3). p.326-334
Abstract
In this paper we present a new, heuristic method for computing logarithms over GF(2P).

When 2P-1 is a Mersenne prime <231-1 it works in very short running times on a

general purpose computer. It is based on the interdependent relations

f,~(t) = t-2~f(t) 2"

and

log f~s(t) = - 2' + 2" log f(t),

where f and frs are polynomials over GF(2).

Its cryptographic significance is discussed and it can be considered as an attempt to

swindle MITRE Corporation which reportedly is using a public key distribution system,

based on the presumed difficulty in computing logarithms over GF(2127).
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
BIT Numerical Mathematics
volume
21
issue
3
pages
326 - 334
publisher
Springer
external identifiers
  • scopus:0019689931
ISSN
0006-3835
DOI
10.1007/BF01941467
language
English
LU publication?
yes
additional info
The information about affiliations in this record was updated in December 2015. The record was previously connected to the following departments: Department of Information Technology (011014001)
id
51a974a3-8587-4c3d-9716-fa4b36529cc3 (old id 1056914)
date added to LUP
2016-04-04 09:42:49
date last changed
2025-10-14 13:23:07
@article{51a974a3-8587-4c3d-9716-fa4b36529cc3,
  abstract     = {{In this paper we present a new, heuristic method for computing logarithms over GF(2P).<br/><br>
When 2P-1 is a Mersenne prime &lt;231-1 it works in very short running times on a<br/><br>
general purpose computer. It is based on the interdependent relations<br/><br>
f,~(t) = t-2~f(t) 2"<br/><br>
and<br/><br>
log f~s(t) = - 2' + 2" log f(t),<br/><br>
where f and frs are polynomials over GF(2).<br/><br>
Its cryptographic significance is discussed and it can be considered as an attempt to<br/><br>
swindle MITRE Corporation which reportedly is using a public key distribution system,<br/><br>
based on the presumed difficulty in computing logarithms over GF(2127).}},
  author       = {{Herlestam, Tore and Johannesson, Rolf}},
  issn         = {{0006-3835}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{326--334}},
  publisher    = {{Springer}},
  series       = {{BIT Numerical Mathematics}},
  title        = {{On computing logarithms over GF(2p)}},
  url          = {{http://dx.doi.org/10.1007/BF01941467}},
  doi          = {{10.1007/BF01941467}},
  volume       = {{21}},
  year         = {{1981}},
}