Primzahlen zur Verschlüsselung

56 views
Skip to first unread message

Wendelin Uez

unread,
Nov 28, 2021, 6:34:01 AM11/28/21
to
Die Sicherheit öffentlicher Schlüssel zur Verschlüsselung und privater
Schlüssel zur Entschlüsselung läge in der Verwendung zweier möglichst großer
Primzahlen, lese ich immer.

Wieviele Primzahlen sind eigentlich schon bekannt?

Ist die Zahl der bekannten Primzahlpaare endlich, und wäre sie im Hinblick
auf ein Durchprobieren aller Paare auch gar nicht mal so riesig, als daß
nicht alle durchprobiert werden können., wäre die Sicherheit doch eher nicht
vorhanden?



Klaus Pommerening

unread,
Nov 28, 2021, 8:12:02 AM11/28/21
to
Wendelin Uez zweifelt:
> Die Sicherheit öffentlicher Schlüssel zur Verschlüsselung und privater
> Schlüssel zur Entschlüsselung läge in der Verwendung zweier möglichst
> großer Primzahlen, lese ich immer.
> Wieviele Primzahlen sind eigentlich schon bekannt?

Bekannte Primzahlen sind schlecht für die Verschlüsselung, weil
ein Angreifer diese versuchsweise ausprobieren kann. Was man
braucht sind zufällig erzeugte Primzahlen. Und davon gibt es
sehr viele: Die Wahrscheinlichkeit, dass eine k-Bit-Zahl prim ist,
ist ungefähr 1.44/k. Zum Beispiel sind von den 2^256 (ungefähr 10^80)
natürlichen Zahlen der Länge 256 Bit (ca. 80 Dezimalstellen) mehr als
10^77 prim, ungefähr 10^26 mal so viele, wie die Erde Atome hat.
Die kann niemand alle kennen oder gar durchprobieren.

Und für die Verschlüsselung werden noch viel größere Primzahlen
verwendet, von denen es noch sehr viel mehr gibt.

> Ist die Zahl der bekannten Primzahlpaare endlich, und wäre sie im
> Hinblick auf ein Durchprobieren aller Paare auch gar nicht mal so
> riesig, als daß nicht alle durchprobiert werden können., wäre die
> Sicherheit doch eher nicht vorhanden?

Wäre die heutige Rechenkapazität schon seit Beginn des Universums
vorhanden, wären in dieser Zeit weniger als 10^30 CPU-Zyklen möglich
gewesen, astronomisch weit davon entfernt, alle Primzahlen oder gar
alle Paare von Primzahlen durchprobieren zu können.
--
Klaus Pommerening
Wieviel ist 2 + 2?
Buddhist: Alles ist Eins.

Martin Vaeth

unread,
Nov 28, 2021, 9:37:32 AM11/28/21
to
Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
> Wendelin Uez zweifelt:
>> Die Sicherheit öffentlicher Schlüssel zur Verschlüsselung und privater
>> Schlüssel zur Entschlüsselung läge in der Verwendung zweier möglichst
>> großer Primzahlen, lese ich immer.
>> Wieviele Primzahlen sind eigentlich schon bekannt?
>
> Bekannte Primzahlen sind schlecht für die Verschlüsselung, weil
> ein Angreifer diese versuchsweise ausprobieren kann. Was man
> braucht sind zufällig erzeugte Primzahlen. Und davon gibt es
> sehr viele: Die Wahrscheinlichkeit, dass eine k-Bit-Zahl prim ist,
> ist ungefähr 1.44/k. Zum Beispiel sind von den 2^256 (ungefähr 10^80)
> natürlichen Zahlen der Länge 256 Bit (ca. 80 Dezimalstellen) mehr als
> 10^77 prim, ungefähr 10^26 mal so viele, wie die Erde Atome hat.
> Die kann niemand alle kennen oder gar durchprobieren.

Also: Man nimmt genügend viele Zufallszahlen und probiert, bis man eine
hat, die prim ist. Der *Test*, ob eine untersuchte Zahl prim ist,
geht relativ schnell, nämlich in O(k) (seit ein paar Jahren bekannt);
ich bezweifle allerdings, dass dieser Algorithmus in der Praxis dafür
benutzt wird, denn er ist (für große Zahlen) unhandlich zu
implementieren, und die in "O" versteckte Konstante ist vermutlich groß.
Man braucht aber gar nicht einen so 100% zuverlässigen Test, sondern
es genügt, die Wahrscheinlichkeit einer Fehleinschätzung so klein zu
machen, dass sie für alle praktischen Zwecke keine Rolle mehr spielt.
Das geht wesentlich schneller und einfacher, z.B. mit dem
Miller-Rabin-Test.

>> Hinblick auf ein Durchprobieren aller Paare

Ein Angreifer muss nicht alle Paare durchprobieren, weil er das
Produkt kennt. *Einen* Faktor zu kennen, reicht ihm aus.

> Wäre die heutige Rechenkapazität schon seit Beginn des Universums
> vorhanden, wären in dieser Zeit weniger als 10^30 CPU-Zyklen möglich
> gewesen

Falls man nur *einen* Rechner hätte. Und dieser kein Quantencomputer ist.
Bei Quantencomputern reichen vermutlich k-1 QuBit, wenn ich die
Definition von QuBit richtig verstanden habe (-1, weil gerade
Zahlen >2 keine Primzahlen sind. Möglicherweise braucht man aber auch
2k-1 QuBit, weil man ja noch dividieren muss - ein Experte möge
das bitte klar stellen.)
In 1-2 Jahren wird es wohl möglich sein, hier k = 256 zu erreichen, oder
vielleicht sogar aktuell benutzte Größen wie k = 4096.
Man bedenke: Ein solcher Computer kann dann die öffentlichen Datenbanken
aller öffentlichen Schlüssel in wenigen Minuten bearbeiten, und die
Ausgabe dieses Prozesses ermöglicht (auch im Nachhinein) das Entschlüsseln
der gesamten derzeit existierenden RSA-verschlüsselten Kommunikation.

Carlo XYZ

unread,
Nov 28, 2021, 1:29:02 PM11/28/21
to
Martin Vaeth schrieb am 28.11.21 um 15:37:

> Ein Angreifer muss nicht alle Paare durchprobieren, weil er das
> Produkt kennt. *Einen* Faktor zu kennen, reicht ihm aus.
>
>> Wäre die heutige Rechenkapazität schon seit Beginn des Universums
>> vorhanden, wären in dieser Zeit weniger als 10^30 CPU-Zyklen möglich
>> gewesen
>
> Falls man nur *einen* Rechner hätte. Und dieser kein Quantencomputer ist.
> Bei Quantencomputern reichen vermutlich k-1 QuBit, wenn ich die
> Definition von QuBit richtig verstanden habe (-1, weil gerade
> Zahlen >2 keine Primzahlen sind. Möglicherweise braucht man aber auch
> 2k-1 QuBit, weil man ja noch dividieren muss - ein Experte möge
> das bitte klar stellen.)

Der Experte heißt Google:

<https://de.wikipedia.org/wiki/Shor-Algorithmus>

2n+3 Qubits, wenn n die Länge der Zahl in Binärdarstellung ist.

Carlo XYZ

unread,
Nov 28, 2021, 2:13:16 PM11/28/21
to
Carlo XYZ schrieb am 28.11.21 um 19:29:

> 2n+3 Qubits, wenn n die Länge der Zahl in Binärdarstellung ist.

sorry, "wenn n die Zahl ist".

Martin Vaeth

unread,
Nov 28, 2021, 2:24:41 PM11/28/21
to
Carlo XYZ <carl...@invalid.invalid> schrieb:
>> Bei Quantencomputern reichen vermutlich k-1 QuBit, wenn ich die
>> Definition von QuBit richtig verstanden habe (-1, weil gerade
>> Zahlen >2 keine Primzahlen sind. Möglicherweise braucht man aber auch
>> 2k-1 QuBit, weil man ja noch dividieren muss - ein Experte möge
>> das bitte klar stellen.)
>
> Der Experte heißt Google:
>
><https://de.wikipedia.org/wiki/Shor-Algorithmus>

Als ich mir den Artikel seinerzeit angeschaut hatte, war noch von O((log n)^3)
die Rede, und der Algorithmus nur in ein paar Zeilen grob skizziert - nicht
ausreichend, um ihn zu verstehen, wenn man die zulässigen Operationen bei
Quantenrechnern nicht in physikalischen Details kennt.
Interessant: Die genaue Zahl wurde anscheinend erst Anfang 2020 in den Artikel
eingeführt und dann mehrmals editiert und rückgängig gemacht - was mit meiner
Erfahrung übereinstimmt, dass längere Zeit kein genauer Konsens über die
Definition eines Qubit und die zulässigen Operationen existierte, sondern die
Details Marketing-abhängig waren. Inzwischen scheint aber Konsens zu bestehen.

Martin Vaeth

unread,
Nov 28, 2021, 2:39:35 PM11/28/21
to
Das ist mit Sicherheit ein Tippfehler in Wikipedia (die History zeigt,
dass n und N in der Einleitung kürzlich mehrmals ausgetauscht wurde,
und anscheinend ging dabei was schief).

Ansonsten wäre der Algorithmus ja schon bei Zahlen der
Größenordnung 256-bit vollkommen überfordert, und es wäre auch
im Widerspruch zur Aussage
"im fehlerfreien Fall wären es nur einige tausend"
(bei einer 2048-bit Zahl).

Carlo XYZ

unread,
Nov 28, 2021, 3:22:06 PM11/28/21
to
Martin Vaeth schrieb am 28.11.21 um 20:39:
Ätzend. Die Länge der Bitdarstellung ist ja eigentlich auch der
übliche Inputparameter. Ich hatte mir zuerst das Papier angeschaut.
Darin steht:

"... our construction uses 3n+0.002nlgn logical qubits,
0.3n3+0.0005n3lgn Toffolis, and 500n2+n2lgn measurement
depth to factor n-bit RSA integers."

Den konstanten Summanden 2 konnte ich zwar nirgends
entdecken, aber daher stammt meine Interpretation von n.
Danach schaute ich nochmal, ohne weiter nachzudenken,
in den Wikipedia-Artikel. Man sollte vorsichtiger als
vorsichtig sein :-)

Klaus Pommerening

unread,
Nov 29, 2021, 12:44:49 AM11/29/21
to
Martin Vaeth überschätzt die Rechenkapazität:
> Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
>> Wäre die heutige Rechenkapazität schon seit Beginn des Universums
>> vorhanden, wären in dieser Zeit weniger als 10^30 CPU-Zyklen möglich
>> gewesen
> Falls man nur *einen* Rechner hätte.

Äh, nein. Sondern wenn man *alle* heute existierenden Rechner
hätte.

> Und dieser kein Quantencomputer ist.

Im Prinzip ja. Aber bei einer vollständigen Suche hat ein
Quantencomputer keinen nennenswerten Vorteil (machbare
Bitlänge verdoppelt sich, d. h., die Größe des Suchraums
wird quadriert). Einen nennenswerten theoretischen Vorteil
hätte ein Quantencomputer nur beim Faktorisieren (dem eigentlich
relevanten Angriff auf RSA-artige Verfahren). Aber da warten
wir mal in Ruhe ab, wie stabil Quantencomputer Rechenvorgänge
dieser Größenordnung dermaleinst erledigen können. Erstmal
haben sie noch selbst bei einfachen Berechnungen große Probleme
mit der Fehlerkorrektur.
--
Klaus Pommerening
Leute, tragt FFP2-Masken! Sonst impfen SIE euch per Sprühnebel!!

Martin Vaeth

unread,
Nov 29, 2021, 1:41:31 PM11/29/21
to
Klaus Pommerening <pomm...@uni-mainz.de> wrote:
> Martin Vaeth überschätzt die Rechenkapazität:
> > Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
> >> Wäre die heutige Rechenkapazität schon seit Beginn des Universums
> >> vorhanden, wären in dieser Zeit weniger als 10^30 CPU-Zyklen möglich
> >> gewesen
> > Falls man nur *einen* Rechner hätte.
>
> Äh, nein. Sondern wenn man *alle* heute existierenden Rechner
> hätte.

Diese paar Nulllen mehr oder weniger halte ich für vernachlässigbar.
Ich meinte eher, dass man in diesem Gedankenspiel das gesamte
Universum zur Berechnung benutzen könnte. Dann wäre die Zahl schon
signifikant größer.

> > Und dieser kein Quantencomputer ist.
>
> Im Prinzip ja. Aber bei einer vollständigen Suche hat ein
> Quantencomputer keinen nennenswerten Vorteil [...]
> hätte ein Quantencomputer nur beim Faktorisieren [...]

Und der Algorithmus zum Faktorisieren schöpft durch die
Mehrdeutigkeit den gesamten Suchraum aus. Insofern kann ich
Deinen ersten Satz nicht nachvollziehen.

> Aber da warten
> wir mal in Ruhe ab, wie stabil Quantencomputer Rechenvorgänge
> dieser Größenordnung dermaleinst erledigen können. Erstmal
> haben sie noch selbst bei einfachen Berechnungen große Probleme
> mit der Fehlerkorrektur.

Ich dachte, die knapp 100 QuBit, die man derzeit erreichen kann,
sind (zumindest für kurze Berechnungen) stabil, wenn man nur oft
genug wiederholt. Aber Genaus weiß ich nicht.

Klaus Pommerening

unread,
Nov 29, 2021, 3:29:24 PM11/29/21
to
Martin Vaeth hakt nach:
> Klaus Pommerening <pomm...@uni-mainz.de> wrote:
>> Im Prinzip ja. Aber bei einer vollständigen Suche hat ein
>> Quantencomputer keinen nennenswerten Vorteil [...]
>> hätte ein Quantencomputer nur beim Faktorisieren [...]
>
> Und der Algorithmus zum Faktorisieren schöpft durch die
> Mehrdeutigkeit den gesamten Suchraum aus. Insofern kann ich
> Deinen ersten Satz nicht nachvollziehen.

Hä? Wie meinen? Vollständige Suche heißt: Ich nehme jedes Element
einer Menge (in irgendeiner Reihenfolge) her und untersuche es auf ein
bestimmtes Kriterium. Da sind Quantencomputer (bisher nur theoretisch)
etwas im Vorteil, aber nicht entscheidend.

Im Fall der Faktorisierung einer Zahl n wäre dieser naive Algorithmus:
Durchlaufe alle natürlichen Zahlen m der Reihe nach und prüfe, ob m|n.
Aufwand im Mittel n/2, das ist exponentiell in Abhängigkeit von
der Stellenzahl von n, die bekanntlich log(n) ist.
Die besseren Faktorisierungsalgorithmen funktionieren ganz anders,
sind viel effizienter, und mit einem Quantencomputer (theoretisch)
noch mal viel effizienter, nämlich polynomial in der Stellenzahl
(der berühmte Shor-Algorithmus).

>> Aber da warten
>> wir mal in Ruhe ab, wie stabil Quantencomputer Rechenvorgänge
>> dieser Größenordnung dermaleinst erledigen können. Erstmal
>> haben sie noch selbst bei einfachen Berechnungen große Probleme
>> mit der Fehlerkorrektur.
>
> Ich dachte, die knapp 100 QuBit, die man derzeit erreichen kann,
> sind (zumindest für kurze Berechnungen) stabil, wenn man nur oft
> genug wiederholt. Aber Genaus weiß ich nicht.

Ja, aber genau diese unverzichtbaren Wiederholungen fressen den
Effizienzvorteil der Quantencomputer wieder auf. Es ist noch nicht
theoretisch geklärt, ob das naturgesetzmäßig so sein muss.
--
Klaus Pommerening
Lieber 200 Euro für ein gefälschtes Impfzertifikat als die Spritze
umsonst.

Ralf Schneider

unread,
Nov 30, 2021, 12:08:46 PM11/30/21
to
Am Sun, 28 Nov 2021 15:22:31 +0100 schrieb Gerhard Strangar:

> Die eine Zahl kennst du ja, die ist öffentlich, Du mußt "nur" die andere
> erraten. Nehmen wir an, sie hätte 384 Bit, die Anzahl der Primzahlen <=
> x kann man annähern durch x/ln(x). Dann hast Du knapp 2^374 Primzahlen
> mit 384 Bit. Eine CPU mit 256 Kernen und 4 GHz macht weniger als 2^65
> Operationen pro Jahr.
> Selbst die Export-Version vom Netscape konnte 512 Bit asymmetrisch, aber
> nur 40 Bit symmetrisch, d.h. alle Primzahlen ausprobieren wäre weiterhin
> undenkbar, aber alle symmetrischen Schlüssel wäre realistisch.

Guten Abend allerseits,

als Nichtmathematiker habe ich eine Frage an mein Komplement.

Hat jemand eine Vorstellung, wieviel denn die Faktorisierung einer aus
solchen 2048 bit langen Zahlen bestehenden öffentlichen Schlüssels kosten
kann, wenn jemand den mit Gewalt zerlegen will ?

Das ist doch sicher ein wichtiger Aspekt bei der Diskussion um die
Sicherheit. Wenn das beispielsweise 2 Bitcoins kosten würde, kann sich
das ja nicht jeder Hacker leisten. Anders sieht es sicher aus, wenn es
nur 100 Euro wären.

Das Erzeugen von Bitcoins ist ja auch einmal eine einfache Methode
gewesen viel Geld zu verdienen, wenn man sich dafür interessiert hat.

Gruß
Ralf

Martin Vaeth

unread,
Nov 30, 2021, 12:12:59 PM11/30/21
to
Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
> Martin Vaeth hakt nach:
>> Klaus Pommerening <pomm...@uni-mainz.de> wrote:
>>> Im Prinzip ja. Aber bei einer vollständigen Suche hat ein
>>> Quantencomputer keinen nennenswerten Vorteil [...]
>>> hätte ein Quantencomputer nur beim Faktorisieren [...]
>>
>> Und der Algorithmus zum Faktorisieren schöpft durch die
>> Mehrdeutigkeit den gesamten Suchraum aus. Insofern kann ich
>> Deinen ersten Satz nicht nachvollziehen.
>
> Hä? Wie meinen? Vollständige Suche heißt: Ich nehme jedes Element
> einer Menge (in irgendeiner Reihenfolge) her und untersuche es auf ein
> bestimmtes Kriterium. Da sind Quantencomputer (bisher nur theoretisch)
> etwas im Vorteil, aber nicht entscheidend.
>
> Im Fall der Faktorisierung einer Zahl n wäre dieser naive Algorithmus:
> Durchlaufe alle natürlichen Zahlen m der Reihe nach und prüfe, ob m|n.

Mein Verständnis war bislang, dass Quantencomputer genau das machen,
also die Superposition aller dieser Zahlen m betrachtet wird, und dass
man im konkreten Fall nur das Problem hat, dass der zweite Teil (die Kopplung
dieser Superposition mit den Ergebnissen des Tests m|n) keine "erlaubte"
Operation für Superpositionen ist, weshalb man den Shor-Algorithmus benötigt,
der das Analoge mit "erlaubten" Operationen erreicht.
So interpretierte ich zumindest Shritt 2 des Quanten-Shor-Algorithmus
auf Wikipedia:

2. Initialisiere das erste Quantenregister (Eingaberegister)
mit der Superposition (siehe Qubit) aller Zustände {a mod q}.

Habe ich da etwas vollkommen missverstanden?

Martin Vaeth

unread,
Nov 30, 2021, 12:31:36 PM11/30/21
to
Ralf Schneider <schne...@freenet.de> schrieb::
>
> Hat jemand eine Vorstellung, wieviel denn die Faktorisierung einer aus
> solchen 2048 bit langen Zahlen bestehenden öffentlichen Schlüssels kosten
> kann, wenn jemand den mit Gewalt zerlegen will?

Hier ist ein zugehöriger 20 Jahre alter Artikel:

https://www.heise.de/newsticker/meldung/
Spezialhardware-bedroht-moeglicherweise-RSA-Sicherheit-58782.html

Es wird viel spekuliert, wieviel große Geheimdienste inzwischen bereits
praktisch schaffen.

Ralf Schneider

unread,
Nov 30, 2021, 12:56:18 PM11/30/21
to
Am Tue, 30 Nov 2021 17:31:33 -0000 (UTC) schrieb Martin Vaeth:

> Spezialhardware-bedroht-moeglicherweise-RSA-Sicherheit-58782.html

Danke, aber da steht nichts über Kosten. Da sind viele Zahlenspiele, die
mich verwirren und nicht informieren. Was ein MFLOP pro Jahr kostet, weiß
ich nicht.

Meine einfache Frage war: Wieviele Euro kostet das Faktorisieren einer
2048 bit langen Zahl ? Kann das jemand in etwas schätzen ?

Jens Kallup

unread,
Nov 30, 2021, 12:57:39 PM11/30/21
to
Am 30.11.2021 um 18:12 schrieb Martin Vaeth:
> Habe ich da etwas vollkommen missverstanden?

die einfachste Form einen Quantencomputer's besteht in der
Berechnung der Superposition, die zwischen 0 und 1 liegen kann,
wobei 0 und 1 selbst auch dazu gehören, aber nicht für Primzahl
exoerimente verwendet werden können, da diese zwei Objekte nicht
invertierbar sind - kann man vergleichen mit "nicht" Farben und
"sind" Farben: 0 - schwarz, 1 - weis (schwarz und weis sind dann
keine Farben, obwohl diese in den Farbraum von Computern (0-255
liegen).
Daher hat man von diesen 5 QuBits nur 3 über.
Dann wirde aber noch 1 QuBit für das Datenflag ansich - / + und
input / output (1 QuBit als quad Bit ansehen also 2 Bit - 4 States).
Das macht dann nach Adam Rieß, der noch kein Quantencomputer kannte
2 QuBits für Berechnungen.
Diese 2 quad QuBits können schon 8 Zustände speichern, also mehr
als das doppelte von normalen digitalen Rechnern.
Das Problem an Quantencomputern allerdings ist, das die Berechnungen
an Hand der Bauweise recht viel Energie entstehen lassen, und dadurch
auch wieder recht viel Energie aufgebracht werden muss, um diese
Zustände zu Validieren, und die Zustände selbst wieder abzukühlen.
Und weil das ganze dann eine Art Mini-Reaktor ist, kann dieser
"abkühl"-Prozeß schon mal paar Stunden Dauern.
Was dann letzendlich den Rechenvorteil gegenüber normalen Computern
eher beeinträchtigt als fördert, weil dann noch am Schluß die Daten
auf 1 Bit (2 Zustände) runtergedrosselt werden müssen, und dadurch
wieder Informationen verloren gehen.
Also am Ende eher eine spielerrei ist.

Gruß, Jens

Jens Kallup

unread,
Nov 30, 2021, 1:12:22 PM11/30/21
to
Am 30.11.2021 um 18:08 schrieb Ralf Schneider:
> Das Erzeugen von Bitcoins ist ja auch einmal eine einfache Methode
> gewesen viel Geld zu verdienen, wenn man sich dafür interessiert hat.

Glaub mir, oder lieber nicht, vertraue mir was ich hier schreibe:
Auch als Nicht-Mathematiker kann man das sicherlich verstehen:
- um Bitcoins zu minen (Benutzer von solchen Systemen werden
Miner genannt), benötigst Du Strom - sehr viel Strom, und Vor-
geld (für die Hardware + Wartungskosten) !!!

Wichtig :
- es steht keine feste Gegen-Währung hinter diesen Bitcoin-Systemen !
- Du zahlst lediglich die Stromkosten, die für sinnfreie Berechnungen
notwendig sind !
- Du musst teure Hardware kaufen - die übertaktet sehr viel mehr dazu
neigt ihren Geist aufzugeben !
- für normal OTTO - Bürger ist das sinnfrei - lediglich was für Groß-
rechenzentren ne Frage !
- ein normaler PC hat nie die Change an die Leistung eines Servers
zu gelangen, um eine Berechnung auf Richtigkeit und - oder auf
schnelligkeit zu prüfen, denn:
- wer zuerst kommt, der bekommt ein Stück von diesen Bitcoin-
Systemen !
- daher: niemals als OTTO Bürger darin investieren !!!
schon alleine wegen der Umwelt und Kohleverschmutzung:
- ich sag dazu nur Kraftwerksstrom !
- Systeme sind nicht sicher !!!
- Hacker versuchen mit anscheinenden "günstigen" Abo-Systemen oder mit
allen Mitteln den Bürger zu betrügen, indem Anfangsgebühren von nicht
unter 100,- Euronen verlangt werden - alles für die Katz !
- daher niemals auf sowas eingehen !!!

- Aus einer Quelle hab ich letzte Woche lesen können, dass das SETI
Projekt eingestampft wurde, weil es eben nur "Kosten" verursacht hat !
- aber der Staat der USA auf Gelder für die Raumfahrt angewiesen war und
ist, wurde dieses Projekt gestartet.
Eigentlich eine Steuerverschwendung.

- ABER: Jeder sollte das sich für sich selbst überlegen, ob er das Geld
auf die Bank bringt, und durch diese Kasperrade mit den Minus-
zinsen halbieren läßt, oder durch sinnfreie Stromkosten sein
Geld "verheizt" !!!

Ich mein, kann man machen - ich mach sowas prinzipiell nicht.
Also, sehe ich diese Frage dieses Artikels hier vom Original-Poster eher
als Scherzartikel, und weniger als ernstgemeint.

Berlin helau !!!

Euer Schreiberling, Jens

Ralf Schneider

unread,
Nov 30, 2021, 2:06:46 PM11/30/21
to
Natürlich investiere ich mit meiner VGA++ Karte keinen Cent in das Mining
von Bitcoins. Die Konkurrenz ist milliardenmal schneller.

Meine ganz einfach gestellte Frage wurde aber immer noch nicht
beantwortet, muss ich leider feststellen.

Gruß
Ralf

Klaus Pommerening

unread,
Nov 30, 2021, 4:13:31 PM11/30/21
to
Martin Vaeth missversteht:
> Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
>> Martin Vaeth hakt nach:
>>> Klaus Pommerening <pomm...@uni-mainz.de> wrote:
>>>> Im Prinzip ja. Aber bei einer vollständigen Suche hat ein
>>>> Quantencomputer keinen nennenswerten Vorteil [...]
>>>> hätte ein Quantencomputer nur beim Faktorisieren [...]
>>>
>>> Und der Algorithmus zum Faktorisieren schöpft durch die
>>> Mehrdeutigkeit den gesamten Suchraum aus. Insofern kann ich
>>> Deinen ersten Satz nicht nachvollziehen.
>>
>> Hä? Wie meinen? Vollständige Suche heißt: Ich nehme jedes Element
>> einer Menge (in irgendeiner Reihenfolge) her und untersuche es auf ein
>> bestimmtes Kriterium. Da sind Quantencomputer (bisher nur theoretisch)
>> etwas im Vorteil, aber nicht entscheidend.
>>
>> Im Fall der Faktorisierung einer Zahl n wäre dieser naive Algorithmus:
>> Durchlaufe alle natürlichen Zahlen m der Reihe nach und prüfe, ob m|n.
>
> Mein Verständnis war bislang, dass Quantencomputer genau das machen,

Könnten sie machen. Dann wären ihre Programmierer aber richtig doof,
weil, wie ich schon erklärt habe, Quantencomputer bei dieser Methode
keinen wirklich relevanten Vorteil haben. (Die Komplexität wäre
sqrt(log(n)) statt log(n).)

> also die Superposition aller dieser Zahlen m betrachtet wird, und dass
> man im konkreten Fall nur das Problem hat, dass der zweite Teil (die Kopplung
> dieser Superposition mit den Ergebnissen des Tests m|n) keine "erlaubte"
> Operation für Superpositionen ist, weshalb man den Shor-Algorithmus benötigt,
> der das Analoge mit "erlaubten" Operationen erreicht.
> So interpretierte ich zumindest Shritt 2 des Quanten-Shor-Algorithmus
> auf Wikipedia:

Die besten Faktorisierungsalgorithmen sind *wesentlich* effizienter
als das Durchsuchen aller potenziellen Faktoren, sogar wenn man
Letzteres auf einem Quantencomputer durchführt. Und auf diesen
Algorithmen baut der Shor-Algorithmus auf, der dann natürlich nochmal
wesentlich effizienter wäre -- auf einem fehlerfreien Quantencomputer.
--
Klaus Pommerening
Leute, geht nicht auf die Impfgegner-Demos! SIE verstecken Agenten mit
Spritzen in den Gullys, um euch von unten zwangszuimpfen!!

Jens Kallup

unread,
Nov 30, 2021, 4:25:38 PM11/30/21
to
Am 30.11.2021 um 20:06 schrieb Ralf Schneider:
> Meine ganz einfach gestellte Frage wurde aber immer noch nicht
> beantwortet, muss ich leider feststellen.

Das war auch nur ein Hinweis dafür, das Du diese Gedanken
streichen solltest !

Ansonsten hängt man Heute an einer Art "Grenze" fest, die
Neue Primzahlen recht schwer auffindbar macht.

Näheres dazu kannst Du auf YouTube bei dem Edmund finden.

Gruß, Jens

Martin Vaeth

unread,
Nov 30, 2021, 11:19:54 PM11/30/21
to
Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
> Martin Vaeth missversteht:
>>> Im Fall der Faktorisierung einer Zahl n wäre dieser naive Algorithmus:
>>> Durchlaufe alle natürlichen Zahlen m der Reihe nach und prüfe, ob m|n.
>>
>> Mein Verständnis war bislang, dass Quantencomputer genau das machen,
>
> Könnten sie machen. Dann wären ihre Programmierer aber richtig doof,
> weil, wie ich schon erklärt habe, Quantencomputer bei dieser Methode
> keinen wirklich relevanten Vorteil haben.

Warum? Wenn man die Kopplung von m mit dem Ergebnis m|n auf die
Überlagerung aller m anwendet (und dies eine zulässige Operation wäre),
wäre das exakt die Laufzeit *eines* Teilbarkeitstests (weil sie
ja alle als "Überlagerung" parallel ablaufen), also log(n).

Dies ist m.E. die entscheidende Optimierung: Von i.W. exponentieller
(in der Anzahl der Bits, s. unten) Laufzeit bei einem klassischen
Rechner (für den naiven Algorithmus) auf lineare Laufzeit bei einem
Quantenrechner (wieder für den naiven Algorithmus).

> (Die Komplexität wäre sqrt(log(n)) statt log(n).)

???

Für einen Nicht-Quantencomputer komme ich auf die Laufzeit log(n)
(Teilbarkeitstest) *multipliziert mit n* (naja, sqrt(n) nach
der trivialen Beobachtung, dass man nur m < sqrt(n) betrachten muss):
Anders als ein Quantencomputer hat man bei klassischen Rechnern hier
eben das Parallelisierbarkeitsproblem: Mit sqrt(n) parallel laufenden
Rechnern kann man freilich problemlos die Laufzeit log(n) erreichen...

> Die besten Faktorisierungsalgorithmen sind *wesentlich* effizienter
> als das Durchsuchen aller potenziellen Faktoren

Natürlich (für klassische Rechner). Aber der Quantenrechner macht das
Durchsuchen ja *parallel* für alle potentiellen Faktoren (falls die
Operation für die Überlagerung zulässig sein sollte), weshalb bei einem
Quantenrechner eine weitere Optimierung gar nicht mehr nötig erscheint.

Jens Kallup

unread,
Dec 1, 2021, 1:15:23 AM12/1/21
to
Am 01.12.2021 um 06:27 schrieb Gerhard Strangar:
> dürfte wesentlich günstiger sein, ein paar "Bugs" im Code
> einzuschleusen, die den Rechenaufwand reduzieren.

sag ich doch: Back-Door !!!

Klaus Pommerening

unread,
Dec 1, 2021, 3:51:33 AM12/1/21
to
Martin Vaeth beharrt:
> Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
>> Martin Vaeth missversteht:
>>>> Im Fall der Faktorisierung einer Zahl n wäre dieser naive Algorithmus:
>>>> Durchlaufe alle natürlichen Zahlen m der Reihe nach und prüfe, ob m|n.
>>> Mein Verständnis war bislang, dass Quantencomputer genau das machen,
>> Könnten sie machen. Dann wären ihre Programmierer aber richtig doof,
>> weil, wie ich schon erklärt habe, Quantencomputer bei dieser Methode
>> keinen wirklich relevanten Vorteil haben.
> Warum? Wenn man die Kopplung von m mit dem Ergebnis m|n auf die
> Überlagerung aller m anwendet (und dies eine zulässige Operation wäre),
> wäre das exakt die Laufzeit *eines* Teilbarkeitstests (weil sie
> ja alle als "Überlagerung" parallel ablaufen), also log(n).

Das wäre richtig, wenn Quantencomputer unbegrenzt parallel rechnen
könnten. Können sie aber nicht, es ist komplizierter. Hab jetzt
keine Zeit, Genaueres zu recherchieren, nur so viel als Hinweis:
Wären Quantencomputer dazu in der Lage, könnten sie auch einen
"Brute-Force"-Angriff auf die Schlüssel eines beliebigen
kryptographischen Verfahrens mit parallelem Durchprobieren
aller 2^k Schlüssel der Bitlänge k durchführen. Alle derzeitigen
Bemühungen um Post-Quanten-Kryptographie wären sinnlos.
--
Klaus Pommerening
Es bereitet deshalb solches Vergnügen, anderer Leute Geheimnisse
herauszufinden, weil dadurch die Aufmerksamkeit der Öffentlichkeit
von den eigenen abgelenkt wird. (Oscar Wilde)

Ralf Schneider

unread,
Dec 1, 2021, 3:17:02 PM12/1/21
to
Am Wed, 1 Dec 2021 06:27:04 +0100 schrieb Gerhard Strangar:

> 2000 Kern-Jahre auf 2,2 GHz, mit heuter Hardware und Großabnehmerpreis
> ca. 5000 Euro nur an Stromkosten - ohne Klimatisierung. Obiges Dokument
> erwähnt, mit 1024 Bit sei es um Faktor 1000 aufwendiger als mit 768. Es
> dürfte wesentlich günstiger sein, ein paar "Bugs" im Code
> einzuschleusen, die den Rechenaufwand reduzieren.

Das ist ja endlich eine Zahl. Vielen Dank ! Das stimmt mich froh. Also
dürfte es mit 4096 millionenfach teurer sind.

Gruß
Ralf

Martin Vaeth

unread,
Dec 2, 2021, 1:55:50 PM12/2/21
to
Klaus Pommerening <pomm...@uni-mainz.de> schrieb:
> Martin Vaeth beharrt:
>> Warum? Wenn man die Kopplung von m mit dem Ergebnis m|n auf die
>> Überlagerung aller m anwendet (und dies eine zulässige Operation wäre),
>> wäre das exakt die Laufzeit *eines* Teilbarkeitstests (weil sie
>> ja alle als "Überlagerung" parallel ablaufen), also log(n).
>
> Das wäre richtig, wenn Quantencomputer unbegrenzt parallel rechnen
> könnten. Können sie aber nicht, es ist komplizierter.

Das meinte ich damit, dass es eben keine "zulässige Operation" ist.
Verstehen tue ich es nicht - vermutlich fehlt mir ein vernünftiger
einführender Text dazu: Der Shor-Algorithmus benutzt Operationen,
von denen ich noch viel weniger erwartet hätte, dass sie "zulässig"
sind (FFT etwa scheint mir doch wesentlich komplexer als eine
modulo-Operation zu sein, die man für einen Teilbarkeits-Test
bräuchte).

> Wären Quantencomputer dazu in der Lage, könnten sie auch einen
> "Brute-Force"-Angriff auf die Schlüssel eines beliebigen
> kryptographischen Verfahrens mit parallelem Durchprobieren
> aller 2^k Schlüssel der Bitlänge k durchführen.

Jein: Nach meinem Verständnis sind Quantencomputer "nahezu" in der
Lage, NP-vollständige Problem in polynomialer Zeit durchzuführen.
(Nur nhezu, weil die polynomiale Testoperation "zulässig" sein muss.)

> Alle derzeitigen Bemühungen um Post-Quanten-Kryptographie wären
> sinnlos.

Nicht, wenn der Angriffs-Algorithmus zwangsläufig außerhalb der
Klasse NP liegt. Bestimmte Anwendungen der Kryptographie sind
daher aber m.W. in der Post-Quanten-Kryptographie prinzipiell
nicht mehr möglich.

Marcus Gloeder

unread,
Dec 8, 2021, 12:55:42 AM12/8/21
to
Am 30.11.21 22:13, schrieb Klaus Pommerening:
>Leute, geht nicht auf die Impfgegner-Demos! SIE verstecken Agenten mit Spritzen in den Gullys, um euch von unten zwangszuimpfen!!

:-D LOL!

Cool! Darf ich das bei Facebook posten?

--
PMs an: m.gl...@gmx.de

Jens Kallup

unread,
Dec 8, 2021, 1:12:28 AM12/8/21
to
Am 08.12.2021 um 06:55 schrieb Marcus Gloeder:
> Cool! Darf ich das bei Facebook posten?

am besten wenden Sie sich an die örtliche Polizeibehörde.
Plagiaten Sie Ihren Arzt und Apotheker.
Benachrichten Sie N24.
Drucken Sie Flyer für 4 Millionen Euro, die von der AfD
gesponsert werden.
Tätowieren Sie Ihr Playboy-Model mit der Aufschrift:
"Aufschwung Ost" - am besten mit großen Lettern.

Du kennst doch sicherlich die 10 großen A's des Büroalltages?
1. Alle
2. Anfallende
3. Arbeiten
4. Auf
5. Andere
6. Abschieben
7. Anschließend
8. Anscheißen
9. Aber
10. Anständig !

hihi, Spaß.
kölle helaf...

Jens

Juergen Ilse

unread,
Dec 11, 2021, 8:52:32 AM12/11/21
to
Hallo,

Marcus Gloeder <m.gl...@gmx.de> wrote:
> Am 30.11.21 22:13, schrieb Klaus Pommerening:
>>Leute, geht nicht auf die Impfgegner-Demos! SIE verstecken Agenten mit Spritzen in den Gullys, um euch von unten zwangszuimpfen!!
>
> :-D LOL!
>
> Cool! Darf ich das bei Facebook posten?

Das ist ja noch schlimmer als in der Heute-Show behauptet (laut der Sendung
hat die Regierung Dart-Profis engagiert, die unschuldige Passanten mittels
passend geworfener Spritzen impfen ...).

Tschuess,
Juergen Ilse (jue...@usenet-verwaltung.de)

Marcus Gloeder

unread,
Dec 14, 2021, 10:39:57 PM12/14/21
to
Am 11.12.21 14:52, schrieb Juergen Ilse:
>Das ist ja noch schlimmer als in der Heute-Show behauptet (laut der Sendung
>hat die Regierung Dart-Profis engagiert, die unschuldige Passanten mittels
>passend geworfener Spritzen impfen ...).

Huahahahaha! LOL! ROFL!
Hör auf! Ich kann nicht mehr vor Lachen!

>Tschuess,
> Juergen Ilse

Viele Grüße
Marcus

--
PMs an: m.gl...@gmx.de

Juergen Ilse

unread,
Dec 15, 2021, 8:07:04 PM12/15/21
to
Hallo,

Marcus Gloeder <m.gl...@gmx.de> wrote:
> Am 11.12.21 14:52, schrieb Juergen Ilse:
>>Das ist ja noch schlimmer als in der Heute-Show behauptet (laut der Sendung
>>hat die Regierung Dart-Profis engagiert, die unschuldige Passanten mittels
>>passend geworfener Spritzen impfen ...).
>
> Huahahahaha! LOL! ROFL!
> Hör auf! Ich kann nicht mehr vor Lachen!

OK, in dem Beitraag der Heute-Show beschraenkte sich diese Behandlung
auf die wartenden in der Schlange vor dem Impfzentrum und sollte der
schnelleren Abfertigung von wuetenden wartenden dienen ...

https://www.zdf.de/comedy/heute-show/
(ab etwa 18:35)

Tschuess,
Juergen Ilse (jue...@usenet-verwaltung.de)

Marcus Gloeder

unread,
Dec 15, 2021, 11:25:34 PM12/15/21
to
Hallo alle zusammen, Hallo Jürgen,

am 16.12.21 02:07, schrieb Juergen Ilse:
>Hallo,
>
>[…]
Vielen Dank für den Link. Ich habe mir die ganze Sendung angeschaut. Echt
cool!
Reply all
Reply to author
Forward
0 new messages