Titlebook: Algorithmische Zahlentheorie; Otto Forster Textbook 19961st edition Springer Fachmedien Wiesbaden 1996 Fibonacci-Zahlen.Fourier-Transforma

lavish

Die Grundrechnungs-Arten,st dabei der Potenzierungs-Algorithmus. Um eine Zahl in die .-te Potenz zu erheben, sind nicht, wie beim naiven Verfahren, . −1 Multiplikationen nötig, sondern höchstens 2., wobei . die Anzahl der Binär-Stellen von . ist.

使害羞

Die Fibonacci-Zahlen, Fibonacci-Zahlen erstellen. Die Fibonacci-Zahlen spielen in verschiedenen Gebieten innerhalb und außerhalb der Mathematik eine Rolle. Wir werden die Fibonacci-Zahlen bei der Untersuchung des euklidischen Algorithmus im nächsten Paragraphen benötigen.

Proponent

medium

压倒

,Die Sätze von Fermat, Euler und Wilson,t durch . teilbare ganze Zahl . gilt .. ≡ 1 mod .. Da sich mit Hilfe des Potenzierungs-Algorithmus auch hohe Potenzen schnell berechnen lassen, kann man diese Aussage dazu benützen, um von einigen Zahlen zu beweisen, dass sie keine Primzahlen sind.

Jogging

Die Struktur von (Z/,Z)*, Primitivwurzeln,es, dass es ein Element ξ gibt, dessen Potenzen ξ. sämtliche Elemente von (ℤ/.ℤ)* durchlaufen. Ein solches Element heißt Primitivwurzel. Es wird sich herausstellen, dass im Falle, dass . eine Primzahl oder Potenz einer ungeraden Primzahl ist, stets Primitivwurzeln in (ℤ/.ℤ)* existieren.