Komplexitätsbestimmung

16.11.2023, 10:34	Malcang	Auf diesen Beitrag antworten »
Komplexitätsbestimmung Hallo mal wieder ich möchte die Komplexität eines Algortihmus' bestimmen und tue mir dabei nach wie vor sehr schwer. Ich möchte euch aber zeigen was ich habe. Der gesamte Algorithmus ist noch nicht getext, daher schreibe ich ihn einfach so: Eingabe: natürliche Zahl $\begin{eqnarray} k \end{eqnarray}$ , ungerade Zahl $\begin{eqnarray} h<2^k \end{eqnarray}$ Ausgabe: True genau dann, wenn $\begin{eqnarray} h\cdot 2^k+1 \end{eqnarray}$ prim ist. Sonst False 1)Berechne für alle Primzahlen $\begin{eqnarray} p<n \end{eqnarray}$ das Jacobisymbol $\begin{eqnarray} \Big( \frac{p}{n}\Big) \end{eqnarray}$ . 2) Falls eines dieser Jacobisymbole $\begin{eqnarray} 0 \end{eqnarray}$ ergibt, beende mit False. 3) Falls eines $\begin{eqnarray} -1 \end{eqnarray}$ ergibt, berechne die Kongruenz $\begin{eqnarray} \Big( \frac{p}{n}\Big) \pmod n \end{eqnarray}$ für diese Primzahl $\begin{eqnarray} p \end{eqnarray}$ 4) Ergibt diese Kongruenz $\begin{eqnarray} -1 \end{eqnarray}$ , beende mit True. Sonst False So, nun versuche ich die Komplexität zu bestimmen. Zuerstmal muss ich die Primzahlen sieben. Soweit ich bei Wikipedia gelesen habe, schafft der beste Algorithmus dies in $\begin{eqnarray} \mathcal{O}\Big(\frac{n}{\log\log n}\Big) \end{eqnarray}$ . Diesen habe ich allerdings nicht implementiert. Bisher arbeite ich mit einer (sicher sehr langsamen) Version des Siebes von Eratostenes. Für das Jacobisymbol habe ich einen Algorithmus, diesen würde ich euch gerne getext zeigen und natürlich erklären da ich nicht verlange, dass ihr euch da durch wühlt . [attach]57356[/attach] Die Zeilen 2 bis 13 fangen nur pathologische Fälle ab, nämlich: Nenner gerade, Nenner ist 1, Zähler ist Null, Zähler ist Eins. In Zeilen 14 bis 19 frage ich den Fall ab, dass der Zähler 2 ist. In Zeile 21 rufe ich den Algorithmus erneut auf mit $\begin{eqnarray} \Big( \frac{(p\mod n)}{n}\Big) \end{eqnarray}$ , falls der Zähler kleiner Null ist oder größer als der Nenner. In Zeilen 24 bis 31 frage ich den Fall ab, dass der Zähler gerade ist und ziehe entsprechend oft den Faktor 2 als Jacobisymbol raus. Und schließlich, Zeile 32, nutze ich das quadratische Reziprozitätsgesetz. Gerade hierbei fällt mir die Bestimmung der Komplexität sehr schwer. Soweit mein Prof sagte, ist das vergleichbar mit dem Euklidischen Algorithmus zur ggT-Bestimmung. Da liege ich dann bei $\begin{eqnarray} \mathcal{O}(n) \end{eqnarray}$ ? Und die Bestimmung der Kongruenz hat mir HAL freundlicherweise schon mit $\begin{eqnarray} n^2\log n \end{eqnarray}$ beantwortet, danke nochmal dafür! Wie bringe ich das nun in Zusammenhang? Ich muss doch die "schlimmste" Komplextität bestimmen, richtig?

1

Verwandte Themen