curl crashes due to "curl: symbol lookup error: /usr/lib/x86_64-linux-gnu/libhogweed.so.4: undefined symbol: __gmpn_cnd_add_n"

For example `curl --insecure -O https://gforge.inria.fr/frs/download.php/file/33524/CGAL-4.4.tar.bz2` crashes 100 % of times with this error message and return code 127.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: curl 7.47.0-1ubuntu2.1
Uname: Linux 4.7.2-040702-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
CurrentDesktop: Unity
Date: Thu Sep 8 20:00:27 2016
InstallationDate: Installed on 2015-12-12 (271 days ago)
InstallationMedia: Ubuntu 15.10 "Wily Werewolf" - Release amd64 (20151021)
SourcePackage: curl
UpgradeStatus: Upgraded to xenial on 2016-03-14 (178 days ago)