From 55fcb39a1209898ec43694f7e25ffb4572b0c4d1 Mon Sep 17 00:00:00 2001
From: Alexei Sheplyakov <varg@theor.jinr.ru>
Date: Tue, 14 Oct 2008 10:37:42 +0400
Subject: [PATCH] mod_gcd: naive hack to chose a 'good' prime (to speed up gcd
 computation).

---
 ginac/polynomial/mod_gcd.cpp | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/ginac/polynomial/mod_gcd.cpp b/ginac/polynomial/mod_gcd.cpp
index 8aa84808..82d5f427 100644
--- a/ginac/polynomial/mod_gcd.cpp
+++ b/ginac/polynomial/mod_gcd.cpp
@@ -104,8 +104,18 @@ void mod_gcd(upoly& result, upoly A, upoly B)
 	ring_t q(0);
 	upoly H;
 
-	ring_t p(2);
+	int count = 0;
+	const ring_t p_threshold = ring_t(1) << (8*sizeof(void *));
+	ring_t p = isqrt(std::min(max_coeff(A), max_coeff(B)));
 	while (true) {
+		if (count >= 8) {
+			count = 0;
+			if (p < p_threshold)
+				p <<= 1;
+			else
+				p = p + (p >> 4);
+		} else 
+			++count;
 		find_next_prime(p, g);
 
 		// Map the polynomials onto Z/p[x]
-- 
2.49.0