Primzahlzwillingsrekorde – nicht nur eine Jagd nach Monstern

Karl-Heinz IndlekoferStefan Wehmeier

Arbeitsgruppe ZahlentheorieUniversität Padeborn

Die Mathematik ist die Königin der Wissenschaften, und die Zahlentheorie ist die Königin der Mathematik.

C.F. Gauß (1777-1855)

Fraktale

Weltrekord aus Paderborn

Definition Primzahl

• Eine Primzahl ist eine natürliche Zahl p größer als 1, die durch keine andere Zahl als durch 1 und sich selbst geteilt wird.

Das Sieb des Eratosthenes

1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Das Sieb des Eratosthenes

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

1 wird gestrichen2 erste Primzahl

also alle Vielfachen von 2 keine Primzahlen

Das Sieb des Eratosthenes

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Nächste Primzahl: 3alle Vielfachen von 3 keine Primzahlen

Das Sieb des Eratosthenes

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Nächste Primzahl: 5streiche alle Vielfachen von 5

Das Sieb des Eratosthenes

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Nächste Primzahl: 7streiche alle Vielfachen von 7

Das Sieb des Eratosthenes

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Die verbleibenden Zahlen sind nun alle Primzahlen zwischen 0 und 50

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

26 27 28 29 30

31 32 33 34 35

36 37 38 39 40

41 42 43 44 45

46 47 48 49 50

51 52 53 54 55

56 57 58 59 60

61 62 63 64 65

66 67 68 69 70

71 72 73 74 75

76 77 78 79 80

81 82 83 84 85

86 87 88 89 90

1301 1302 1303 1304 1305

1306 1307 1308 1309 1310

1311 1312 1313 1314 1315

1316 1317 1318 1319 1320

1321 1322 1323 1324 1325

1326 1327 1328 1329 1330

1331 1332 1333 1334 1335

1336 1337 1338 1339 1340

1341 1342 1343 1344 1345

1346 1347 1348 1349 1350

1351 1352 1353 1354 1355

1356 1357 1358 1359 1360

1361 1362 1363 1364 1365

1366 1367 1368 1369 1370

1371 1372 1373 1374 1375

1376 1377 1378 1379 1380

1381 1382 1383 1384 1385

1386 1387 1388 1389 1390

1391 1392 1393 1394 1395

1396 1397 1398 1399 1400

1401 1402 1403 1404 1405

1406 1407 1408 1409 1410

1411 1412 1413 1414 1415

1416 1417 1418 1419 1420

Euklid von Alexandria

• Gelebt von ca. 330 bis ca. 275 v. Chr.

• „Die Elemente“ ein 13-bändiges Kompendium des damaligen Mathematik-Wissens

Es gibt unendlich viele Primzahlen.

Annahme: Es gibt nur endlich viel Primzahlen p1, ..., pn.Betrachte nun n := p1 * ... * pn +1.n ist nicht durch p1, ..., pn teilbar. Also muss n selbst Primzahlsein oder aus Primzahlen zusammen gesetzt sein, die von p1, ..., pn verschieden sind. Widerspruch!

2 kleine Beispiele: 2*3+1=7 2*3*5*7*11*13+1=30031=59*509

Es gibt also unendlich viele Primzahlen.

Mit welcher Wahrscheinlichkeit ist eine erzeugte Zahl prim?

• Zahlen von 90000 – 92000• Anzahl: 2000• Davon Primzahlen: 174

• Vermutung von Gauß: eine Zufallszahl ist

mit Wahrscheinlichkeit eine Primzahl

n

)ln(1

n

)91000ln(1087,02000

174hlZahlenanza

Primzahlen

Carl Friedrich Gauß• * 30. April 1777 in Braunschweig• 23. Februar 1855 in Göttingen• Schon als Kind begeistert von der

Mathematik• Der Herzog von Braunschweig

ermöglichte ihm das Studium am Collegium Carolinum in Braunschweig

• Einige Erfolge:– Methode der kleinsten Quadrate– Das Gesetz der normalen

Fehlerverteilung– Fundamentalsatz der Algebra

Primzahlen in Intervallen

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10^8, 10^8+c 10^ 10, 10^ 10+c 10^ 12, 10^ 12+c 10^ 14, 10^14+c

e r wa r te t e Anz a hl

ge f unde ne Anz a h l

Der exakte Beweis

• ... paßt leider nicht auf diese Folie• Er wurde im Jahr 1896 von Hadamard und

de la Valée-Poussin erbracht• Der Beweis macht einen „Umweg“, indem

er die Theorie der Funktionen über den komplexen Zahlen verwendet

• Inzwischen kennt man noch weitere Beweise

Jacques Salomon Hadamard Charles Jean Gustave de la Vallée Poussin* 8. Dez. 1865, Versailles (Frankreich) * 14. Aug. 1866, Louvain (Belgien) 17. Okt. 1963, Paris (Frankreich) 2. März 1962, Louvain (Belgien)

Was sind Primzahlzwillinge?

2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 50

Godfrey Harold Hardy John Edensor Littlewood* 7. Feb. 1877 Cranleigh (England) * 9. Juni 1885 Rochester (England) 1. Dez. 1947 Cambridge (England) 6. Sep. 1977 Cambridge (England)

Die Wahrscheinlichkeit ein Primzahlzwillingspaar zu finden

Die Wahrscheinlichkeit, dass eine Zahl p Primzahl ist, ist .

Die Wahrscheinlichkeit, dass p+2 Primzahl ist, ist .

Hardy-Littlewood:Die Wahrscheinlichkeit, dass sowohl p als auch p+2

Primzahlen sind, ist ungefähr .

)ln(1

p

)ln(1

p

2

)ln(1

p

Primzahlzwillinge in Intervallen

0

100

200

300

400

500

600

700

10^8, 10^8+ c 10 ^10,10^1 0+c 10^12, 10^12+ c 10^ 14,10^1 4+c

e rw ar te te Anz ahlg efund ene A nza h l

Die Forschung

• Ob es unendlich viele Primzahlzwillinge gibt, ist ein offenes Problem!

• Ziel: Das Finden von möglichst großen Primzahlzwillingen

Primzahltests• Probedivision: eine Zahl n ist genau dann Primzahl, wenn

sie keinen Teiler zwischen 1 und hat. Man kann also versuchen, n durch alle kleineren Zahlen zu dividieren.

• Rechnet man (großzügig) 1 Milliarde Divisionen pro Sekunde, so schafft man pro Jahr etwa 3*10^16 Divisionen, seit Entstehung der Welt also etwa 5*10^26 Divisionen. Man hätte in dieser Zeit also eine 53-stellige Zahl testen können. In der Mathematik der Gegenwart untersucht man jedoch zum Teil Zahlen mit mehreren Millionen Stellen!

• Gibt es schnellere Verfahren?

n

Pierre de Fermat* 17. August 1601 Beaumont-de-Lomagne (Frankreich)

12. Januar 1665 Castres (Frankreich)

Berühmt vor allem durch seinen „letzten Satz“: Sind und

, so gilt3n cba nnn

INcba ,,

Der Test von Fermat

• Satz von Fermat: Wenn p eine Primzahl ist, so gilt für jede Zahl a, , dass

den Rest 1 lässt.

• Aber: es gibt auch Zahlen, die keine Primzahlen sind und für die diese Aussage für sehr viele a gilt

11 papa p :1

Beispiel p=5 (Primzahl)

a=1

a=2

a=3

a=4

51

514

5135

165

24

51165

815

34

51515

2565

44

Beispiel p=6 (keine Primzahl)

a=1

a=2 f

a=3 f

a=4 f

a=5 f

61

615

6256

326

25

63406

2436

35

641706

10246

45

655206

31256

55

• Gary L. Miller • Michael O. Rabin

Der Miller-Rabin-Test

Satz von Miller-Rabin: Wenn p eine ungerade Primzahl ist, so lässt

den Rest 1 oder p-1. Wenn p keine Primzahl ist, so lässt

für mindestens ¾ aller a einen anderen Rest.

pap

:21

pap

:21

Problem

Unsere p haben etwa 20.000 Dezimalstellen,

um auszurechnen braucht man sehr

viele Multiplikationen großer Zahlen.

ap2

1

Multiplizieren in der Schule

13456923 * 67890125 67890125 203670375 271560500 339450625 407340750 611011125 135780250 203670375 913592184585375

Verdoppelt man die Zahl der Stellen, so vervierfacht sich der Aufwand!

Das Karazuba-Verfahren

1)Schreibe 2 gegebene 2n-stellige

Zahlen als a * 10^n + b bzw. c * 10^n + d

2)Dann gilt:(a * 10^n + b)(c * 10^n + d) =(ac)*10^2n + (ad + bc)*10^n + bd

3)Weiter gilt:(a + b)(c + d) = ac + (ad + bc) + bd

4)Man kann also die Multiplikation von zwei 2n-stelligen Zahlen auf drei Multiplikationen von n-stelligen Zahlen (ac, (a+b)(c+d), bd) sowie einigen Additionen zurückführen.

1) 13456923 = 1345 * 10^4 + 6923 67890125 = 6789 * 10^4 + 125

n = 4, a = 1345, b = 6923, c = 6789, d = 125

3) 1345 + 6923 = 8268 6789 + 125 = 6914 8268 * 6914 = 57164952

1345 * 6789 = 9131205 6923 * 125 = 865375

(a*d+b*c) = 57164952 – 865375 9131205 = 47168372

2)+ 865375 = 913592184585375

10*4716837210*9131205 48

Anatolii Alekseevich Karazuba

• Geboren 31.1.1937 in Grozny

• 1954-1959 Studium in Moskau

• 1962: Entdeckung seines berühmten Algorithmus

• Seit 1983 Dekan des Bereichs Zahlentheorie am Stekhlov-Institut

Es geht noch schneller...

Rekord Primzahlzwillinge

Atkin, RichertDubner Parady, Smith,

Zarantonello

Dubner

Dubner Dubner

Indlekofer, Járai

Indlekofer, Járai Ballinger,

Gallot

Indlekofer, Járai, Wassing

Indlekofer, Járai, Wassing

Lifchitz

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000