Auf der Grundlage der Quantenmechanik wurden in den vergangenen Jahren
neue Rechnermodelle entwickelt, die im Hinblick auf polynomiale
Berechenbarkeit möglicherweise mächtiger sind als klassische
Turingmaschinen. Das Problem der Primfaktorzerlegung läßt sich auf
einem Quantenrechner in polynomialer Zeit lösen, während alle dafür
bisher bekannten Verfahren auf herkömmlichen Rechnern exponentiell
sind. Falls es gelingt, Quantenrechner physikalisch zu realisieren,
würde dies den Begriff der polynomialen Berechenbarkeit ebenso wie die
Sicherheit heutiger Kryptosysteme grundsätzlich in Frage stellen.