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:
- 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:
- 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:
- Addition, subtraction and multiplication mod 14:
- addmod(10,13,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:
- 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:
- 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:
- Inversion can be done with the recip command:
- 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:
- All the above arithmetic operations of addition, subtraction,
multiplication and powers work, but now we also have inversion:
- 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