Implementation of cryptographic functions in Python. All the materials were sourced from "Systems and Networks" course in my school.
Subject-wide functions and other common facilities.
a.k.a. phi function
The phi function of a given integer n counts the positive integers up to n that a coprime with n.
Two coprime numbers only share 1 as a common factor.
Let's give an example: ๐(4) = ...
4 is factored as 1 x 2 x 2; the numbers from 1 to 4 (n) that are coprime with 4 (n) are 1 and 3.
[1, 2, 3, 4], hence ๐(4) = 2
- n is prime => ๐(n) = n - 1
- a, b are coprimes => ๐(a*b) = ๐(a)*๐(b)
- N = p1 * p2 with p1, p2 primes => ๐(N) = ๐(p1)*๐(p2)
= (p1-1)(p2-1)
- Note that prime numbers are also coprimes with every other number.
We offer a routine to compute Euler's totient for a given number.
The code is under cryptow/maths/totient.py