diff --git a/configure.ac b/configure.ac
index 57ea99d..e923762 100644
--- a/configure.ac
+++ b/configure.ac
@@ -73,8 +73,18 @@ AM_CONDITIONAL([BUILD_PDF], [test "$DBLATEX" == "found"])
 PKG_CHECK_MODULES([LIBMNL], [libmnl >= 1.0.3])
 PKG_CHECK_MODULES([LIBNFTNL], [libnftnl >= 1.0.2])
 
-AC_CHECK_LIB([gmp], [__gmpz_init], ,
-	     AC_MSG_ERROR([No suitable version of libgmp found]))
+AC_ARG_WITH([libgmp], [AS_HELP_STRING([--without-libgmp],
+            [Disable libgmp support (use builtin mini-gmp)])], [],
+            [with_libgmp=yes])
+AS_IF([test "x$with_libgmp" != xno], [
+AC_CHECK_LIB([gmp],[__gmpz_init], , AC_MSG_ERROR([No suitable version of libgmp found]))
+])
+AM_CONDITIONAL([BUILD_MINIGMP], [test "x$with_libgmp" == xno])
+
+
+AS_IF([test "x$with_libgmp" != xyes -a "x$with_debug" != xno], [
+AC_MSG_ERROR([--without-libgmp MUST be used with --disable-debug])
+])
 
 AC_ARG_WITH([cli], [AS_HELP_STRING([--without-cli],
             [disable interactive CLI (libreadline support)])],
@@ -130,4 +140,5 @@ AC_OUTPUT
 echo "
 nft configuration:
   cli support:			${with_cli}
-  enable debugging:		${with_debug}"
+  enable debugging:		${with_debug}
+  use shared libgmp:		${with_libgmp}"
diff --git a/include/expression.h b/include/expression.h
index 4b96879..7477c3e 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -2,7 +2,7 @@
 #define NFTABLES_EXPRESSION_H
 
 #include <stdbool.h>
-#include <gmp.h>
+#include <gmputil.h>
 #include <linux/netfilter/nf_tables.h>
 
 #include <nftables.h>
diff --git a/include/gmputil.h b/include/gmputil.h
index 63eb0ba..1bf696a 100644
--- a/include/gmputil.h
+++ b/include/gmputil.h
@@ -1,7 +1,17 @@
 #ifndef NFTABLES_GMPUTIL_H
 #define NFTABLES_GMPUTIL_H
 
+#include <config.h>
+
+#ifdef HAVE_LIBGMP
 #include <gmp.h>
+#else
+#include <mini-gmp.h>
+/* mini-gmp doesn't come with gmp_printf, so we use our own minimal variant */
+extern int mpz_printf(const char *format, const mpz_t value);
+#define gmp_printf mpz_printf
+#endif
+
 #include <asm/byteorder.h>
 
 enum mpz_word_order {
diff --git a/include/utils.h b/include/utils.h
index 45cb5a7..b814568 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -9,14 +9,14 @@
 #include <unistd.h>
 #include <assert.h>
 #include <list.h>
-#include <gmp.h>
+#include <gmputil.h>
 
 #define BITS_PER_BYTE	8
 
 #ifdef DEBUG
 #define pr_debug(fmt, arg...) gmp_printf(fmt, ##arg)
 #else
-#define pr_debug(fmt, arg...) ({ if (false) gmp_printf(fmt, ##arg); 0; })
+#define pr_debug(fmt, arg...) ({ if (false) {}; 0; })
 #endif
 
 #define __fmtstring(x, y)	__attribute__((format(printf, x, y)))
diff --git a/src/Makefile.am b/src/Makefile.am
index 378424d..099052a 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -51,4 +51,8 @@ if BUILD_CLI
 nft_SOURCES +=	cli.c
 endif
 
+if BUILD_MINIGMP
+nft_SOURCES +=	mini-gmp.c
+endif
+
 nft_LDADD	= ${LIBMNL_LIBS} ${LIBNFTNL_LIBS}
diff --git a/src/gmputil.c b/src/gmputil.c
index cb46445..b965fb3 100644
--- a/src/gmputil.c
+++ b/src/gmputil.c
@@ -14,11 +14,9 @@
 #include <stdio.h>
 #include <unistd.h>
 #include <string.h>
-#include <gmp.h>
 
 #include <nftables.h>
 #include <datatype.h>
-#include <gmputil.h>
 #include <utils.h>
 
 void mpz_bitmask(mpz_t rop, unsigned int width)
@@ -148,6 +146,61 @@ void mpz_switch_byteorder(mpz_t rop, unsigned int len)
 	mpz_import_data(rop, data, BYTEORDER_HOST_ENDIAN, len);
 }
 
+#ifndef HAVE_LIBGMP
+/* mini-gmp doesn't have a gmp_printf so we use our own minimal
+ * variant here which is able to format a single mpz_t */
+int mpz_printf(const char *f, const mpz_t value)
+{
+	int n = 0;
+	while (*f) {
+		if (*f != '%') {
+			if (fputc(*f, stdout) != *f)
+				return -1;
+
+			++n;
+		} else {
+			unsigned long prec = 0;
+			int base;
+			size_t len;
+			char *str;
+			bool ok;
+
+			if (*++f == '.')
+				prec = strtoul(++f, (char**)&f, 10);
+
+			if (*f++ != 'Z')
+				return -1;
+
+			if (*f == 'u')
+				base = 10;
+			else if (*f == 'x')
+				base = 16;
+			else
+				return -1;
+
+			len = mpz_sizeinbase(value, base);
+			while (prec-- > len) {
+				if (fputc('0', stdout) != '0')
+					return -1;
+
+				++n;
+			}
+
+			str = mpz_get_str(NULL, base, value);
+			ok = str && fwrite(str, 1, len, stdout) == len;
+			free(str);
+
+			if (!ok)
+				return -1;
+
+			n += len;
+		}
+		++f;
+	}
+	return n;
+}
+#endif
+
 static void *gmp_xrealloc(void *ptr, size_t old_size, size_t new_size)
 {
 	return xrealloc(ptr, new_size);
