# 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), precprime(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.
• 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.