Carmichael Function λ(n): Definition, Properties and Example

Η συνάρτηση Carmichael λ(n)

Η λ(n) (συνάρτηση Carmichael ή ελάχιστος καθολικός εκθέτης) είναι ο εκθέτης της πολλαπλασιαστικής ομάδας (ℤ/nℤ)^× και ικανοποιεί πάντοτε λ(n) ∣ φ(n).

Ορισμός

Η λ(n) είναι ο μικρότερος θετικός ακέραιος m τέτοιος ώστε για κάθε a με gcd(a,n)=1 να ισχύει:

a^m ≡ 1 (mod n)

Ισοδύναμα, m = exp((ℤ/nℤ)^×).

Υπολογισμός

Αν n = ∏ p_i^α_i, τότε:

λ(n) = lcm( λ(p₁^α₁), λ(p₂^α₂), … )

με:

λ(p^α) =

• p^α−1(p−1), αν p είναι περιττός πρώτος
• 1, αν p = 2 και α = 1
• 2, αν p = 2 και α = 2
• 2^α−2, αν p = 2 και α ≥ 3

Ιδιότητες & Χρήσεις

(Θεώρημα Carmichael) Για κάθε a με gcd(a,n)=1 ισχύει:

a^λ(n) ≡ 1 (mod n)

Συνήθως λ(n) ≤ φ(n), με αυστηρή ανισότητα για πολλά n.

Εφαρμογές: μείωση εκθετών σε υπολογισμούς mod n, δοκιμές πρωτότητας, κρυπτογραφία (RSA).

Παράδειγμα

Υπολόγισε: 2009²⁰⁰⁹ (mod 1000)

1000 = 2³ · 5³
λ(2³) = 2
λ(5³) = 5²·4 = 100

Άρα: λ(1000) = lcm(2,100) = 100

2009 ≡ 9 (mod 1000) και gcd(9,1000)=1.

Επομένως:

9²⁰⁰⁹ ≡ 9^{2009 mod 100} = 9⁹ (mod 1000)

Υπολογίζουμε: 9⁹ ≡ 489 (mod 1000)

Τελικό αποτέλεσμα: 2009²⁰⁰⁹ ≡ 489 (mod 1000)

The Carmichael Function λ(n)

The Carmichael function λ(n) is the exponent of the multiplicative group (ℤ/nℤ)^× and always satisfies λ(n) | φ(n).

Definition

λ(n) is the smallest positive integer m such that for every a with gcd(a,n)=1:

a^m ≡ 1 (mod n)

Equivalently, m = exp((ℤ/nℤ)^×).

Computation

If n = ∏ p_i^α_i, then:

λ(n) = lcm( λ(p₁^α₁), λ(p₂^α₂), … )

• p^α−1(p−1), for odd primes p
• 1, for p = 2, α = 1
• 2, for p = 2, α = 2
• 2^α−2, for p = 2, α ≥ 3

Properties & Uses

(Carmichael’s theorem) For every a coprime to n:

a^λ(n) ≡ 1 (mod n)

Usually λ(n) ≤ φ(n), with strict inequality for many integers n.

Applications: exponent reduction in modular arithmetic, primality testing, cryptography.

Example

Compute: 2009²⁰⁰⁹ (mod 1000)

λ(1000) = 100, and 2009 ≡ 9 (mod 1000).

9²⁰⁰⁹ ≡ 9⁹ (mod 1000)

Thus: 9⁹ ≡ 489 (mod 1000)

Final result: 2009²⁰⁰⁹ ≡ 489 (mod 1000)