NOTES TO lecture on prime numbers
title: Prime numbers - What's the use of prime numbers?
lecturer: Rudolf Taschner
date: 08.06.04 bzw. 09.03.28
author: Lukas Prokop
introduction: Very interesting lecture on the mathematical background of prime numbers
via: http://mathcast.org/

[ britischer Geheimdienst, Circles
Verschlüsselung
Bibel-Code (Aleph-Tav, Bet-Shin, ...)
Cäsar-Code
Dekodierung rentabel?
007 = Smiley
Circles: 143, 23, 47
Circles -> 007: 143,23
007: 007^23 = 42^2 = 7^16 * 7^4 * 7^2 * 7^1 = 48 * 113 * 49 * 7 = 1860432 mod 143 = 2
[ "Wie sie sehen, es befindet sich hinten eine Kamera und in diese Kamera, in die ich nicht blicken darf - weil das macht nur der Bundespräsident bei der Neujahrsansprache - ... diese Kamera... nein... diese Kamera nimmt den Vortrag auf"
007 -> Circles: 2
Circles: 2^47 = 2^32 * 2^8 * 2^4 * 2^2 * 2^1 = 48 * 113 * 16 * 4 * 2 = 694272 mod 143 = 7


Tabelle:
      | 1  2  3  4  5  6  7  8  9 ...
______________________________________
 1^n  | 1  1  1  1  1  1  1  1  1 ...
 2^n  | 2  4  8 16 32 64 128 ...
 3^n  | 3  9 ...
 ....

von Fermat entdeckt

Gesetzesmäßigkeit:
	zB 2. Spalte: 1 4 9 mod (Index nächster Spalte) ist 1
		1 (1^2) mod 3 = 1
		4 (2^2) mod 3 = 1
		8 (3^2) mod 3 = 1
		16 (4^2) mod 3 = 1
	andere Spalte betrachten:
		1 (1^4) mod 5 = 1
		16 (2^4) mod 5 = 1
		81 (3^4) mod 5 = 1
	nächste Spalte (bei der gültig): 7
	nächste Spalte (bei der gültig): 11
	... => Primzahlen

	Fazit:
		a^(p-1) = 1 mod p (wenn p ... Primzahl)
		zB p = 11; a^10 = 1 mod 11; zB a = 5; 5^10 (=9765625) = 1 mod 11
	Verschlüsselung:
		p * q = Produkt zweier Primzahlen (zB 11*13=143)
		a^(p-1)(q-1) = a^(10*12) = a^120 = 1 mod 143
		M^23 mod 143 = c mod 143
		Wieso zur Dekodierung 47?
			23 * 47 = 1081 = 9*120 + 1
			c^47 = (a^23)^47 = (a^120)^9*a = 1*a

			47 -> aus 120
			Methode von Euklid (vor 2300 Jahren)
				120 / 23 = 5 + 5:23
				23/5 = 4 + 3/5
				5/3 = 1 + 2/3
				3/2 = 1 + 1/2
				2/1 = 2 (kein Rest)
				-> Kettendivision
				Teilquotienten: 5, 4, 1, 1, 2

			   |   5         4         1          1           2
			___________________________________________________
			 1 |   5  5*4+1=21 21*1+5=26 26*1+21=47 47*2+26=120
			Formel: last_num * column + prelast_num
			=> 47
			"Ich mache jetzt keine Mathematik mit ihnen. Ich mache nur Kochrezepte"
		Aber wieso 120?
			120 -> aus 143 (schwer)
			143 = 11 * 13
			120 = 10 * 12
		Aber wie kommt man auf Primzahlen > 143?
			n = Zahl (variabel, 200/300-stellig)
			e = Zahl (variabel)
			[ Griechen: alpha (keine Variable) = 1 (=> Griechen konnten nicht mit Variablen rechnen)
			[ Griechen: beta = 2; pi = 80
			n = p * q
			m = (p-1)(q-1)
			e: a^e = c mod n
			d: e * d = 1 mod m
			d: c^d = a mod n
		Problematik also:
			Produkte von zwei Zahlen mit Computern berechnen => leicht
			Primfaktorzerlegung von zwei Zahlen mit Computern => sehr schwer

"Das Geschäft der Geheimdienste ist ein schmutziges und trauriges und melancholisches Geschäft. Aber das Geschäft der Mathematik - das dahinter steht - ist noch immer ein schönes Geschäft"
1970er -> Rivest, Shamir, Adleman -> RSA

Analoges Beispiel:
	Zucker und Sand leicht vermischbar
	Trennen sehr schwer

Fermat: 4 294 967 297 ist Produkt? ja, 641 * 6700417 (100 Jahre später von Euler entdeckt)