ARIBAS

ARIBAS ist ein 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.

==> n := factorial(30).
-: 265_25285_98121_91058_63630_84800_00000

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):

==> rab_primetest(n+1).
-: false

Da der Nachfolger von 30, also 31, eine Primzahl und somit der Restklassenring $\Z/31\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:

==> (n+1) mod 31.
-: 0

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?

==> q := (n+1) div 31.
-: 8_55654_38649_09388_98826_80154_83871
==> rab_primetest(q).
-: false

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

==> rho_factorize(q).
working .
factor found after 256 iterations
-: 12421

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

==>  31 * 12421 * 82561 * 1080941 * 7_71906_83199_27551.
-: 265_25285_98121_91058_63630_84800_00001

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 Gleitpunktzahlarithmetik, in der reelle Zahlen bis zu 4096 Bit belegen können:

==> set_floatprec(4096).
-: 4096
==> sqrt(2).
-: 1.41421_35623_73095_04880_16887_24209_69807_85696_71875_37694_80731_76679_
73799_07324_78462_10703_88503_87534_32764_15727_35013_84623_09122_97024_92483_
60558_50737_21264_41214_97099_93583_14132_22665_92750_55927_55799_95050_11527_
82060_57147_01095_59971_60597_02745_34596_86201_47285_17418_64088_91986_09552_
32923_04843_08714_32145_08397_62603_62799_52514_07989_68725_33965_46331_80882_
96406_20615_25835_23950_54745_75028_77599_61729_83557_52203_37531_85701_13543_
74603_40849_88471_60386_89997_06990_04815_03054_40277_90316_45424_78230_68492_
93691_86215_80578_46311_15966_68713_01301_56185_68987_23723_52885_09264_86124_
94977_15421_83342_04285_68606_01468_24720_77143_58548_74155_65706_96776_53720_
22648_54470_15858_80162_07584_74922_65722_60020_85584_46652_14583_98893_94437_
09265_91800_31138_82464_68157_08263_01005_94858_70400_31864_80342_19489_72782_
90641_04507_26368_81313_73985_52561_17322_04024_50912_27700_22694_11275_73627_
28049_57381_08967_50401_83698_68368_45072_57993_64729_06076_29969_41380_47565_
48237_28997_18032_68024_74420_62926_91248_59052_18100_44598_42150_59112_02494_
41341_72853_14781_05803_60337_10773_09182_86931_47101_71111_68391_65817_26889_
41975_87165_82152_12822_95184_88472_08969_46338_62891_56288_27659_52635_14054_
22676_53239_69461_75112_91602_40871_55101_35150_45538_12875_60052_63146_80171_
27402_65396_94702_40300_51749_53188_62925_63138_51881_63478_00156_93691_76881_
85237_86840_52287_83762_93892_14300_65586_95686_85964_5952

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

 function trialdiv(x: integer): array;
 var
   st: stack;
   q: integer;
 begin
   q := 2;
   while q := factor16(x,q) do
       stack_push(st,q);
       x := x div q;
   end;
   stack_push(st,x);
   return stack2array(st);
 end;

Literatur

• Otto Forster: Algorithmische Zahlentheorie. Vieweg, 1996, ISBN 352806580X.

Weblinks

• ARIBAS Webseite der Universität München