Riemann - Vermutung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:40 Mi 22.10.2008 | | Autor: | Irmchen |
Guten Abend !
Ich habe in meiner Vorlesung nachdem der Begriff des Restsymbols modulo m eingeführt wurde die foldende Definition vorliegen, von der ich mir leider nichts drunter vorstellen kann. Ich finde diese Menge auch in keiner mir bekannten Literatur. Ich hoffe, das mir jemand dabei helfen kann, mir zu erklären, welche Bedeutung diese Menge spielt und ob sie vielleicht unter einem besonderen Namen bekannt ist.
Definition :
[mm] ni (p) := \min \{ x \in \{1, .... , p-1 \} \ | \ ( \bruch{x}{p} ) = -1 \} [/mm]
Wenn ich das richtig sehe, dann handelt es sich dabei um das kleinste x aus der Menge [/mm] [mm] \{ 1, ... , p -1 \} [/mm] [/mm] , welches es quadratisches Nichtrest modulo p ist ?
Dann steht noch unter der Definition die Bemerkung:
Wenn die Riemann - Vermutung gilt, dann folgt
[mm] ni (p ) \le 2 \cdot \log (p ) [/mm]
Was ist denn die Riemann -Vermutung hier?
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:30 Do 23.10.2008 | | Autor: | felixf |
Hallo
> Ich habe in meiner Vorlesung nachdem der Begriff des
> Restsymbols modulo m eingeführt wurde die foldende
> Definition vorliegen, von der ich mir leider nichts drunter
> vorstellen kann. Ich finde diese Menge auch in keiner mir
> bekannten Literatur. Ich hoffe, das mir jemand dabei helfen
> kann, mir zu erklären, welche Bedeutung diese Menge spielt
> und ob sie vielleicht unter einem besonderen Namen bekannt
> ist.
>
> Definition :
>
> [mm]ni (p) := \min \{ x \in \{1, .... , p-1 \} \ | \ ( \bruch{x}{p} ) = -1 \}[/mm]
>
> Wenn ich das richtig sehe, dann handelt es sich dabei um
> das kleinste x aus der Menge[/mm] [mm]\{ 1, ... , p -1 \}[/mm][/mm] , welches
> es quadratisches Nichtrest modulo p ist ?
Genau.
> Dann steht noch unter der Definition die Bemerkung:
>
> Wenn die Riemann - Vermutung gilt, dann folgt
> [mm]ni (p ) \le 2 \cdot \log (p )[/mm]
>
> Was ist denn die Riemann -Vermutung hier?
Das ist die ganz normale ![[]](/images/popup.gif) Riemannsche Vermutung, wozu es sehr viel Material im Netz gibt. Einfach mal den Link anklicken oder google befragen oder...
Die Riemannsche Vermutung sagt also u.a. auch aus, dass der kleinste quadratische Nichtrest eher klein ist. Das hat folgende wichtige Konsequenz:
um Quadratwurzeln modulo p zu bestimmen, gibt es einen probabilistischen Algorithmus. Dieser benoetigt erstmal einen quadratischen Nichtrest -- man hofft, diesen erraten zu koennen. Deswegen ist der Algorithmus nichtdeterministisch, und deswegen kann er lange brauchen.
Wenn man jetzt aber weiss, dass der kleinste quadratische Nichtrest [mm] $\le [/mm] 2 [mm] \log(p)$ [/mm] ist, kann man einfach alle Zahlen bis $2 [mm] \log(p)$ [/mm] durchprobieren, und man hat also in spaetestens $2 [mm] \log(p)$ [/mm] Schritten einen quadratischen Nichtrest gefunden.
Wenn man eine solche Abschaetzung nicht hat, weiss man nur dass die Haelfte aller Zahlen zwischen $1$ und $p - 1$ quadratische Nichtreste sind, es kann also sein dass man erst nach [mm] $\approx [/mm] p/2$ Versuchen einen findet.
Da [mm] $\log(p)$ [/mm] aber viel, viel kleiner wie $p/2$ ist (naemlich polynomiell in der Eingabegroesse, also [mm] $\log(p)$, [/mm] und nicht exponentiell, da $p/2 = 1/2 * [mm] \exp(\log(p))$), [/mm] ist das natuerlich toll :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:50 Do 23.10.2008 | | Autor: | Irmchen |
Guten Abend!
Vielen Dank für die Antwort!
Viele Grüße
Irmchen
|
|
|
|
