For testing purposes, I need to find two 64-bit integer values that exactly multiply to a 128-bit intermediate value with a specific bit pattern. Obviously, I can generate the desired intermediate value and divide by random values until I find a combination that works, but is there a more efficient way?
views:
157answers:
3
+7
A:
This problem sounds like integer factorisation. No fast algorithms are known unfortunately, but from glancing at that Wikipedia page it seems there are some (possibly tricky) algorithms that are faster than trial division.
j_random_hacker
2009-09-16 15:59:16
Indeed I had a feeling that was the case. It's made even trickier by the fact that the two target variables have to fall within a given range.
gct
2009-09-16 16:01:03
+4
A:
I was about to post the same thing as j_random_hacker. I'll just add that if the 128-bit number is prime, or has a prime factor larger than 64 bits, then there will be no solution to your problem.
jbourque
2009-09-16 16:03:11
Fortunately I can just generate a new 128-bit value after a certain number of iterations have failed. So that's a bonus.
gct
2009-09-16 16:06:34
Well, if you can generate new 128-bit values, then what's special about the values? Wouldn't it be easier to generate 64-bit values and multiply them together? If you need special characteristics in the 128-bit value, it's might be easier to figure out how to make 64-bit pairs of numbers that will multiply to a 128-bit value with the desired characteristics than to do it the other way around.
jbourque
2009-09-16 16:23:37
+1
A:
And I'll just add to previous comment: if 128 bit number has prime factor larger than 64 bits, then it certainly has a factor less than 64 bits :)
Eugene N.
2009-09-16 17:31:23