Gibt es eine bessere als lineare Untergrenze für Factoring und diskretes Log?

Gibt es Referenzen, die Details zu Schaltkreisuntergrenzen für bestimmte schwierige Probleme liefern, die in der Kryptographie auftreten, wie z. B. Integer Factoring, Prim / Composite Discrete Logarithm Problem und seine Variante über Punktgruppen elliptischer Kurven (und ihre höherdimensionalen abelschen Varietäten) und das Allgemeine verstecktes Untergruppenproblem?

Speziell hat eines dieser Probleme mehr als eine lineare Komplexitätsuntergrenze?

@ Suresh: Nach deinem Rat, hier ist meine "Antwort". Der Status der unteren Schaltkreisgrenzen ist ziemlich bedrückend. Hier sind die "aktuellen Rekorde":

• $4n-4$ für Schaltkreise über und für Schaltkreise über und computing ; Redkin (1973). Diese Grenzen sind eng. $\{\land,\lor,\neg\}$$7n-7$$\{\land,\neg\}$$\{\lor,\neg\}$$\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$
• $5n-o(n)$ für Schaltungen über die Basis mit allen Fanin-2-Gattern mit Ausnahme der Parität und ihrer Negation; Iwama und Morizumi (2002).
• ( 7 / 3 ) n - O ( 1 ) 3 - n - O ( 1 $3n-o(n)$ für allgemeine Schaltungen über die Basis mit allen Fanin-2-Toren; Blum (1984). Arist Kojevnikov und Sasha Kulikov aus Petersburg haben einen einfacheren Beweis für eine Untergrenze gefunden. Der Vorteil ihres Beweises ist seine Einfachheit, nicht numerisch. Später gaben sie einen einfachen Beweis der -Untergrenze für allgemeine Schaltkreise (alle Fanin-2-Gatter sind erlaubt). Wenn auch für sehr komplizierte Funktionen - affine Dispergierer. Die Artikel sind hier online . $(7/3)n-o(1)$$3n-o(1)$
• { ∧ , ∨ , ¬ $n^{3-o(1)}$ für Formeln über ; Hastad (1998). $\{\land,\lor,\neg\}$
• 2 Ω ( n 2 / log 2 n ) Ω ( n 3 / 2 / log n $\Omega(n^2/\log n)$ für allgemeine Fanin- Formeln, für deterministische Verzweigungsprogramme und für nicht deterministische Verzweigungsprogramme; Nechiporuk (1966). $2$$\Omega(n^2/\log^2 n)$$\Omega(n^{3/2}/\log n)$

Also, Ihre Frage "Haben speziell diese Probleme mehr als eine lineare Komplexitätsuntergrenze?" bleibt weitestgehend offen (bei Stromkreisen). Mein Appell an alle jungen Forscher: Vorwärts, diese "Barrieren" sind nicht unzerbrechlich! Aber versuchen Sie, "unnatürlich" im Sinne von Rasborow und Ruditsch zu denken.