Some results on computational complexity

zbMath0361.68070MaRDI QIDQ1239605

Volker Strassen

Publication date: 1976

Published in: Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV) (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/146659

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Factorization (11Y05) Computational methods for problems pertaining to field theory (12-08)

Related Items (18)

A babystep-giantstep method for faster deterministic integer factorization ⋮ Few Product Gates But Many Zeros ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ Subresultants of \((x-\alpha)^m\) and \((x-\beta)^n\), Jacobi polynomials and complexity ⋮ Fast norm computation in smooth-degree abelian number fields ⋮ An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient ⋮ A search for Wieferich and Wilson primes ⋮ Smoothness and factoring polynomials over finite fields ⋮ Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ On the ultimate complexity of factorials ⋮ A deterministic algorithm for integer factorization ⋮ An exponent one-fifth algorithm for deterministic integer factorisation ⋮ A time-space tradeoff for Lehman’s deterministic integer factorization method ⋮ A deterministic algorithm for finding \(r\)-power divisors ⋮ A Reduction of Integer Factorization to Modular Tetration ⋮ Faster deterministic integer factorization ⋮ Deterministic factorization of sums and differences of powers

This page was built for publication: Some results on computational complexity