JuliaMath / JuliaMath/Primes.jl

factor with method selection

Open
#175 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
Julia
Stars
108
Forks
34
PR merge metrics
No merged PRs in 30d

Description

Hello,

Currently, `factor()` uses a hardcoded algorithm chain: trial division up to 2^32, then `pollardfactor()`. With ECM and eventually MPQS being added, users would benefit from:

1. Explicitly choosing a factorization algorithm
2. Tuning algorithm parameters (e.g., ECM smoothness bound)
3. A clean extension point for future algorithms

Proposed API

Following SciML conventions (cf. `solve(prob, alg`) in DifferentialEquations.jl ...):
```julia
abstract type FactorizationMethod end
struct TrialDivision <: FactorizationMethod end
struct PollardRho <: FactorizationMethod end
struct ECM <: FactorizationMethod
B1::Int
num_curves::Int
end
struct Auto <: FactorizationMethod end

# Keyword API (backwards compatible)
factor(n; method=Auto())

# Positional dispatch (Julian style)
factor(n, ::TrialDivision)
factor(n, ::PollardRho)
factor(n, ::ECM)
factor(n, ::Auto) # current polyalgorithm heuristic
```

`Auto()` would encode the current behavior (trial division → Pollard rho) and grow to include ECM/MPQS size-based heuristics.

Backward compatibility

- `factor(n)` continues to work unchanged (defaults to Auto())
- `factor(ContainerType, n)` unaffected
- `eachfactor(n)` would also accept a method keyword

Considerations

- Should strategy types be exported? Probably yes for discoverability.
- Should eachfactor support methods too, or only factor?
- Parameterless strategies (TrialDivision(), PollardRho()) could carry default tuning parameters later without breaking API.

Related:
- https://github.com/JuliaMath/Primes.jl/issues/159#issuecomment-2538065172

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.