Sunday, May 08, 2011

[mnnfmzxq] Pollard's Rho in Haskell

A sloppy attempt (but works) on implementing Pollard's rho factorization method in Haskell, with multiple simultaneous polynomials.

Some composites that fail with x^2 + 1 : 16 21 22 25 32 44 62 64 88 95 124 125 169 176 185 248 289 299 341 352 475 485 496 682 703 704 901 925 992 1003

Some composites that fail with both x^2+1 and x^2+2: 16 32 1363 1681 2669 3683 5969 17447 18419 18769 51409 68921 90721 173101 281597 563957 743419 793223 935749 949537 1306783 1614127 1813069 2463059

The one composite I could find overnight that failed with x^2+{1,2,3}: 26756459

All were initialized with FAST=SLOW=2, as per wikipedia. Perhaps 0 would have been a better choice.

A few tests seem to show that going "deeper" with a single polynomial seemed on average more effective per CPU time than multiple polynomials run a fewer iterations.

No comments :