ARIBAS

from Wikipedia, the free encyclopedia

ARIBAS is a free computer program for number theoretic calculations. It was developed by Otto Forster under the GNU General Public License .

classification

ARIBAS is an interpreter that uses a syntax based on Pascal . A long number arithmetic is fundamental for ARIBAS , which allows exact calculations to be carried out even with very large, whole numbers. Based on this, ARIBAS offers an extensive library of functions from the area of algorithmic number theory . Forster's book Algorithmic Number Theory is based on ARIBAS and introduces the mathematically interested reader to the program, so to speak.

Since ARIBAS always calculates with numbers, it is not a computer algebra system .

A sample interactive session

First, the factorial of the number 30 is calculated. The result is assigned to the variable n. To make long numbers easier to read, ARIBAS uses an underscore after every five digits in the output . 

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

Although the number n is not exactly small, it has all sorts of small prime factors : exactly the prime numbers less than 30 (with different exponents). If you add one, you get a number that cannot have a divisor less than or equal to 30. (E.g. 13 is a divisor of n and n + 13, but not n + 1). For certain output numbers (instead of the number 30 in our example) even large prime numbers, so-called arise in this way Faculty primes . The ARIBAS function can be used to rab_primetestprove in a fraction of a second that this is not a prime number in the present case (see Miller-Rabin test ): 

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

Since the successor of 30, i.e. 31, is a prime number and thus the remainder class ring is even a field , a not too complicated consideration shows that

must apply. (Idea of ​​proof: the factors 2, 3, ..., 29 cancel each other out modulo 31 in suitable pairs to 1!) In other words, 31 is a divisor of n + 1: 

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

This example shows the importance of exact long number arithmetic: With a pocket calculator you can get 30! also calculate. But due to the limited accuracy of about 10 digits, the numbers 30! and 30! +1 do not differ from each other. The proof that 30! +1 is divisible by 31 without a remainder cannot be provided with a pocket calculator.

Can the quotient (n + 1) / 31 be further factorized? 

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

So q is not a prime number either. Using the Pollard-Rho method one finds: 

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

By repeating this principle one obtains the presumable prime factorization of n + 1: 

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

The caveat here, presumably, is to say that it has not been proven that all the calculated factors are really prime. rab_primetest(...)delivered "true" several times for each factor . It only follows from this that there is a certain (relatively high) probability that the numbers are prime. This is why the Miller-Rabin test is also called a probabilistic prime number test. A "false" result, on the other hand, is deterministic: it is then by no means a prime number.

More code examples

ARIBAS also has an extended floating point number arithmetic in which real numbers can occupy up to 4096 bits: 

==> 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

Furthermore, ARIBAS can be extended by user-defined functions, as shown here using the example of a function for the decomposition of small numbers into prime factors: 

 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;

literature

Web links