[vuptqpwg] Demonstration of RSA in Pari/GP

We demonstrate 16384-bit RSA below, slightly larger than the size (15360) recommended by NIST for the security level equivalent of 256-bit AES (symmetric) encryption.  Encryption (equivalently signature verification) was pretty fast (averaging 0.79 milliseconds (790 microseconds) over repeated trials).  Decryption, with its much larger exponent, is much slower, though still tolerable (0.76 seconds).

We generate p and q with precprime, obviously not random, because it is a compact and easy way to get a large prime number.  It also provides example timings of how long it might take to find a 8192-bit prime number.  The purpose \g5 is to catch if or when Pari/GP is trying to do a large futile factorization.  (Aside: it will try to do such a factorization when f is computed as f=eulerphi(n).  But this can be made to complete in 537 milliseconds by preceding it with addprimes(p).)  The most significant magic is the inversion of e modulo f, where f is not a prime.

GP/PARI CALCULATOR Version 2.7.5 (released)
amd64 running linux (x86-64/GMP-6.0.0 kernel) 64-bit version

? #
timer = 1 (on)
? s=2^8192
1090748135...
? p=precprime(s)
time = 34,720 ms.
1090748135...
? q=precprime(p-1)
time = 42,080 ms.
1090748135...
? p-s
-2439
? q-s
-5619
? n=p*q
1189731495...
? f=(p-1)*(q-1)
1189731495...
? \g5
debug = 5
? e=65537
65537
? gcd(e,f)
1
? d=lift(Mod(e,f)^(-1))
5478025787...
? lift(Mod(e,f)*Mod(d,f))
1
? c=Mod(10^40,n)^e
time = 4 ms.
Mod(621624...
? lift(c^d)
time = 829 ms.
10000000000000000000000000000000000000000
? x=0;for(i=1,10,x=x+Mod(random(n),n)^d)
time = 7,569 ms.
? x=0;for(i=1,10000,x=x+Mod(random(n),n)^e)
time = 7,901 ms.
? \q
$ cat /proc/cpuinfo
model name : Intel(R) Core(TM) i5-4690S CPU @ 3.20GHz