To code a "pause and save" function in GMP

2007-09-26, 14:26

Hello,

I'm trying to make a soft for calculations and studies on prime numbers.

Actually, my calculations consist of several calls to the GMP library (maybe ten to create the number I'll test) but the longest part, as you can guess, is the call to the GMP primality test function mpz_probab_prime_p(N, k) (an improved version of the Miller-Rabin test). I think you know this function, usually I use "10" as second argument: mpz_probab_prime_p(N, 10). I would like to be able to pause and save the process AT ANY TIME (even during the call to mpz_probab_prime_p(N, k), which can last many days), in order to be able to shut down the computer (I travel a lot) and, later, to restart the computer and go on the calculations where I stopped them. How can I do this?

Thanks for help!

akruppa · 2007-09-26, 14:36

I don't think GMP itself supplies functionality to save its state and resume later. A simple way would be calling mpz_probab_prime_p(N, 1) ten times instead; if you have to shut down the computer, you'll have to re-run only the missing calls. Otoh, I doubt you really need 10 Miller-Rabin runs for testing primality. If your input number isn't specifically desinged to fool probable prime tests, one run should be enough to establish primality beyond reasonable doubt.

If you want to checkpoint a single Rabin-Miller run, you could write the exponentiation routine yourself and add periodic saving of its state. A somewhat gory way would be running the code in a debugger and creating a core dump when you want to interrupt, later you can resume from the core file.

There was a PRP program based on George Woltman's FFT code some time ago, I think it had save-and-resume functionality. Does that still exist?

Alex

ewmayer · 2007-09-26, 16:21

Alex is far more closely acquainted with GMP than am I, but it seems to me that if mpz_probab_prime_p() is based on Miller-Rabin, then it's basically a set of individual pseudoprime tests using various bases. Have you looked at the guts of mpz_probab_prime_p() to see if there is an obvious loop-over-bases structure which you could simply extract and instead do as a sequence of individual calls? Then, even if you lose the state during any of of these pseudoprime sub-tests, that would represent a far smaller time loss. You just need to make sure there is some kind of simple logging which lets you know how many of the bases it got through in order to restart at the appropriate "checkpoint."

Jens K Andersen · 2007-09-26, 21:34

GMP's mpz_probab_prime_p(N, k) does 3 things (or stops if N is shown composite):
1) Trial factoring of N.
2) A base 210 Fermat prp test.
3) k Miller-Rabin tests with random bases.

If you call it more than once then you waste time on repeating trial factoring and the same Fermat test.
You can call mpz_millerrabin directly to skip trial factoring, and you can make a copy of it without the lines that perform a Fermat test.

Note that if you have an x86 cpu with Linux or Windows then PrimeForm/GW is much faster than GMP at gigantic prp tests. I have never heard of people who search primes with GMP at sizes that take days to test. But if you have already found a prp with PrimeForm/GW then it can make sense to check it with GMP.

2007-09-26, 14:26	#1
initial 11×479 Posts	To code a "pause and save" function in GMP Hello, I'm trying to make a soft for calculations and studies on prime numbers. Actually, my calculations consist of several calls to the GMP library (maybe ten to create the number I'll test) but the longest part, as you can guess, is the call to the GMP primality test function mpz_probab_prime_p(N, k) (an improved version of the Miller-Rabin test). I think you know this function, usually I use "10" as second argument: mpz_probab_prime_p(N, 10). I would like to be able to pause and save the process AT ANY TIME (even during the call to mpz_probab_prime_p(N, k), which can last many days), in order to be able to shut down the computer (I travel a lot) and, later, to restart the computer and go on the calculations where I stopped them. How can I do this? Thanks for help!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
"Factorizing" function	jnml	Miscellaneous Math	8	2017-11-01 18:31
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"Cannot initialize FFT code" with no swap (SOLVED)	Unregistered	Information & Answers	0	2010-07-15 14:10
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12
Search for a number theoretic function related to "prime divisor sums"	juergen	Math	2	2004-07-10 23:01

2007-09-26, 14:36	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I don't think GMP itself supplies functionality to save its state and resume later. A simple way would be calling mpz_probab_prime_p(N, 1) ten times instead; if you have to shut down the computer, you'll have to re-run only the missing calls. Otoh, I doubt you really need 10 Miller-Rabin runs for testing primality. If your input number isn't specifically desinged to fool probable prime tests, one run should be enough to establish primality beyond reasonable doubt. If you want to checkpoint a single Rabin-Miller run, you could write the exponentiation routine yourself and add periodic saving of its state. A somewhat gory way would be running the code in a debugger and creating a core dump when you want to interrupt, later you can resume from the core file. There was a PRP program based on George Woltman's FFT code some time ago, I think it had save-and-resume functionality. Does that still exist? Alex

2007-09-26, 16:21	#3
ewmayer ∂²ω=0 Sep 2002 República de California 103×113 Posts	Alex is far more closely acquainted with GMP than am I, but it seems to me that if mpz_probab_prime_p() is based on Miller-Rabin, then it's basically a set of individual pseudoprime tests using various bases. Have you looked at the guts of mpz_probab_prime_p() to see if there is an obvious loop-over-bases structure which you could simply extract and instead do as a sequence of individual calls? Then, even if you lose the state during any of of these pseudoprime sub-tests, that would represent a far smaller time loss. You just need to make sure there is some kind of simple logging which lets you know how many of the bases it got through in order to restart at the appropriate "checkpoint."

2007-09-26, 21:34	#4
Jens K Andersen Feb 2006 Denmark E6₁₆ Posts	GMP's mpz_probab_prime_p(N, k) does 3 things (or stops if N is shown composite): 1) Trial factoring of N. 2) A base 210 Fermat prp test. 3) k Miller-Rabin tests with random bases. If you call it more than once then you waste time on repeating trial factoring and the same Fermat test. You can call mpz_millerrabin directly to skip trial factoring, and you can make a copy of it without the lines that perform a Fermat test. Note that if you have an x86 cpu with Linux or Windows then PrimeForm/GW is much faster than GMP at gigantic prp tests. I have never heard of people who search primes with GMP at sizes that take days to test. But if you have already found a prp with PrimeForm/GW then it can make sense to check it with GMP.