re: programming with LARGE integers.

From: George Marsaglia (geo_at_stat.fsu.edu)
Date: 02/08/05 

Date: Tue, 8 Feb 2005 08:49:48 -0500

I too have an interest in LARGE integer arithmetic,
and perhaps those experienced in software mentioned
in this thread can suggest applications to the
problem of establishing periods of certain RNGs.

Those periods are the order of b=2^32 for
primes of the form a*2^n+1.

For example, the order of
b=2^32 for the prime p=2228926*2^131072+1
is 2228926*2^131066, i.e., a*2^(n-6)

I currently use Maple for establishing such
periods. Maple's order(b,p) will not work for
such large p's, but this will:

  y:=b&^a mod p:
  for i to n do
  y:=y*y mod p:
  if y=1 then k:=i: break fi:
             od:
  k;

After an hour or two, the resulting k is
typically from n-10 to n-6, that is,
I 'lose' from six to ten 2's from the exponent.

Of course to verify that k is the order of b mod p
it is necesary to confirm that the code

 y&^(a/d) mod p:
 for i to k do y:=y*y mod p od:
 min(y,2);

 returns 2 for every prime divisor d of a.

This approach, using Maple with
      a=9995 and n=1282755
would take days, and the Everest
for current climbers:
the order of b=2^32 for the
prime p=28433*2^7830457+1
might take weeks or months.

I predict that the order for 'Everest'
will be around 28433*2^7830450.

Can any of you enthusiasts find, or
outline ways to find, such orders?

George Marsaglia

Relevant Pages

  • Ford and Oracle
    ... Ford kills 'Everest' procurement software system ... major procurement software system built around Oracle Corp.'s 11i E-Business ... Suite of applications. ... Everest, and collapse its purchasing processes around its original ...
    (comp.os.vms)
  • Re: Debian packages similar to mathematica or mathlab ?
    ... Not any Linux, though: x86, Alpha and PPC. ... than some other applications, such as Maple, which is available for ... x86/x86_64 only (AFAIK). ...
    (Debian-User)