## RCM3720 Cryptography, Network and Computer Security

### Laboratory Class 3: Number Theory

• Check out the commands gcd and factor, and test them on different numbers, small and large.
• Axiom provides a few useful commands for taking apart the factors of an object:
• n:=5040
• f:=factor(n)
• numf:=numberOfFactors(f)
• fs:=[nthFactor(f,i) for i in 1..numf]
• es:=[nthExponent(f,i) for i in 1..numf]
• reduce(*,[fs.i^es.i for i in 1..numf])
• The last command simply multiplies all the factors to their powers.
• Check out the commands prime?, nextPrime and prevPrime.
• To compute the i-th prime, we can construct a stream (an infinite list) in Axiom:
• primes:Stream Integer:=[i for i in 2.. | prime? i]
• Now we can find, for example, the 100-th prime, and the 2500-th prime:
• primes.100
• primes.2500
• Create random 10 digit primes:
• p := nextPrime(random(10^10))
• q := nextPrime(random(10^10))
• Now multiply them and factor the product. How long did it take?
• Try the same thing with 12 digit primes and 15 digit primes.
• The extended Euclidean algorithm is implemented by the command extendedEuclidean. Here's how to use it:
• a:=1149
• b:=3137
• g:=extendedEuclidean(a,b)
• s:=g.coef1
• t:=g.coef2
• and now test them:
• s*a+t*b
• Try this on a few other numbers.
• Axiom uses the command positiveRemainder instead of mod command, so let's define mod to be a renaming of the positiveRemainder function:
• mod ==> positiveRemainder
• Now the commands addmod, submod, mulmod, and invmod can be used to perform modular arithmetic. Here's a few examples; first a simple modulus calculation:
• -10 mod 3
• Addition, subtraction and multiplication mod 14:
• submod(17,23,14)
• mulmod(13,27,14)
• Powers and inverses:
• powmod(19,237,14)
• invmod(11,14)
• Find out what happens if you try to take an inverse of a number not relatively prime to the modulus:
• invmod(12,14)
• Try these command with a few other numbers, and test out the examples in the notes.
• The second method, which can be more powerful, is to treat all numbers as elements of the residue values 0 to n-1. This can be done with the IntegerMod construction, or its abbreviation ZMOD. Here's a few examples:
• a:=11::ZMOD 14
• This declares the variable a to be a member of the residue class modulo 14. Now all arithmetic including a will be reduced to this same class of values:
• a+25
• a*39
• a^537
• Inversion can be done with the recip command:
• recip(a)
• We don't have to define a variable first. All the above commands could be equivalently written as:
• (11::ZMOD 14)+25
• 11::ZMOD 14*39
• 11::ZMOD 14^537
• recip(11::ZMOD 14)
• If the modulus is a prime, then division (by non-zero values) is also possible. Axiom provides the alternative construction PrimeField or more simply PF. For example:
• a:=7::PF 11
• All the above arithmetic operations of addition, subtraction, multiplication and powers work, but now we also have inversion:
• 1/a
• Using any of the methods you like, test out Fermat's theorem for a large prime p and an integer a.
• Euler's totient function is implemented with eulerPhi. Choose a large integer n, a random a with gcd(a,n)=1 , and test Euler's theorem