MathUtilsPollardRhoFactor Method

public static BigInteger[] PollardRhoFactor(
	BigInteger n,
	Action<RhoCallbackReason, int, BigInteger> rhoCallback
)

Parameters

n  BigInteger

The number to factor.

rhoCallback  ActionRhoCallbackReason, Int32, BigInteger

A callback delegate that calling applications can use to trace factoring progress. Null for no callbacks.

Return Value

Timing experiments on random N-digit composite numbers each having a pair of approximately equally sized factors shows that it takes about 3 seconds to factor a 25 digit number. The factoring time then roughly doubles for each digit added to the length of the number. So by 27 digits the time is around 12 seconds, by 30 digits it's around 80 seconds, by 34 digits it's around 830 seconds and thereafter the algorithm becomes impractical to use. These timings were made using the worst case scenario where there were two large similar size factors. Randomly entered 40 digit numbers can normally be factored in seconds, so long as there aren't many very large factors which make the algorithm struggle. This behaviour of the Pollard Rho algorithm is expected and is explained in many articles.

The following extract is from the end of test run that took just over an hour to complete:

832300000 5681967607180583256837584269544797833514
832400000 896252119279863117827247259667254144209
832500000 9015194283788784414057474364339407009366
Rho found............ 944979853807853701 (832568664)
Probable prime....... 10026803449983859488613
[47] 78926398267892678917263112121219786139987689763 = 3 × 3 × 3 × 53 × 5821 × 944979853807853701 × 10026803449983859488613

Reference