Re: Primality Testing Question

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

[Mark Andrews:]
> I'm a developer (not a mathematician) recently tasked with finding 1) a
> primality test algorithm for numbers at least up to about 10^20 and
> preferably 10^40. It must be a test for true primality, not pseudo
> primality 2) a factoring algorithm. Poking around a bit, I came across
> Pari. The manual leads me to believe a good composite pseudo primality test
> is incorporated, but I have no idea from docs what range of numbers
> IsPrime() is valid for as a true primality test. In addition, I would
> appreciate a coded example of how to do factorization using Pari. The ideal
> would be to incorporate, as a library, those parts of Pari applicable to
> the task into a Windows 32 bit executable.

isprime(n) is never valid as a true primality test (unless n < 3)

In library mode, the function miller(n, k) will check whether n is prime
using k pre-determined bases, see the comments in src/basemath/ifactor1.c
(lines 87 and below). For k = 7, all composites up to 

   n < 341 550 071 728 321 == 10670053 * 32010157

are detected. There's no true primality test in PARI (shame...) but it should
be quite straightforward to implement e.g. Selfridge's theorem for the range
you're interested in (n < 10^40). Factor n - 1, then for each pseudo-prime q
dividing n-1, find (by trial and error: try 2,3,...) an integer a(q) such
that a ^ (n-1)/q != 1 (mod n)  [ and check that a^(n-1) = 1 (mod n) ]. If you
succeed for each q, then n is prime, provided the q's are true primes; so
start over with the q's until they all fall below Jaeschke's bound as given
above.


As for factorization: (assuming n is a t_INT GEN, e.g n = lisexpr("129381928"))

  GEN x = factor(n);

then

  x[1] is a (column) vector of (pseudo)primes (as GENs)
  x[2] is a (column) vector of exponents      (as GENs)

Hope this helps,

   Karim.

P.S: please note that PARI copyright forbids including any part of the PARI
code in commercial software without our prior approval.
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/