Reverse carry-less binary multiplication problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

deskjethp
Posts: 49
Joined: Wed Mar 02, 2011 3:28 am UTC

Reverse carry-less binary multiplication problem

Postby deskjethp » Fri Nov 20, 2015 10:48 pm UTC

Rule the fifth declaration: This is not homework, but probably looks like it. It's just an interesting thing I ran across the other day on a coding website.

So I found this decryption challenge where an obfuscated encryption algorithm is provided and the challenge is to code up a decryption program. When simplified (It's all presented in hex and whatnot in the beginning), I found the encryption takes two given inputs and does the equivalent of longhand binary multiplication on them up to the point where all the addends would be added together, but does an XOR operation on them instead of adding them, producing the output. This XOR step would be the same as just doing the adding but never carrying. The goal of the challenge is to provide the possible original factors, having been given the result.

Example encryption:

Image

Given the inputs 11111 and 11111, they get almost-multiplied together giving the addends 11111, 111110, 1111100, 11111000, and 111110000. These are XOR'd together producing 101010101. So given something like 101010101, the goal is to produce (11111 , 11111) as output. Or whatever other factors might happen to produce it.

Another example with multiple inputs that produce the same output:

Image

In this case, the goal is to produce (011, 110) and (101, 10). I've noted that for outputs that end in 0, 2 (10) is a possible input. Some inputs (there might be a pattern here that will help) also produce the same output as when they are multiplied (101 and 10 produces 1010, 101 and 11 produce 1111, etc).

So far, I've figured out the following:

1) It is not feasible to brute force this beyond a low number of digits in the output.
2) Factors of x digits and y digits produce an output of x+y-1 digits.
2b) Therefore any amount of addends may be produced from 1-n where n=output digits
2c) Obviously, multiplying a 6 digit by a 2 digit number longhand will either produce 6 addends or 2 addends for example. They will XOR together to the same result and
must therefore share some property, but I don't know what.
3) Whatever addends are produced are going to all be the topmost one shifted to the left some number of times.
4) If the output ends in 1, both factors must also end in 1.
5) The leftmost digit of the largest is always going to be a (You wouldn't have leading 0s)

All of this is sort of helpful in figuring out an efficient way of solving this, most particularly #3 probably, but I don't know how to calculate this efficiently for a set of two 128 bit inputs as the problem states. I know there's a way to do it, since a number of folks have solved it, but working in a deductive brute force fashion isn't going to cut it. On top of that, I don't know if there's a direct correlation between the factors and the answer, if the addends need to be calculated, and I don't have a good way of getting the factors from the given addends. The addends->factors part is easy enough to deal with for one of the inputs since it's all left shifts and one of them can be deduced from the topmost non-zero addend, but given that there are multiple sets of input factors for each given output, figuring them all out is proving to be a challenge.

Insights anyone?
arbivark wrote:when i was first a tenant at 19, i was probably a nuisance .. a bother, to the landlord because i'd do stuff like, hey there's a fireplace here, get me a hammer, hey if i make a hole in my ceiling there's an attic that runs the length of the rowhouses.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5305
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Reverse carry-less binary multiplication problem

Postby Thesh » Fri Nov 20, 2015 11:04 pm UTC

Ask yourself this: under what conditions would the least significant bit of the output be "1" - you should be able to figure it out from there.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

deskjethp
Posts: 49
Joined: Wed Mar 02, 2011 3:28 am UTC

Re: Reverse carry-less binary multiplication problem

Postby deskjethp » Fri Nov 20, 2015 11:20 pm UTC

If both inputs end in 1, then the output ends in 1. I have stated this in 4). However, beyond only the rightmost digit, I haven't yet been able to determine a pattern.

Am I missing something obvious?
arbivark wrote:when i was first a tenant at 19, i was probably a nuisance .. a bother, to the landlord because i'd do stuff like, hey there's a fireplace here, get me a hammer, hey if i make a hole in my ceiling there's an attic that runs the length of the rowhouses.

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Reverse carry-less binary multiplication problem

Postby Cauchy » Sat Nov 21, 2015 6:08 pm UTC

If we treat the binary string a_na_{n-1}...a_0 as the polynomial a_nx^n + a_{n-1}x^{n-1} + ... + a_0x^0, then your multiplication is multiplication of these polynomials in the polynomial ring over Z/2Z, that is, the integers modulo 2. Since Z/2Z is a field, Z/2Z[x] is a unique factorization domain, which means that every polynomial factors uniquely into prime polynomials. In your original multi-factor example, for instance, x^3 + x = x(x+1)^2 modulo 2, so 1010 can be written as [x(x+1)^2]*1 = 1010 * 1, [x(x+1)]*(x+1) = 110*11, or [(x+1)^2]*x = 101*10.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5959
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Reverse carry-less binary multiplication problem

Postby jestingrabbit » Mon Nov 23, 2015 9:59 am UTC

So, to add to what Cauchy is saying, you can build up a big bag of "prime" polynomials, say, all the polynomials of degree less than n, then you can try to divide each polynomial of length n by each polynomial with degree less than floor(n/2) to get the primes of degree n. And you don't have to test all of them, you know the one's with a 0 in the least significant bit are divisible by x, and the ones with an even number of bits set to 1 are divisible by x+1, and there's a somewhat trickier rule for x^2 +x +1, so you don't need to deal with all the polynomials, and given an input of length m, you only need to get the primes up to m/2, and you only have to build as many as you need till you get factors of the input.

So, still computationally pretty heavy, but a little more tractable.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

SecMunic
Posts: 1
Joined: Tue Feb 14, 2017 3:41 pm UTC

Re: Reverse carry-less binary multiplication problem

Postby SecMunic » Tue Feb 14, 2017 3:45 pm UTC

The inverse operation is super simple:

write the number in base 4. You will get a number with only 0 and 1

interpret the number as written in base 2 (common binary). That's the answer.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests