ARIBAS
# ARIBAS

ARIBAS ist ein freies Computerprogramm für zahlentheoretische Berechnungen. Es wurde von Otto Forster unter der GNU General Public License entwickelt.

## Einordnung

ARIBAS ist ein Interpreter, der eine an Pascal angelehnte Syntax verwendet. Grundlegend für ARIBAS ist eine Langzahlarithmetik, die es gestattet, exakte Berechnungen auch mit sehr großen, ganzen Zahlen durchzuführen. Darauf aufbauend bietet ARIBAS eine umfangreiche Bibliothek von Funktionen aus dem Bereich der algorithmischen Zahlentheorie an. Forsters Buch Algorithmische Zahlentheorie baut auf ARIBAS auf und führt den mathematisch interessierten Leser sozusagen nebenbei in das Programm ein.

Da ARIBAS stets mit Zahlen rechnet, handelt es sich nicht um ein Computeralgebrasystem.

## Eine interaktive Beispielsitzung

Zunächst wird die Fakultät der Zahl 30 berechnet. Das Ergebnis wird der Variable n zugewiesen. Zur leichteren Lesbarkeit langer Zahlen verwendet ARIBAS bei der Ausgabe einen Unterstrich nach jeweils fünf Ziffern.

Obwohl die Zahl n nicht gerade klein ist, besitzt sie lauter kleine Primfaktoren: genau die Primzahlen kleiner 30 (mit unterschiedlichen Exponenten). Wenn man Eins hinzu addiert, so erhält man eine Zahl, die keinen Teiler kleiner oder gleich 30 besitzen kann. (Z. B. ist 13 ein Teiler von n und von n+13, aber nicht von n+1). Für gewisse Ausgangszahlen (anstelle der Zahl 30 in unserem Beispiel) entstehen auf diese Art sogar große Primzahlen, sogenannte Fakultätsprimzahlen. Dass es sich im vorliegenden Fall um keine Primzahl handelt, lässt sich mit der ARIBAS Funktion rab_primetest in einem Sekundenbruchteil nachweisen (vgl. Miller-Rabin-Test):

Da der Nachfolger von 30, also 31, eine Primzahl und somit der Restklassenring $\mathbb {Z} /31\mathbb {Z}$ sogar ein Körper ist, zeigt eine nicht allzu komplizierte Überlegung, dass

    $30!\equiv -1\mod 31$

gelten muss. (Beweisidee: Die Faktoren 2, 3, ..., 29 heben sich modulo 31 jeweils in geeigneten Paaren zu 1 auf!) Mit anderen Worten, 31 ist ein Teiler von n+1:

An diesem Beispiel wird die Bedeutung einer exakten Langzahlarithmetik deutlich: Mit einem Taschenrechner lässt sich zwar 30! ebenfalls berechnen. Aber aufgrund der auf etwa 10 Ziffern begrenzten Genauigkeit lassen sich die Zahlen 30! und 30!+1 nicht voneinander unterscheiden. Der Nachweis, dass 30!+1 durch 31 ohne Rest teilbar ist, lässt sich also mit einem Taschenrechner nicht erbringen.

Kann der Quotient (n+1)/31 noch weiter faktorisiert werden?

Auch q ist also keine Primzahl. Durch Anwendung der Pollard-Rho-Methode findet man:

Durch Wiederholung dieses Prinzips erhält man die vermutliche Primfaktorzerlegung von n+1:

Die Einschränkung vermutlich will hierbei sagen, dass es nicht bewiesen ist, dass sämtliche berechneten Faktoren auch wirklich prim sind. rab_primetest(...) lieferte zwar bei jedem Faktor mehrfach "true". Daraus folgt aber nur, dass es sich mit einer gewissen (relativ hohen) Wahrscheinlichkeit um Primzahlen handelt. Daher spricht man beim Miller-Rabin-Test auch von einem probabilistischen Primzahltest. Ein Ergebnis "false" hingegen ist deterministisch: Es handelt sich dann keinesfalls um eine Primzahl.

## Weitere Code-Beispiele

ARIBAS verfügt auch über eine erweiterte Gleitkommaarithmetik, in der rationale Zahlen bis zu 4096 Bit belegen können:

Ferner kann ARIBAS durch benutzerdefinierte Funktionen erweitert werden, wie hier am Beispiel einer Funktion zur Zerlegung kleiner Zahlen in Primfaktoren gezeigt werden soll:

