如何将基于φ(n)与因式分解的O(n)原根算法优化至≤O(√n)？

Great question—let's break down why your current approach is slow and how to fix it. The core bottleneck in your existing O(n) algorithm is iterating over every element in ℤₙ*, which becomes completely infeasible as n grows large. We can drastically cut this down by leveraging number theory properties to avoid brute-forcing all candidates.

Key Observations to Guide Optimization #

First, a quick sanity check: primitive roots only exist for n ∈ {1, 2, 4, pᵏ, 2pᵏ} where p is an odd prime and k ≥ 1. Start by verifying this condition with your factorise(n) function—if n doesn't fit this form, you can immediately return that no primitive root exists, saving unnecessary computation.

Step-by-Step Optimized Workflow #

Here's the revised approach, with all steps staying within O(√n) time:

1. Validate Primitive Root Existence

   • Use your factorise(n) to decompose n into prime factors. Check if n matches the valid forms listed above. If not, exit early.

2. Compute φ(n)

   • Run your existing O(√n) Euler's totient function algorithm. This is straightforward since you already have this tool ready.

3. Factorize φ(n) into Distinct Prime Factors

   • Use factorise(φ(n)) to get the unique prime factors p₁, p₂, ..., pₖ of φ(n). Since φ(n) ≤ n-1, √φ(n) ≤ √n, so this step remains O(√n).

4. Find a Valid Candidate (No More Full Traversal!)

   • Instead of checking every element in ℤₙ*, test small candidates sequentially (starting from 2) or random candidates until you find one that meets the primitive root condition:

     For all i from 1 to k, compute pow(m, φ(n)/p_i, n) using fast exponentiation. If none of these results are congruent to 1 mod n, then m is a primitive root of n.

Why This Works (and Is Fast) #

• Density of Primitive Roots: In ℤₙ*, the number of primitive roots is φ(φ(n)). The density φ(φ(n))/φ(n) is non-trivial—for primes p, this is φ(p-1)/(p-1), which means you'll usually find a valid candidate within a handful of tries (often within the first 5-10 numbers).
• Fast Exponentiation: Each pow(m, e, n) uses binary exponentiation, which runs in O(log e) time. Since e = φ(n)/p_i ≤ φ(n) ≤ n, log e is O(log n). With k (number of distinct primes of φ(n)) being at most O(log n), each candidate check takes O((log n)²) time—negligible compared to O(n).

Additional Optimizations for Specific Cases #

• Prime Powers: If n = pᵏ (p odd prime), first find a primitive root g modulo p. Then:
  • If pow(g, p, p²) ≠ g mod p², g is also a primitive root modulo pᵏ.
  • Otherwise, g + p is a primitive root modulo pᵏ.
    This avoids testing candidates directly on the larger modulus pᵏ, saving even more time.
• Even Prime Powers: For n = 2pᵏ, if g is a primitive root modulo pᵏ, then g is a primitive root modulo 2pᵏ if g is odd; otherwise, g + pᵏ is.

Complexity Breakdown #

Let's confirm the total time stays ≤ O(√n):

• factorise(n): O(√n)
• φ(n): O(√n)
• factorise(φ(n)): O(√φ(n)) ≤ O(√n)
• Candidate checks: O((log n)²) per candidate, with a constant number of candidates on average.

Adding these up, the total time is dominated by the O(√n) steps, fully meeting your requirement.

内容的提问来源于stack exchange，提问作者unseen_rider