Minimal Universal Exponent

Last updated 2019-05-19SourceLinknumber theoryjavascript

This was a project for a number theory course: MATH 4150 at Georgia Tech. The goal was to compute the minimal universal exponent for a number, also known as the Carmichael function.

The minimal universal exponent of a positive integer nn is the smallest positive integer mm such that:

am1(modn)aZn+wheregcd(a,n)=1a^m \equiv 1 \pmod n \quad\forall a \in \Z_n^+ \quad\textrm{where}\quad \textrm{gcd}(a, n) = 1

This Carmichael function, we’ll refer to it as λ(n)=m\lambda(n) = m, is instrumental to the generation of RSA keys.

In order to compute the function, we have to break down nn to it’s prime factors. Then by the Chinese Remainder Theorem, we can compute the minimal universal exponent using the least common multiple of the prime factors’ exponents.

λ(n)=lcm(λ(p1r1,,λ(pkrk))wheren=i=1kpiri\lambda(n) = \textrm{lcm}(\lambda(p_1^{r_1}, \mathellipsis, \lambda(p_k^{r_k})) \quad\textrm{where}\quad n = \prod_{i=1}^kp_i^{r_i}

Then for any prime factor λ(piri)\lambda(p_i^{r_i}) corresponds with Euler’s totient for that prime factor.

This means that the majority of the work by far is in factoring nn since computing the lcm and Euler’s totient for the prime factors is trivial. This is evident in the Chrome DevTools profile:

Chrome DevTools profile

For reference, here is the function for computing the minimal universal exponent:

function min_unv_exp(num) {
  /* Returns a number representing the minimal universal exponent
   * of a positive integer num */

  var e = 1; /* This will be the returned exponent, note: needs to be
    one for the first lcm to work */

  /* Iterate through prime factors, computing lcm of each totient */
  prime_factorization(num).forEach(function(factor) {
    if (factor.p === 2) {
      if (factor.e == 2) {
        e = lcm(e, 2);
      } else if (factor.e > 2) {
        e = lcm(e, Math.pow(2, factor.e - 2));
      }
    } else {
      e = lcm(e, Math.pow(factor.p, factor.e - 1) * (factor.p - 1));
    }
  });

  return e;
}

Digging into the prime factorization function the fastest way I could implement it was using a accumulator approach:

function prime_factorization(n) {
  /* Returns an array of prime factors (in least sorted order)
   * where each factor is an object of the form
   * {'p': 7, 'e': 4}
   * where p is the prime base and e is the exponent for p in the factorization
   */
  var factors = [];
  for (var p = 2; p <= n; p++) {
    var e = 0;
    while (n % p == 0) {
      n = n / p;
      e++;
    }
    if (e > 0) {
      factors.push({ p: p, e: e });
    }
  }
  return factors;
}

This relies on the observation that dividing nn by its the smallest prime factor p1r1p_1^{r_1} the smallest number greater than p1p_1 that divides n/p1r1n/p_1^{r_1} is necessarily a prime factor of nn.

A quick proof for this follows from contradiction. Let p1r1p_1^{r_1} be the factor of nn such that p1p_1 is minimal and r1r_1 is maximal.

Now assume q>p1q > p_1 is the next smallest divisor of nn and qq is not prime.

Since qq is composite, there must exist a prime factor ϕ<q\phi < q.

ϕqϕn\phi|q \,\rarr\, \phi|n

Since ϕnϕ>p1\phi|n \,\rarr\, \phi > p_1 otherwise p1p_1 would not be the smallest prime factor of n.

However, since q>ϕ>p1q > \phi > p_1 and ϕn\phi|n that means qq is not the next smallest divisor of nn unless q=ϕq=\phi in which case qq is prime breaking our assumption that qq is composite. ∎