[math-fun] Efficient way to find solutions?
I'd like to efficiently find solutions to constraints of the form lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting. Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
How many constraints are in each && expression, exactly? Do you really mean there are 2^40 expressions joined by &&, or that you have 2^40 sets of lower_k and upper_k bounds, or something else? The order of 0x88405 mod 2^24 is 2^22, does that induce duplicated or contradicted constraints? The constant 0x88405 is invertible mod 2^24, can you multiply each constraint by 0x88405^-1 mod 2^24 sufficient times so that every constraint reads like this, for some j = j(k)? lower_k * 0x88405^-j <= x < upper_k * 0x88405^-j If yes, then could you proceed one constraint at a time hoping the intersection of all possible values for x will shrink to nothing? On 10/11/19 11:51 , Mike Stay wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas?
Thanks for your questions & comments! On Fri, Oct 11, 2019 at 10:40 PM Andres Valloud <avalloud@smalltalk.comcastbiz.net> wrote:
or that you have 2^40 sets of lower_k and upper_k bounds
This.
The order of 0x88405 mod 2^24 is 2^22, does that induce duplicated or contradicted constraints?
There'll be at most ten clauses ANDed together, so the order isn't an issue.
The constant 0x88405 is invertible mod 2^24, can you multiply each constraint by 0x88405^-1 mod 2^24 sufficient times so that every constraint reads like this, for some j = j(k)?
lower_k * 0x88405^-j <= x < upper_k * 0x88405^-j
No, because the upper and lower bounds are natural numbers. If all of them were elements of Z / 2^24 Z, then bounds wouldn't make sense.
If yes, then could you proceed one constraint at a time hoping the intersection of all possible values for x will shrink to nothing?
Well, shrink to a single value. About 20 years ago I published a ciphertext-only attack on zipcloak when there were five or more files in the archive. Now I've got a client who's only got two files, so there are fewer bits to filter with, and the brute-force I used before would be too much work. I'm guessing whether there's a carry at bit 24 of a 32-bit word. If there is a carry, that sets a lower bound on the low 24 bits, while if there isn't, that sets an upper bound. But then the whole state gets multiplied by 0x08088405 mod 2^32, so it spreads the range out over the whole space. I can work mod 2^24, but I'm hoping there's a way of calculating the answer rather than brute-forcing the space and filtering.
On 10/11/19 11:51 , Mike Stay wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
Throwing out some thoughts here... Set T1 = ((x * 0x000001) mod 2^24) and T2 = ((x * 0x088405) mod 2^24) etc. Then for each x, compute a T by bitwise concatenating T1,T2...T10 , which should be a 240 bit number. Granted 0 <= x < 2^24, there will be 2^24 such numbers. Sort all Ts into a list. Then the numbers that satisfy the first constraint (C1 from lower1, upper1) can be found within a range R1 in this list, Numbers that satisfy both C1 and C2 are found in a range R2 which is inside R1 etc. Test all 2^40 constraints against this sorted list, when the range is empty, the test has failed. I think this can be done in O= 2^40 * 2 * 24 * 10 ( Worst case using binary search to identify the ranges ) and should be doable with relative modest computing power. Or have I misinterpreted the problem ? /f On Fri, Oct 11, 2019 at 8:52 PM Mike Stay <metaweta@gmail.com> wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks, that's an excellent idea! On Sat, Oct 12, 2019 at 7:12 AM Frank Stevenson <frankstevensonmobile@gmail.com> wrote:
Throwing out some thoughts here...
Set T1 = ((x * 0x000001) mod 2^24) and T2 = ((x * 0x088405) mod 2^24) etc.
Then for each x, compute a T by bitwise concatenating T1,T2...T10 , which should be a 240 bit number. Granted 0 <= x < 2^24, there will be 2^24 such numbers.
Sort all Ts into a list. Then the numbers that satisfy the first constraint (C1 from lower1, upper1) can be found within a range R1 in this list, Numbers that satisfy both C1 and C2 are found in a range R2 which is inside R1 etc.
Test all 2^40 constraints against this sorted list, when the range is empty, the test has failed. I think this can be done in O= 2^40 * 2 * 24 * 10 ( Worst case using binary search to identify the ranges ) and should be doable with relative modest computing power.
Or have I misinterpreted the problem ?
/f
On Fri, Oct 11, 2019 at 8:52 PM Mike Stay <metaweta@gmail.com> wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
On second thought it probably won't be that efficient, since R2 is not a contiguous range :-( But maybe the method can be adjusted a little by having a table of booleans of points inside R1 that satisfies C2,C3,C4 etc. Other speed-up tricks could be to have 10 tables, with the high order bits taken from T1, T2, T3 in a cyclical fashion. The searching can be started from the sorted table that corresponds to the the narrowest set of criteria (fewest start points) This sounds like a fun problem that I could even contribute some time to do some programming if you are interested. Cheers, Frank On Sat, Oct 12, 2019 at 6:38 PM Mike Stay <metaweta@gmail.com> wrote:
Thanks, that's an excellent idea!
On Sat, Oct 12, 2019 at 7:12 AM Frank Stevenson <frankstevensonmobile@gmail.com> wrote:
Throwing out some thoughts here...
Set T1 = ((x * 0x000001) mod 2^24) and T2 = ((x * 0x088405) mod 2^24)
etc.
Then for each x, compute a T by bitwise concatenating T1,T2...T10 , which should be a 240 bit number. Granted 0 <= x < 2^24, there will be 2^24
such
numbers.
Sort all Ts into a list. Then the numbers that satisfy the first constraint (C1 from lower1, upper1) can be found within a range R1 in this list, Numbers that satisfy both C1 and C2 are found in a range R2 which is inside R1 etc.
Test all 2^40 constraints against this sorted list, when the range is empty, the test has failed. I think this can be done in O= 2^40 * 2 * 24 * 10 ( Worst case using binary search to identify the ranges ) and should be doable with relative modest computing power.
Or have I misinterpreted the problem ?
/f
On Fri, Oct 11, 2019 at 8:52 PM Mike Stay <metaweta@gmail.com> wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You haven't said what the lower and upper constraints look like. If they are parametrized nicely you can use a variant of what's called the Kelley cutting plane method. Basically, the idea is that at every stage you have a small finite set of "active" constraints. You find a feasible solution (i.e. one satisfying all the constraints). If upper and lower have a nice structure you can find some of the inactive constraints that are maximally violated, and add those, etc. Victor On Fri, Oct 11, 2019 at 2:52 PM Mike Stay <metaweta@gmail.com> wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Andres Valloud -
Frank Stevenson -
Mike Stay -
Victor Miller