Skip to main content
What to do if the number isn't odd.
Source Link
user2357112
  • 779
  • 6
  • 12

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 232 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 232 is 1041204193. So, multiply by 1041204193, and you have the original x back.

If we had, say, 60 instead of 33, we wouldn't be able to recover the original number, but we would be able to narrow it down to a few possibilities. By factoring 60 into 4*15, computing the inverse of 15 mod 232, and multiplying by that, we can recover 4 times the original number, leaving only 2 high-order bits of the number to brute-force. Wolfram Alpha gives us 4008636143 for the inverse, which doesn't fit in an int, but that's okay. We just find a number equivalent to 4008636143 mod 232, or force it into an int anyway to have the compiler do that for us, and the result will also be an inverse of 15 mod 2**32. (We get -286331153.)

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 232 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 232 is 1041204193. So, multiply by 1041204193, and you have the original x back.

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 232 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 232 is 1041204193. So, multiply by 1041204193, and you have the original x back.

If we had, say, 60 instead of 33, we wouldn't be able to recover the original number, but we would be able to narrow it down to a few possibilities. By factoring 60 into 4*15, computing the inverse of 15 mod 232, and multiplying by that, we can recover 4 times the original number, leaving only 2 high-order bits of the number to brute-force. Wolfram Alpha gives us 4008636143 for the inverse, which doesn't fit in an int, but that's okay. We just find a number equivalent to 4008636143 mod 232, or force it into an int anyway to have the compiler do that for us, and the result will also be an inverse of 15 mod 2**32. (We get -286331153.)

Source Link
user2357112
  • 779
  • 6
  • 12

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 232 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 232 is 1041204193. So, multiply by 1041204193, and you have the original x back.