analyze-prime-numbers

Files (1)

• SKILL.md

SKILL.md (first lines)

# Analyze Prime Numbers

Analyze prime numbers by selecting and applying the appropriate algorithm for the task at hand: primality testing, integer factorization, or prime distribution analysis. Verify results computationally and relate findings to the Prime Number Theorem.

## When to Use

- Determining whether a given integer is prime or composite
- Finding the complete prime factorization of an integer
- Counting or listing primes up to a given bound
- Verifying the Prime Number Theorem approximation for a specific range
- Investigating properties of primes in a number-theoretic proof or computation

## Inputs

- **Required**: The integer(s) to analyze, or a bound for distribution analysis
- **Required**: Task type -- one of: primality test, factorization, or distribution analysis
- **Optional**: Preferred algorithm (trial division, Miller-Rabin, Sieve of Eratosthenes, Pollard's rho)
- **Optional**: Whether to produce a formal proof of primality or a computational verdict
- **Optional**: Output format (factor tree, prime list, count, table)

## Procedure

### Step 1: Determine the Task Type

Classify the request into one of three categories and select the appropriate algorithmic path.

1. **Primality test**: Given a single integer n, determine whether n is prime.
2. **Factorization**: Given a composite integer n, find its complete prime factorization.
3. **Distribution analysis**: Given a bound N, analyze the primes up to N (count, list, gaps, density).

Record the task type and the input value(s).

**Got:** A clear classification with the input values recorded.

**If fail:** If the input is ambiguous (e.g., "analyze 60"), ask the user to clarify whether they want a primality test, factorization, or distribution analysis. Default to factorization for composite numbers and primality confirmation for suspected primes.

### Step 2: Apply Primality Testing (if task = primality)

Test whether n is prime using an algorithm matched to the size of n.

1. **Handle trivial cases**: n < 2 is not prime. n = 2 or n = 3 is prime. If n is even and n > 2, it is composite.

2. **Small n (n < 10^6)**: Use trial division.
   - Test divisibility by all primes p up to floor(sqrt(n)).
   - Optimization: test 2, then odd numbers 3, 5, 7, ... or use a 6k +/- 1 wheel.
   - If no divisor found, n is prime.

3. **Large n (n >= 10^6)**: Use Miller-Rabin probabilistic test.
   - Write n - 1 = 2^s * d where d is odd.
   - For each witness a in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}:
     - Compute x = a^d mod n.
     - If x = 1 or x = n - 1, this witness passes.
     - Otherwise, square x up to s - 1 times. If x ever equals n - 1, pass.
     - If no pass, n is composite (a is a witness).
   - For n < 3.317 * 10^24, the witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} give a deterministic result.

4. **Record the verdict**: prime or composite, with the witness or certificate.

**Small primes reference (first 25):**

| Index | Prime | Index | Prime | Index | Prime |
|---|---|---|---|---|---|
| 1     | 2     | 10    | 29    | 19    | 67    |
| 2     | 3     | 11    | 31    | 20    | 71    |
| 3     | 5     | 12    | 37    | 21    | 73    |
| 4     | 7     | 13    | 41    | 22    | 79    |
| 5     | 11    | 14    | 43    | 23    | 83    |
| 6     | 13    | 15    | 47    | 24    | 89    |
| 7     | 17    | 16    | 53    | 25    | 97    |
| 8     | 19    | 17    | 59    |       |       |
| 9     | 23    | 18    | 61    |       |       |

**Got:** A definitive answer (prime or composite) with the algorithm used and any witnesses or divisors found.

**If fail:** If Miller-Rabin reports "probably prime" but certainty is required, escalate to a deterministic test (e.g., AKS or ECPP). For trial division, if computation is too slow, switch to Miller-Rabin.

### Step 3: Apply Factorization (if task = factorization)

Factor n completely into its prime power decomposition.

1. **Extract small factors by trial division**:
   - Divide out 2 as many times as possible, recording the exponent.
   - Divide out odd primes 3, 5, 7, 11, ... up to a cutoff (e.g., 10^4 or sqrt(n) if n is small).
   - After each division, update n to the remaining cofactor.

2. **If cofactor > 1 and cofactor < 10^12**: Continue trial division up to sqrt(cofactor).

3. **If cofactor > 1 and cofactor >= 10^12**: Apply Pollard's rho algorithm.
   - Choose f(x) = x^2 + c (mod n) with random c.
   - Use Floyd's cycle detection: x = f(x), y = f(f(y)).
   - Compute d = gcd(|x - y|, n) at each step.
   - If 1 < d < n, d is a non-trivial factor. Recurse on d and n/d.
   - If d = n, retry with a different c.

4. **Verify**: Multiply all found prime factors (with exponents) and confirm the product equals the original n. Test each factor for primality.

5. **Present the result** in standard form: n = p1^a1 * p2^a2 * ... * pk^ak with p1 < p2 < ... < pk.

**Algorithm complexity notes:**

| Algorithm       | Complexity                  | Best for              |
|---|---|---|
| Trial division  | O(sqrt(n))                  | n < 10^12             |
| Pollard's rho   | O(n^{1/4}) expected         | n up to ~10^18        |
| Quadratic sieve | L(n)^{1+o(1)}              | n up to ~10^50        |
| GNFS            | L(n)^{(64/9)^{1/3}+o(1)}  | n > 10^50             |

**Got:** A complete prime factorization in canonical form, verified by multiplication.

**If fail:** If Pollard's rho fails to find a factor after many iterations (cycle detected without a non-trivial gcd), try different values of c (at least 5 attempts). If all fail, the cofactor may be prime -- confirm with a primality test.

### Step 4: Apply Distribution Analysis (if task = distribution)

Analyze the distribution of primes up to a given bound N.

1. **Generate primes using the Sieve of Eratosthenes**:
   - Create a boolean array of size N + 1, initialized to true.
   - Set indices 0 and 1 to false (not prime).
   - For each p from 2 to floor(sqrt(N)):

From pjt222/agent-almanac, MIT.

More from pjt222/agent-almanac