How to compile GnuTLS

I installed nettle-dev & nettle-bin and it works :)

The issue is that nettle won't build libhogweed unless, as you've observed, the dev headers for libgmp are present. Unfortunately, the docs and .configure --help and output from configure don't say anything about this.

Meanwhile, the gnuTLS docs don't explain this either (and as you notice, its configure output here is not very helpful). Although libgmp is listed as a pre-req, for some reason libhogweed is not (perhaps because it is assumed to be part of nettle). The reason for your configure error "cannot find -lgmp" is that libgmp isn't present, but libhogweed.so won't be there either, since it is a hidden optional part of nettle. If you then install libgmp-dev and just run configure for gnutls, you'll get the same "checking for libnettle... no". What this should say is "checking for libhogweed... no", but whoever is in charge of the conf script is too lazy to break that up (I guess a patch could be submitted).

In other words, you need to install libgmp-dev and then rebuild nettle before you build gnutls.