Using number fields to compute logarithms in finite fields

Oliver Schirokauer

Mathematics of Computation 2000

Time bound

L_Q[1/3, (64/9)^1/3], Q=pⁿ, n fixed

Space bound

Not extracted from the source

Source / version date

24 May 1999

Comparison variant

Fixed extension degree · classical heuristic

Cost scale

L_Q[1/3,c]

coefficientExact

(64/9)^{1/3}

Assumptions and source notes

The paper describes the NFS adaptation for finite fields of arbitrary fixed extension degree; prime fields are degree one. The conjectured expected running time includes the complete computation. The date is the electronic publication (24 May 1999), while the journal issue is dated 2000. The source notes that its prime-field case was already covered by the author’s 1993 paper.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

@article{schirokauer00,
  author = {Oliver Schirokauer},
  title = {{Using number fields to compute logarithms in finite fields}},
  journal = {Mathematics of Computation 69(231), 1267–1283},
  year = {2000},
  doi = {10.1090/S0025-5718-99-01137-0},
  url = {https://doi.org/10.1090/S0025-5718-99-01137-0},
  keywords = {discrete logarithms, number field sieve, fixed extension degree},
  cr_date = {1999-05-24},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 69(231), 1267–1283},
  cr_author_ids = {oliver-schirokauer}
}