//! Multiplicative-group structure — totient, Carmichael, order, primitive root.

use crate::number::{factorize, gcd, lcm, modpow};

/// Euler's totient `φ(n)`: the number of integers in `[1, n]` coprime to `n`.
/// `φ(0) = 0` (convention), `φ(1) = 1`. Computed from the prime factorization as
/// `n · ∏(1 − 1/p)`, dividing before multiplying so no intermediate exceeds `n`.
///
/// # Examples
///
/// ```
/// use coprime::number::totient;
///
/// assert_eq!(totient(1), 1);
/// assert_eq!(totient(12), 4); // the units 1, 5, 7, 11
/// assert_eq!(totient(13), 12); // p prime ⇒ φ(p) = p − 1
/// ```
#[must_use]
pub fn totient(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let mut result = n;
    for &(p, _) in factorize(n).as_slice() {
        result = result / p * (p - 1); // p | result, so the division is exact
    }
    result
}

/// The Carmichael function `λ(n)`: the exponent of the unit group `(Z/nZ)*` — the
/// least `m >= 1` with `a^m ≡ 1 (mod n)` for every `a` coprime to `n`. `λ(1) = 1`;
/// `None` for `n = 0` (no unit group). Since `λ(n) ≤ φ(n) ≤ n`, the `lcm` never
/// overflows for a valid factorization, so for every `n ≥ 1` the result is `Some`
/// — the `Option` only ever reports the (unreachable) `lcm` overflow, mirroring
/// [`lcm`]. Computed as the `lcm` of the per-prime-power values
/// `λ(p^e) = p^(e-1)(p-1)` for odd `p` (or `p = 2, e ≤ 2`), and `λ(2^e) = 2^(e-2)`
/// for `e ≥ 3`.
///
/// # Examples
///
/// ```
/// use coprime::number::carmichael;
///
/// assert_eq!(carmichael(1), Some(1));
/// assert_eq!(carmichael(8), Some(2)); // (Z/8)* = {1,3,5,7}, each squares to 1
/// assert_eq!(carmichael(15), Some(4)); // lcm(λ(3), λ(5)) = lcm(2, 4)
/// ```
#[must_use]
pub fn carmichael(n: u64) -> Option<u64> {
    if n == 0 {
        return None;
    }
    let mut acc = 1u64;
    for &(p, e) in factorize(n).as_slice() {
        let lam = if p == 2 && e >= 3 {
            1u64 << (e - 2) // λ(2^e) = 2^(e-2) for e >= 3
        } else {
            p.pow(e - 1) * (p - 1) // λ(p^e) = p^(e-1)(p-1); fits since it divides φ(n) ≤ n
        };
        acc = lcm(acc, lam)?;
    }
    Some(acc)
}

/// The multiplicative order of `a` modulo `m`: the least `k >= 1` with
/// `a^k ≡ 1 (mod m)`, or `None` when `a` is not a unit (`gcd(a, m) != 1`, which
/// includes `m <= 1`). The order divides `φ(m)`; it is found by starting at
/// `φ(m)` and dividing out each prime factor as far as `a^· ≡ 1` permits.
///
/// # Examples
///
/// ```
/// use coprime::number::order;
///
/// assert_eq!(order(2, 7), Some(3)); // 2³ = 8 ≡ 1 (mod 7)
/// assert_eq!(order(3, 7), Some(6)); // 3 is a primitive root mod 7
/// assert_eq!(order(0, 5), None); // 0 is not a unit
/// ```
#[must_use]
#[allow(clippy::many_single_char_names)] // a, m, n, t, q — canonical names
pub fn order(a: u64, m: u64) -> Option<u64> {
    if m <= 1 {
        return None;
    }
    let ar = a % m;
    if gcd(ar, m) != 1 {
        return None;
    }
    let n = totient(m);
    let mut t = n;
    for &(q, eq) in factorize(n).as_slice() {
        t /= q.pow(eq); // q^eq | n, so the division is exact
        while modpow(ar, t, m) != 1 {
            t *= q;
        }
    }
    Some(t)
}

/// A primitive root of `m` — a generator of the unit group `(Z/mZ)*` — as the
/// *least* such generator, or `None` when the group is not cyclic. By Gauss the
/// group is cyclic exactly for `m ∈ {1, 2, 4, p^k, 2·p^k}` with `p` an odd prime;
/// a unit `g` generates it iff `g^(φ(m)/q) ≢ 1 (mod m)` for every prime `q | φ(m)`.
///
/// # Examples
///
/// ```
/// use coprime::number::primitive_root;
///
/// assert_eq!(primitive_root(7), Some(3)); // 3 generates (Z/7)*
/// assert_eq!(primitive_root(25), Some(2));
/// assert_eq!(primitive_root(8), None); // (Z/8)* is not cyclic
/// ```
#[must_use]
pub fn primitive_root(m: u64) -> Option<u64> {
    match m {
        0 => return None,
        1 => return Some(0), // the trivial group {0}
        2 => return Some(1),
        4 => return Some(3),
        _ => {}
    }
    if !cyclic_odd_part(m) {
        return None;
    }
    let phi = totient(m);
    let qs = factorize(phi);
    for g in 2..m {
        if gcd(g, m) != 1 {
            continue;
        }
        if qs
            .as_slice()
            .iter()
            .all(|&(q, _)| modpow(g, phi / q, m) != 1)
        {
            return Some(g);
        }
    }
    None // unreachable: a cyclic group has a generator
}

/// Whether `m` (already decided for `0, 1, 2, 4`) is `p^k` or `2·p^k` for an odd
/// prime `p` — i.e. whether `(Z/mZ)*` is cyclic.
fn cyclic_odd_part(m: u64) -> bool {
    let mut x = m;
    if x.is_multiple_of(2) {
        x /= 2;
    }
    if x.is_multiple_of(2) {
        return false; // m divisible by 4 (and m != 4 here) ⇒ not cyclic
    }
    // x is odd; cyclic iff x is a single odd prime power.
    x > 1 && factorize(x).as_slice().len() == 1
}
