Diskrete algebraische Methoden

i

i

“main” — 2013/4/10 — 15:19 — page 116 — #128

i

i

i

i

i

i

116 Zahlentheoretische Algorithmen

Aufgaben

3.1. (Master-Theorem II) Sei



k

i=0

α

i

< 1.ZeigenSie:Aus

f(n) ≤

k



i=0

f

(

α

i

n

)

+O(n)

folgt f(n) ∈O(n).

3.2. Zeigen Sie, dass auf Eingabe zweier Binärzahlen

a, b ∈ N in polynomieller Zeit

entscheidbar ist, ob ein

c ∈ Q mit c

2

= a/b existiert.

3.3. Zeigen Sie, dass

1729 eine Euler’sche Pseudoprimzahl zur Basis 2, jedoch kei-

ne starke Pseudoprimzahl zur Basis

2 ist. Finden Sie des Weiteren mit Hilfe von Be-

merkung 3. 5 einen nichttrivialen Teiler von

1729.

3.4. (Lucas-Test; nach Édouard Lucas, 1842–1891) Sei

n ≥ 1 und a ∈ Z.ZeigenSie,

dass

n eine Primzahl ist, wenn die folg ...