Using PARI/GP for Cryptography

Here are some notes on the features of Pari/GP that I have found demonstrated in cryptography class. Don’t forget that the entire manual and a tutorial are available on-line in pdf format.
Built-in functions

Most of these commands are documented on pages 46-54 and 62-72 of the user’s guide.

add, subtract, multiply a and b a+b, a-b, a*b

integer quotient when a is divided by b a\b

integer remainder when a is divided by b (i.e. a mod b) a%b

a raised to the power b (see powermod below) a^b

assign a the value b a=b

compare a to b ab, a<=b, a!=b a==b

a `and' b, a `or' b, `not' a a &&b, a||b, !a

convert a to an element of Zn Mod(a,n)

convert an element x of Zn to an integer (see note) lift(x)

binary expansion of a binary(a)

nth bit of a bittest(a,n)

random integer between 0 and n-1 random(n)

highest power of p dividing a valuation(a,p)

greatest common divisor of a and b gcd(a,b) and bezout(a,b)

chinese remainder theorem applied to x and y (note) chinese(x,y)

φ(n) eulerphi(n)

factor the integer a factorint(a)

is p a prime integer? isprime(p)

first prime larger or smaller than a nextprime(a), prevprime(a)

nth prime number prime(n)

discrete log of x to the base g (note) znlog(x,g)

multiplicative order of x in Zn znorder(x)

find a primitive root modulo p znprimroot(p)

Legendre symbol of a over b kronecker(a,b)

define an elliptic curve E E=ellinit([0,0,0,a,b])

add/subtract z and w on elliptic curve E elladd(E,z,w) ellsub(E,z,w)

multiply z by k on elliptic curve E ellpow(E,z,k)

quit gp \q or quit

Other useful devices

Use ? to get help. For example ?bezout will give you information on the bezout function.
Use \l to start and stop a log file of your session.
Use # to turn on/off a timer. Use ## to find out the time of the last computation.
/* comments */
The sequence (1/a)%n will give the inverse of the integer a modulo n (assuming a and n are relatively prime).
you can define a powermod function with the command powermod(x,k,m)=lift(Mod(x,m)^k)
For some functions, the parameters (I've written them as x,y,g) need to be of the form Mod(a,n) since they are considered to be members of Zn.
There is a description of programming tools (loops, if statements, etc.) on pages 137-143 of the user's guide.

Advertisement