Multiple Precision Signed Integer Package by James Pate Williams, Jr.

I very recently created a multiple precision signed integer package in C++ using the standard library and a base of 10. I then implemented two integer factoring algorithms trial division and Pollard’s Rho method. Trial division uses all the prime numbers <= 10000 and there are 1229 such primes. Due to the choice of language and the exceedingly small base the resulting application is awfully slow when compared to a similar C# application. The multiple precision signed integer package is largely based on translation of the Pascal source code found in “Prime Numbers and Computer Methods for Factorization” by Hans Riesel. The test number is 2 ^ 72 – 1 which is a Mersenne composite integer. The output large integers start with the number of base 10 digits in the number. For comparison I have included the output from my C# Big Integer factorization program as a screen shot.
Menu

0 Exit Application
1 Test of Package
2 Trial Division
3 Pollard Rho

2

n = 4722366482869645213695

Duration (min:sec.mil) = 00:08.784

n is composite, factors:

3 ^ 3 factor has 1 digits
5 factor has 1 digits
7 factor has 1 digits
13 factor has 2 digits
17 factor has 2 digits
19 factor has 2 digits
37 factor has 2 digits
73 factor has 2 digits
109 factor has 3 digits
241 factor has 3 digits
433 factor has 3 digits
Large prime 5 3 8 7 3 7


Menu

0 Exit Application
1 Test of Package
2 Trial Division
3 Pollard Rho

3

n = 4722366482869645213695

n is composite, factors:

 2 2 1
 1 3
 1 3
 4 3 5 1 5
 2 1 3
 4 1 2 4 1
 3 2 4 1
 3 1 0 9
 3 4 3 3
 5 3 8 7 3 7

 1 3
 1 3
 1 3
 1 5
 1 7
 2 1 3
 2 1 7
 2 1 9
 2 3 7
 2 7 3
 3 1 0 9
 3 2 4 1
 3 4 3 3
 5 3 8 7 3 7

Duration (min:sec.mil) = 00:02.197