Juergen, You may want to consider a probabilistic method such as the Rabin-Miller test.  This test can be performed very quickly, and some variations on it make it very accurate.  How important is proof of primality in your application? -Ted <div>On 11/13/05, Juergen Bullinger <<a href="mailto:juergen.bullinger@gmx.net">juergen.bullinger@gmx.net</a>> wrote:<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Hello, I need to do compositeness checks on very large numbers (thousands of bits). At the moment I use trial divisions and termat checks (2^(p-1) ?= 1 (mod p)). * At the moment I use mpz_powm for this purpose, but I wonder if there is a better/faster way to do that, because for me it is sufficient to use 2 as the base (mpz_powm(resultVar, 2, phiVar, prime)). I know that there are functions with base 2, but it looks that they are all using long integers as an exponent, but I need larger exponents. Thank you in advance Juergen -- Juergen Bullinger <<a href="mailto:juergen.bullinger@gmx.net">juergen.bullinger@gmx.net</a>> _______________________________________________ gmp-discuss mailing list <a href="mailto:gmp-discuss@swox.com">gmp-discuss@swox.com</a> <a href="https://gmplib.org/mailman/listinfo/gmp-discuss">https://gmplib.org/mailman/listinfo/gmp-discuss</a> </blockquote></div>