Warning: fopen(111data/log202008141714.log): failed to open stream: No space left on device in /home/pde321/public_html/header.php on line 107

Warning: flock() expects parameter 1 to be resource, boolean given in /home/pde321/public_html/header.php on line 108

Warning: fclose() expects parameter 1 to be resource, boolean given in /home/pde321/public_html/header.php on line 113
Vorrichtung zum Ermitteln von Primzahlen - Dokument DE102005003031A1
 
PatentDe  


Dokumentenidentifikation DE102005003031A1 25.08.2005
Titel Vorrichtung zum Ermitteln von Primzahlen
Anmelder Schick, Carl, Dr., Zürich, CH
Erfinder Schick, Carl, Dr., Zürich, CH
Vertreter Rechtsanwältin Hirschberg-Weinekötter, C., Rechtsanw., 80539 München
DE-Anmeldedatum 22.01.2005
DE-Aktenzeichen 102005003031
Offenlegungstag 25.08.2005
Veröffentlichungstag im Patentblatt 25.08.2005
IPC-Hauptklasse G06F 17/10
Zusammenfassung Die Vorrichtung zum Ermitteln von Primzahlen umfasst einen Rechner oder Computer, in dem ein Algorithmus implementiert ist, mit dem für eine gegebene positive Zahl p > 3 ausgehend von einem Anfangswert $I1 und mit Hilfe einer Rekursionsformel der Form $I2 pes-Werte pes(p) gewonnen werden, die durch die Formel pes(p) = n definiert sind, wobei n jeweils der kleinste Wert ist, für den $I3 gilt, und wobei p und q0 ungerade teilerfremde Zahlen sind.

Beschreibung[de]

Die vorliegende Erfindung betrifft eine Vorrichtung zum Ermitteln von Primzahlen.

Primzahlen haben verschiedene Anwendungsmöglichkeiten, wie es sich beispielsweise aus der publiziertem Patentanmeldung US 2003/0235299 A1 (Int. CI. H04k 1/00) für Kryptographie oder sonst aus der US 2003/0235189 A1 ergibt.

Aus der Fachliteratur sind Methoden zum Ermitteln von Primzahlen bekannt, die relativ aufwendig sind, so dass sie praktisch nur von Spezialisten angewendet werden können, und es ist Aufgabe der vorliegenden Erfindung, eine Vorrichtung zum Ermitteln von Primzahlen zu schaffen, die auch von Jugendlichen im Schulalter bedienbar ist.

Diese Aufgabe wird in vorteilhafter Weise erfindungsgemäß durch eine Vorrichtung nach Patentanspruch 1 gelöst.

Andere vorteilhafte Ausführungen der Erfindung ergeben sich aus den weiteren abhängigen Ansprüchen.

Die Erfindung beruht auf der Erkenntnis, dass jede ungerade Zahl p ein Spektrum von Zahlen qi mit i = {0, 1, 2 , 3, ... n} aufweist, welches im Folgenden an Hand zweier Figuren (1 und 2) näher erläutert wird.

Als Anfangswert q0 kann beispielsweise eine ungerade Zahl gewählt werden, wobei p und |q0| < p relativ prim sein müssen. Dieses Spektrum ergibt sich aus dem folgenden Algorithmus:

Der Algorithmus qn+1 = p – 2 |qn| = qn+1 wird im Folgendem Spektralalgorithmus zur Zahl p genannt. Im Allgemeinen ist es statt |x| auch üblich abs(x) zu schreiben, worin x eine beliebige positive oder negative Zahl ist. Es ist leicht zu beweisen, dass falls p und q0 relativ prim sind und p > 3 eine positive ungerade ganze Zahl ist, p ein Spektrum von sich wiederholenden ungeraden Zahlen qk mit |qk| < p hat, wobei auch qk und p relativ prim sind. Dabei besteht dieses Spektrum aus einer beschränkten Anzahl Ts ≤ Tv = (p – 1)/2 ungerader Zahlen qk mit |qk| < p, die sich periodisch in einer bestimmten Reihenfolge, das heißt in Runden, wiederholen, die alle im Betrag voneinander verschieden sind. Zur Vereinfachung wird hier eine Funktion pes(p) definiert, derart, dass pes(p) = Ts(p) der Spektralperiode Ts(p) der ungeraden Zahl p entspricht.

Man kann experimentell feststellen, dass für einige Primzahlen wie p = 17 oder p = 31 die Spektralperiode pes(p) kleiner als 8 bzw. 15, das heißt kleiner als der sich aus dem erwähnten Ausdruck Tv = (p – 1)/2 ergebende Wert ist. Für andere Primzahlen ist die Periode genau (p – 1)/2. Es gibt dementsprechend zwei Arten von Primzahlen, nämlich "harte" Primzahlen mit einer vollständigen Periode pes(p) = Tv = (p – 1)/2 und "weiche" Primzahlen mit einer reduzierten Periode pes(p) = Tr < (P – 1)/2.

Die Zahlen in den Tabellen (1 und 2) wurden mit Hilfe des Spektralalgorithmus als Funktion pes(p) nach der Definition pes(p) = Ts(p) ermittelt. Dabei weisen zum Beispiel die Primzahlen 37 und 47 (1) und 53, 59 und 61 (2) eine vollständige Periode auf. Sie sind daher "hart". Im Gegensatz dazu weisen die Primzahlen 41 und 43 (1) eine reduzierte Spektralperiode auf, und sie sind daher "weich".

Entsprechendes gilt beispielsweise für die weiche zusammengesetzte Zahl 51 (2) bezüglich der eulerschen-Funktion &#981;(p) (Totient) statt der Funktion (p – 1).

Die Primzahlen p mit reduzierter Periode Tr(p) stimmen nicht mit anderen klassischen Reihen von Primzahlen überein. Solche "weichen" Primzahlen befinden sich nur teilweise unter den Primzahlen der Form 4 k + 1 oder 4 k – 1, oder den "irregulären" Primzahlen nach Kummer, oder den sogenannten "guten" Primzahlen, oder den Primzahlen von Sophie Germain usw.

Man kann auch leicht experimentell feststellen, dass wenn eine Zahl p zusammengesetzt ist, ihr pes-Wert pes(p) kleiner ist als Tv = (p – 1)/2. Der Spektralalgorithmus eignet sich daher sehr gut, um "harte" Primzahlen von zusammengesetzten Zahlen zu unterscheiden.

Jede weiche ungerade Zahl p weist ein Spektrum mit einer Anzahl B Teilspektren auf. Der Parameter B definiert somit für jede weiche Zahl p eine Anzahl verschiedener Teilspektralreihen, wobei im Ausdruck pes(p) = ½ &#981;(p)/B der Parameter B nur ganze Werte aufweisen kann, nämlich B = 1 für harte Zahlen p bzw. B = 2, 3,... für weiche Zahlen p, worin &#981;(p) = Totient(p) ist.

Unabhängig davon, ob es sich um eine harte oder weiche ungerade Zahl p handelt, ist somit der Zahl p eine totale Anzahl Ts = Totient(p)/2 – &#981;(p)/2 = B·pes(p) von qk-Werten zugeordnet, die in B Gruppen oder Teilspektren verteilt sind, und jede der B Gruppen weist jeweils eine Anzahl n = pes(p) Werte qk auf. Im Sonderfall, dass p eine Primzahl ist, gilt: Tv = B·pes(p) = (p – 1)/2.

Ist zudem &#981;(p) = 2n = 2 pes(p) die Phifunktion (Totient) einer ungeraden Zahl p, so ist der Ausdruck 22n – 1 = 2&#981;(P) – 1 = 22pes(p) – 1 durch p teilbar.

Mit Hilfe des Spektralalgorithmus, der durch ein einfaches Computerprogramm implementiert werden kann, und eines Rechners kann der pes-Wert einer beliebigen ungeraden Zahl p eindeutig ermittelt werden, und es gelten folgende praktische Eigenschaften:

Gilt für den ermittelten pes-Wert einer ungeraden Zahl p die Beziehung pes(p) = (p – 1)/2, so handelt es sich um eine harte Primzahl p.

Führt der ermittelte pes-Wert einer ungeraden Zahl p zu einem Parameter B, definiert durch den Quotienten B = ½ (p – 1)/pes(p) > 1, der nicht eine ganze Zahl B > 1 darstellt, so ist die Zahl p zusammengesetzt.

Gilt für den ermittelten pes-Wert einer ungeraden Zahl p, dass der Parameter B definiert durch den Quotienten B = ½ (p – 1)/pes(p) > 1 genau eine ganze Zahl > 1 darstellt, so kann die Zahl p eine weiche Primzahl oder eine zusammengesetzte Zahl sein. Ist nämlich dieser Ausdruck eine ganze Zahl B > 1, so ist p entweder eine weiche Primzahl oder eine sogenannte pouletsche Zahl, wobei Listen von pouletschen Zahlen bekannt sind.

Zur Lösung der Aufgabe, ob eine ungerade Zahl p prim oder zusammengesetzt ist, kann zusammenfassend ein Verfahren mit folgenden Verfahrensschritten durchgeführt werden:

Es sind zunächst mit Hilfe des Spektralalgorithmus und eines Computers der pes-Wert der Zahl p und daraus auch der Parameter B, wie oben definiert, zu ermitteln:

Ergibt sich für den ermittelten Parameter B ein Wert B = 1, so ist p eine harte Primzahl. Ist B eine rationale Zahl, dargestellt als Quotient zweier ganzer Zahlen, die relativ prim sind, so ist p eine zusammengesetzte Zahl; und ist schließlich B > 1 eine ganze Zahl, so kann p entweder eine weiche Primzahl oder eine sogenannte pouletsche Pseudoprimzahl sein.

Ist p = 21449 eine Primzahl ?

Die erfindungsgemäße Vorrichtung liefert den folgenden pes-Wert:

pes(21449) = 264. Daraus folgt: B = (21449 – 1)/(2·264) = 2681/66. Da B keine ganze Zahl ist, ist somit p eine zusammengesetzte Zahl. Dabei ist 264 = 2·11·12 mit 11 = pes(89) und 12 = pes(241); somit ist p = 21449 = 89·241 eine zusammengesetzte Zahl.

Ist p = 10897 mit pes(10897) = 64 eine Primzahl ?

Da B = (10897 – 1)/128 = 681/8 (keine ganze Zahl), ist p zusammengesetzt. Dabei ist 4 ein Teiler von 64 und da pes(17) = 4, ist 17 tatsächlich ein Teiler von 10897 = 17·641.

Ist p = 5527 eine Primzahl ?

Da pes(5527) = 2763 und B = (5527 – 1)/5526 = 1 ist, ist p eine harte Primzahl.

Ist p = 49981 eine Primzahl ?

Da pes(49981) = 30 und B = (49981 – 1)/60 = 833 (ganze Zahl) ist, ist p entweder eine weiche Primzahl oder eine pouletsche Zahl. Die Teiler von 30 sind: 2, 3, 5, 6, 10, 15 und 30. Dabei gilt pes(331) = 15 und pes(151) = 15.

Die Zahl p = 49981 ist effektiv durch 331 und 151 teilbar.

Ist p = 174763 eine Primzahl ?

Mit Hilfe der erfindungsgemäßen Vorrichtung wird zunächst pes(174763) = 19 ermittelt, daraus folgt B = (174763 – 1)/38 = 4599 (ganze Zahl), und p kann prim oder zusammengesetzt sein.

Der Ausdruck 2·19 + 1 = 39 = 3·13 führt zu keiner Primzahl. Da sich die Zahl 174763 nicht in der Liste der pouletschen Zahlen befindet, ist sie prim.

Diese Vorrichtung erlaubt daher mit Sicherheit wenigstens harte Primzahlen zu ermitteln, das heißt ohne Pseudoprimzahlen berücksichtigen zu müssen.

Die pes-Funktion gibt in vielen Fällen nicht nur eine eindeutige Antwort auf die Frage, ob eine ungerade Zahl p prim oder zusammengesetzt ist, sondern es ist mit ihrer Hilfe auch oft möglich, mindestens einen Faktor der Zahl p zu ermitteln. Ist der pes-Wert der Zahl p bekannt, so erlaubt dies, den Parameter B = ½/(p – 1)/pes(p) sofort zu berechnen, und das B-Kriterium besagt, dass alle ungeraden Zahlen p, für die der Parameter B keine ganze Zahl ist, mit Sicherheit zusammengesetzte Zahlen sind, die man daher – bezüglich der gestellten Frage – nicht in der Tabelle der pouletschen Zahlen suchen muss. Im Folgenden wird nun eine weitere Formel angegeben, um, ausgehend vom pes-Wert, einen Faktor der Zahl p zu erhalten.

Das B-Kriterium ist daher scharf genug, um bei vielen Zahlen zu entscheiden, ob sie zusammengesetzt oder prim sind, jedoch ungenügend, um damit Faktoren der Zahl p, falls sie zusammengesetzt ist, zu ermitteln. Zu diesem Zweck ist folgende Eigenschaft nützlich.

Es gibt zusammengesetzte Zahlen p = p1 p2 p3 ..., von denen mindestens ein Faktor p1 durch die Formel p1 = ggT[p, (2pes(p)/&ggr; + &lgr;)] ermittelt werden kann, worin &lgr; = 1 oder &lgr; = – 1 sein kann und pes(p)/&ggr; < pes(p) eine ganze Zahl ist, und worin mit ggT ein Algorithmus zur Bestimmung des grössten gemeinsamen Teilers der Zahl p und des Ausdrucks in runden Klammern bezeichnet wird.

  • pes(271·293) = pes(79403) = 39420
  • ggT [79403, (239420/02 – 1)] = 271 mit &ggr; = 2 &lgr; = –1
  • pes(271·307) = pes(83197) = 4590
  • ggT[83197, (2459 + 1)] = 307 mit &ggr; = 10 &lgr; = +1
  • ggT[83197, (22295 – 1)] = 271 mit &ggr; = 2 &lgr; = –1
  • pes(293·277) = pes(81161) = 3358 = 2·23·73
  • ggT[81161, (248 + 1)] = 277 mit &ggr; = 73 &lgr; = +1
  • ggT[81161, (248 + 1)] = 293 mit &ggr; = 23 &lgr; = +1
  • pes(59·1103·2089) = pes(135945853) = 58
  • ggT[135945853, (229 + 1)] = 59 mit &ggr; = 2 &lgr; = +1

Kompakte Pseudoprimzahlen sind jene, die sich nicht mit Hilfe dieser Eigenschaft zerlegen lassen. Ist beispielsweise der pes-Wert einer zusammengesetzten Zahl p prim, so ist es mit Hilfe dieser Formel nicht möglich, die Faktoren der Zahl p zu ermitteln. Zum Beispiel pes(1103·2089) = pes(2304167) = 29 mit ggT [2304167, (229 – 1)] = 2304167 und ggT [2304167, (21 – 1)] = 1.

In weiterer Ausgestaltung der Erfindung kann daher die Liste der pouletschen Zahlen durch eine kürzere Liste mit solchen kompakten Pseudoprimzahlen ersetzt werden.

Die erfindungsgemäße Vorrichtung kann beispielsweise auch ein Schultaschenrechner sein, um in unterhaltsamer Weise Primzahlen zu suchen.

Eine solche Vorrichtung kann derart ausgestaltet sein, dass sie bis zu einer vorgegebenen oberen Grenze von ungeraden Zahlen p pes-Werte pes(p) durch einfaches Eintippen der Zahl p und Betätigung von nur einer, oder zwei oder einer geringen Anzahl von Tasten ermitteln kann.

Weitere Beispiele:

Wie viele Primzahlen gibt es zwischen 100 000 000 und 100 000 100 ? Mit Hilfe des Spektralalgorithmus kann ein Personalcomputer die pes-Werte der Zahlen

p = 108 + 1 bis p = 108 + 99 ermitteln.

Die pes-Werte die zu B = ½(p – 1)/pes(p) = ganze Zahl führen sind:

pes(100 000 007) = 50 000 003 mit B = 1

pes(100 000 037) = 50 000 018 mit B = 1

pes(100 000 039) = 50 000 019 mit B = 1

pes(100 000 049) = 6 250 003 mit B = 8

pes(100 000 073) = 25 000 018 mit B = 2

pes(1000 000 81) = 6 250 005 mit B = 8

Die drei ersten Zahlen sind harte Primzahlen. Für die drei letzten müsste man die Liste der pouletschen Zahlen konsultieren. Sie sind aber tatsächlich weiche Primzahlen.

Es sei eine Primzahl größer als 1 000 000 000 gesucht:

Die Rechnung mit der erfindungsgemäßen Vorrichtung ergibt, dass unter den Zahlen (109 + 1), (109 + 3) und (109 + 7) nur p = (109 + 7) einen pes-Wert hat, der zu B = ganze Zahl führt. Diese Rechnung ergibt pes(109 + 7) = 500 000 003. Die Zahl 109 + 7 ist demzufolge eine harte Primzahl.

In weiterer Ausgestaltung der Erfindung kann die Vorrichtung derart ausgestaltet sein, dass sie zunächst automatisch Zahlen der Form r = p 2m erkennen und durch 2m dividieren kann, bevor der pes-Wert von p ermittelt wird.

Nachher gilt pes(r) = pes(p).

Für weitere Details über die pes-Funtion wird auf das Buch "Trigonometrie und unterhaltsame Zahlentheorie" von Carl Schick, 8044 Zürich, ISBN 3-9522917-0-6, verwiesen, das erst nach dem Prioritätstag dieser Patentanmeldung der Öffentlichkeit zugänglich gemacht werden soll.


Anspruch[de]
  1. Vorrichtung zum Ermitteln von Primzahlen, dadurch gekennzeichnet, dass in einem Rechner oder Computer ein Algorithmus implementiert ist, mit dem für eine gegebene ganze Zahl p > 3 ausgehend von einem Anfangswert |q0| < p und mit Hilfe der Rekursionsformel qn = p – 2·|qn-1| pes-Werte pes(p) gewonnen werden, die durch die Formel pes(p) = n definiert sind, wobei n jeweils der kleinste Wert ist, für den |qn| = |q0| gilt, und wobei p und q0 ungerade teilerfremde Zahlen sind.
  2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, dass durch eine weitere Programmierung ein Wert B = ½(p – 1)/pes(p) ermittelt wird, um festzustellen, dass bei B = 1 die Zahl p eine harte Primzahl ist oder dass, falls B > 1 einen Bruch darstellt, diese Zahl p zusammengesetzt ist.
  3. Vorrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass darin eine Liste von Pseudoprimzahlen oder kompakten Pseudoprimzahlen gespeichert ist, und dass Mittel vorhanden sind, um, falls ein ermittelter Wert B = ½(p – 1)/pes(p) ≠ 1 eine ganze Zahl darstellt, festzustellen, ob sich die gegebene Zahl p in dieser Liste befindet, wobei sie in diesem Fall zusammengesetzt ist.
  4. Vorrichtung nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass diese Vorrichtung ein Taschenrechner oder ein Personalcomputer ist.
  5. Vorrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass sie bis zu einer vorgegebenen oberen Grenze von Zahlen p pes-Werte pes(p) durch Eintippen der Zahl p und Betätigung von einer einzigen Taste oder von zwei oder einer geringen Anzahl Tasten ermitteln kann.
  6. Vorrichtung nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass sie als Gerät ausgestaltet ist, um in unterhaltsamer Weise Primzahlen zu suchen.
  7. Vorrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass sie einen ggT-Algorithmus und Mittel umfasst, um Faktoren der Form pi = 99T[p, (2pes(p)/&ggr; + &lgr;)] zu ermitteln, worin &lgr; = 1 oder &lgr; = – 1 sein kann und &ggr; > 1 ein Teiler von pes(p) ist, und worin mit ggT ein Algorithmus zur Bestimmung des grössten gemeinsamen Teilers der Zahl p und des Ausdrucks zwischen den runden Klammern bezeichnet wird.
  8. Vorrichtung nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, dass sie ausgebildet ist, um zunächst automatisch Zahlen der Form r = p 2m zu erkennen und durch 2m zu dividieren, bevor der pes-Wert von p ermittelt wird.
  9. Vorrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass eine Liste von pouletschen Zahlen gespeichert ist, um zu prüfen, ob sich darunter eine Zahl p befindet, bevor der pes-Wert pes(p) berechnet wird.
  10. Computerprogramm zum Betreiben einer Vorrichtung nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass es einen Algorithmus umfasst, mit dem ausgehend von einem Anfangswert |q0| < p und mit Hilfe der Rekursionsformel qn = p – 2·|qn-1| pes-Werte pes(p) gewonnen werden, die durch die Formel pes(p) = n definiert sind, wobei n jeweils der kleinste Wert ist, für den |qn| = |q0| gilt, und wobei p und q0 ungerade teilerfremde Zahlen sind.
Es folgen 2 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com