August 19, 2024
P34 - Calculate Euler's totient function phi(m)
Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.
Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
* (totient-phi 10)4
Find out what the value of phi(m) is if m is a prime number. Euler's totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).
lisp
;;; Euler's totient function phi(m) is defined as the number
;;; of positive integers r (1 <= r <= m) that are coprime to m.
(defun phi (m)
(if (< 0 m)
(phi-aux 1 m)
'undef
)
)
;;; Function phi-aux(k,m) is defined as the number
;;; of positive integers r (k <= r < m) that are coprime to m.
(defun phi-aux (k m)
(if (<= k m)
(+ (phi-aux (1+ k) m)
(if (coprime k m) 1 0)
)
0
)
)
Be first to comment