@alesia, c'e' stato un gran cianciare su un argomento decisamente interessante e complesso.
Allora, riassumiamo: librerie per la gestione di numeri di dimensione arbitraria ce ne sono diverse. La piu' famosa e' GMP (GNU MultiPrecision Library), ed immagino sia esattamente quella che hai trovato.
https://gmplib.org
Piu' interessanti sono i CAS (Computer Algebra System) che permettono di poter lavorare direttamente con tali numeri, ed implementano gia' gli algoritmi di fattorizzazione, test di primalita', ed ovviamente le operazioni matematiche.
Il piu' bello, a mio avviso, e' Mathematica, ma e' a pagamento (non costa molto). Ci sono molte alternative gratuite, ma forse il migliore e' Maxima.
http://maxima.sourceforge.net
Le operazioni di somma, sottrazione si implementano esattamente come si farebbe a mano.
Per la moltiplicazione e la divisione ci sono diversi metodi, i piu' banali dei quali e' esattamente quello che si usa quando si fanno le operazioni con carta e matita.
Gli algoritmi li trovi anche su Wikipedia.
Come libri: Handbook of Applied Cryptography (trovi i PDF gratuiti) e The Art of Computer Programming Volume 2 (per palati fini )
Ovviamente ce ne sono altri, basta cercare con Google.
https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
http://cacr.uwaterloo.ca/hac
Il test di primalita' e' un problema DIFFICILE: infatti sono stati trovati algoritmi STATISTICI che permettono di supporre che un numero sia primo a meno di una probabilita' imposta come parametro (1/100, 1/000, 1/100000000, ecc). NON ESISTE UN ALGORITMO sicuro al 100%, se non facendo tutti i test possibili (il che potrebbe richiedere tempi dell'ordine dei miliardi di anni anche mettendo in parallelo TUTTI i computer del mondo )
La fattorizzazione e' un problema DIFFICILE: non esistono algoritmi in grado di fattorizzare numeri , se non per tentativi. Comunque, numeri di 200 cifre (decimali, circa 650 cifre binarie) sono ancora trattabili.
Ben piu' complicato e' analizzare numeri di 1024/2048 bit: infatti i vari HTTPS, FTPS, SSH, SSL, ecc si basano su numeri di 2048 bit.
NON ESISTE un algoritmo per generare numeri primi: i primi SI CERCANO.
Il sistema e' banale: si inizia con un numero dispari, si usa un test di primalita', se non lo passa, si aggiunge 2 e si ricomincia. Ci sono sistemi piu' efficienti, ma non si va molto piu' lontano da questo banale sistema. Quello che fanno e' sfruttare tutta una serie di regole per usare passi piu' ampi di 2.
OVVIAMENTE i due problemi sono strettamente correlati: se si dovesse trovare un test di primalita' sicuro al 100% ed efficiente, si potrebbe anche trovare un algoritmo efficiente per la fattorizzazione.
https://en.wikipedia.org/wiki/Primality_tes
https://it.wikipedia.org/wiki/Fattorizzazion
https://en.wikipedia.org/wiki/Mersenne_prim