Click or drag to resize

MathUtils.FactorNaive Method

A simple naive factoring method that uses division by the sequence 2,3,6n±1 up to the square root

Namespace: Orthogonal.Common.Basic
Assembly: Orthogonal.Common.Basic (in Orthogonal.Common.Basic.dll) Version: 2025-03-15 14:42 GMT+11
Syntax
C#
Copy
public static IEnumerable<BigInteger> FactorNaive(
	BigInteger n
)

Parameters

n  BigInteger
The number to factor.

Return Value

IEnumerable<BigInteger>
An enumerable sequence of factors.
Remarks

This code was created as an experiment in early 2021 while playing around with Carmichael numbers and Fermat's Little Theorem. I was so shocked by the high-speed performance of the BigInteger class that I decided it was worth saving this code as a reference.

As the Blog Post explains, the naïve factoring loop works surprisingly fast up until about 1018 after which it hits the exponential wall and quickly becomes impractical.

See Also