Zahlen über chinesischen Restsatz
Verfasst: Mi Sep 16, 2009 12:56 pm
Tag
So, hier nun eine Vorstellung meiner Arbeit, die ich im Urlaub für meine Facharbeit geschrieben habe.
Es handelt sich um eine Klasse, mit der sich (in der Theorie) beliebig große Zahlen darstellen lassen.
Die Klasse basiert auf dem Prinzip des chinesischen Restsatzes. Laut dem hat ein System von Kongruenzen genau eine Lösung x im Zahlenraum Zm wenn gilt:
x = a1 (mod m1)
...
x = an (mod mn)
m = m1 * ... * mn
Vorraussetzung dafür ist, dass die sogenannten Module m1, ..., mn teilerfremd sind (ich benutze hierfür Primzahlen)
Die Zahl x befindet sich damit im Raum zwischen 0 und m-1
Darstellen kann man die Zahl nun durch ihre Reste a1, an
Mit diesen Resten kann man dann auch rechnen:
xa + xb = xc
=> a1 + b1 = c1 (mod m1)
Soweit komme ich mit beliebig großen Zahlen im Moment auf eine ganz annehmbare Geschwindigkeit....nämlich ca 50-60 Prozent der Geschwindigkeit bei Integer-Rechnungen.
Problem ist im Moment, dass ich die Zahlen nicht in ihrer Größe vergleichen kann. Aus diesem Problem folgt auch, dass ich die Zahlen nicht effizient ausgeben kann.
Das dürfte ersichtlich werden, wenn man sich die Ausgabemethode ansieht^^
Fertig bin ich natürlich noch nicht. Die Klasse wird dazu da sein die sehr großen Zahlen aufzunehmen, die bei Verschlüsselungsalgorithmen wie RSA anfallen.
Achja: Die Dateien hab ich mal signiert, um nachweisen zu können, dass sie von mir stammen, ich in meiner Facharbeit also nichts geklaut habe.
So, hier nun eine Vorstellung meiner Arbeit, die ich im Urlaub für meine Facharbeit geschrieben habe.
Es handelt sich um eine Klasse, mit der sich (in der Theorie) beliebig große Zahlen darstellen lassen.
Die Klasse basiert auf dem Prinzip des chinesischen Restsatzes. Laut dem hat ein System von Kongruenzen genau eine Lösung x im Zahlenraum Zm wenn gilt:
x = a1 (mod m1)
...
x = an (mod mn)
m = m1 * ... * mn
Vorraussetzung dafür ist, dass die sogenannten Module m1, ..., mn teilerfremd sind (ich benutze hierfür Primzahlen)
Die Zahl x befindet sich damit im Raum zwischen 0 und m-1
Darstellen kann man die Zahl nun durch ihre Reste a1, an
Mit diesen Resten kann man dann auch rechnen:
xa + xb = xc
=> a1 + b1 = c1 (mod m1)
Soweit komme ich mit beliebig großen Zahlen im Moment auf eine ganz annehmbare Geschwindigkeit....nämlich ca 50-60 Prozent der Geschwindigkeit bei Integer-Rechnungen.
Problem ist im Moment, dass ich die Zahlen nicht in ihrer Größe vergleichen kann. Aus diesem Problem folgt auch, dass ich die Zahlen nicht effizient ausgeben kann.
Das dürfte ersichtlich werden, wenn man sich die Ausgabemethode ansieht^^
Fertig bin ich natürlich noch nicht. Die Klasse wird dazu da sein die sehr großen Zahlen aufzunehmen, die bei Verschlüsselungsalgorithmen wie RSA anfallen.
Achja: Die Dateien hab ich mal signiert, um nachweisen zu können, dass sie von mir stammen, ich in meiner Facharbeit also nichts geklaut habe.