1

I have a good solution for Prime Factorization implemented in VB.Net with BigInteger using both Pollard's Rho and Brent's algorithms (see: https://stackoverflow.com/a/31978350/44080)

For N< 2^63 I belive UInt64 should be adequately large, and possibly (much?) faster.

However my UInt64 conversion fails on this line:

y = ((y^2) Mod n + c) Mod n 'fails when y^2 > UInt64.Max

Changing this line to

y = CULng((CDbl(y^2) Mod n + c) Mod n)

Kills performance since the type conversion is in a loop.

Please how can I fix this?

I still think UInt64 will out perform BigInteger if we can side step the above issue.

EDIT:

I just found this: Dirichlet .NET Number Theory Library which claims to have Int128 and Int256 that out performs .Net BigInteger.

It even has several optimized algorithms for Prime number Factorization. Could have saved me 2 days of research and testing.

Community
  • 1
  • 1
Charles Okwuagwu
  • 10,538
  • 16
  • 87
  • 157
  • @WDS Thanks again for the pointing me to Pollard's Rho Algorithm in the linked SO solution – Charles Okwuagwu Aug 13 '15 at 11:21
  • Basically you can't, but you can change the limit on N to make it work. – harold Aug 13 '15 at 11:24
  • @harold you are refereeing to y^2. I was hoping a cleaver refactoring of the algorithm or a variant would eliminate the need for y^2 – Charles Okwuagwu Aug 13 '15 at 11:27
  • 4
    You can't use `double`... they don't have the needed precision. If y is 64 bit, then y^2 is up to 128 bits. There is no integral data type of 128 bits. You could restrict yourself to factoring Int32 numbers, then you wouldn't have any problem. – xanatos Aug 13 '15 at 11:35
  • @CharlesO it's theoretically possible in you can calculate a square by summing partial products and then you can mod them before they overflow, but that's insanely slow. – harold Aug 13 '15 at 11:39
  • If you need factorization of this big numbers, and you can't afford BigIntegers for performance reasons, I'd rather suggest re-thinking your solution. How often does this factorization occur? Are those Bigints really that bad? Have you done some profiling? – Borsunho Aug 13 '15 at 11:43
  • @harold Uint64 would definitely out perform BigInteger. I would then need to test N before choosing which implementation to use. – Charles Okwuagwu Aug 13 '15 at 11:43
  • Yes. N < 2^32 should work. – harold Aug 13 '15 at 11:47
  • or rework the algorithm with the UInt64 in mind – Charles Okwuagwu Aug 13 '15 at 11:51
  • 1
    @CharlesO well no not really. – harold Aug 13 '15 at 12:21
  • 1
    `(y^2) Mod n` - I am not a mathematician, but intuition suggests that this can be optimized somehow. – 500 - Internal Server Error Aug 13 '15 at 12:55

1 Answers1

1

How to perform modular multiplication (compute the square) without overflow:

As long as the modulus is at least one bit less than the maximum, the solution is to split the numbers in low-bit and high-bit halves, then perform the arithmetic piecemeal, kind of like grade-school multiplication where you multiply by the one’s digit, then shift the sum and multiply by the ten’s digit, and so on, except that the “digits” are the size of the square root of the maximum number that can be represented in the integer datatype.

Consider the example of calculating 56 * 37 modulo 100 using 8-bit arithmetic, so no intermediate total may be 256 or greater. We start by representing a = 56 = 3 * 16 + 8 and b = 37 = 2 * 16 + 5, (note that 16 is the square root of 256) so:

a1 = 8
a2 = 3
b1 = 5
b2 = 2

Then the four intermediate products with their shifts are:

p11 = 8 * 5 = 40
p12 = 8 * 2 = 16 > 32 > 64 > 128 (28) > 56
p21 = 3 * 5 = 15 > 30 > 60 > 120 (20) > 40
p22 = 3 * 2 = 6 > 12 > 24 > 48 > 96 > 192 (92) > 184 (84) > 168 (68) > 136 (36)

We’re using binary arithmetic, so each number doubles as it is shifted, taking it modulo 100 as we go. The product of two low-half numbers is not shifted, the product of a low-half and high-half number is shifted 4 times (since log2 16 = 4), and the product of two high-half numbers is shifted 8 times. Then the intermediate products are summed, again removing m each time an intermediate sum exceeds m:

s = 40 + 56 = 96
s = 96 + 40 = 136 (36)
s = 36 + 36 = 72

And that’s the final answer: 56 * 37 = 2072, which is 72 (mod 100).

If m is within one bit of the maximum for the integer data type, things get messier; the basic answer is to split into three parts, compute the intermediate products, and recombine.

See my blog for code in Scheme, and also a contributed solution in C that uses a somewhat different algorithm.

user448810
  • 17,381
  • 4
  • 34
  • 59