Advanced

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
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
id
51a974a3-8587-4c3d-9716-fa4b36529cc3 (old id 1056914)
date added to LUP
2008-04-11 13:47:56
date last changed
2016-10-13 04:35:44
@misc{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    = {ARRAY(0xc4fbf68)},
  series       = {BIT Numerical Mathematics},
  title        = {On computing logarithms over GF(2p)},
  url          = {http://dx.doi.org/10.1007/BF01941467},
  volume       = {21},
  year         = {1981},
}