Karim BELABAS on Tue, 28 Mar 2000 15:34:15 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Primality Testing Question |
[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/