Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

For my Cryptography research I am interested in finding solutions to the following inequalities in terms of $r$ and $s$, where $p$ is some fixed constant.

$$\begin{align} 2^{p - s + 4} + 2^{p - r} + 2^{p - r - s + 4} + 13/4 < 2^{p - 8} \\ 2^{p - r + 4} + 2^{p - s + 8} + 2^{p - r - s + 8} + 13/4 < 2^{p - 4} \end{align}$$

I have tried the following computation:

Solve[2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 2^(p - 8) && 
2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 2^(p - 4), {r, s}]

Unfortunately, it is taking forever to compute (literally days), so does anyone have any ideas?

Thanks!

share|improve this question
    
Have you tried using Reduce[] instead of Solve[]? –  J. M. Jul 4 '12 at 0:04
    
@J.M. I have not, I will go try it! Thanks for the suggestion. –  Samuel Reid Jul 4 '12 at 0:08
    
Specify domain as an option Reduce[... , {r,s} , Integers] or Solve[... , {r,s} , Reals] - depending on what you are looking for. It may not be solvable. Try to narrow down parameter P then. –  Vitaliy Kaurov Jul 4 '12 at 0:22
    
I tried both of your ideas and they were not very useful in reducing the computation time. Any other ideas? –  Samuel Reid Jul 4 '12 at 0:47
4  
Why a downvote ??? This question is really good one, showing limits of symbolic computing (at least of Solve or Reduce). And it is really original among hundreds boring questions on front-end rubbish. –  Artes Jul 4 '12 at 15:54
add comment

3 Answers

up vote 8 down vote accepted

Let's start by seeing if there is a solution at all.

conds = 2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 2^(p - 8) &&
        2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 2^(p - 4)
FindInstance[ conds, {p, r, s}, Integers]
(* {{p->84, r->164, s->92}} *)

Ok, that looks nice, there is at least one solution. We can visualize the solution space including the solution FindInstance found with

RegionPlot3D[conds, {p, 0, 200}, {r, 0, 200}, {s, 0, 200}, AxesLabel -> {p, r, s}]

RegionPlot of solution space

Ok, it looks there are hard lower limits for each parameter and a soft transition between those planes. We can have a look at that interesting part.

RegionPlot3D[conds, {p, 7, 20}, {r, 7, 20}, {s, 7, 20}, AxesLabel -> {p, r, s}]

RegionPlot of solution space detail

Now to get some quantifiable lower limits, we can make it easier for Reduce by working with 2 to the power of p,r,s instead of the parameters themselves.

powconds = conds /. Thread[{p, r, s} -> Log[2, {pp, pr, ps}]]

conditions in terms of the powers

Reduce[powconds, {pp, pr, ps}, Integers] still takes forever so let's constrain pp,pr,ps to be positive.

pospowconds = powconds && And @@ Thread[{pp, pr, ps} > 0]

pow conditions with positive integer constraint

Now

reducedconds = Reduce[pospowconds, {pp, pr, ps}]

is able to find a nice reduction

reduced pow conditions

that we can transform back to our original parameters

newconds = reducedconds /. Thread[{pp, pr, ps} -> 2^{p, r, s}]

reduced conditions in the original parameters

or in terms of p,r,s that is

newconds /. Greater[a_, b_] -> Greater[Log[2, a], Log[2, b]] // PowerExpand

taking the logarithm of the inequalities

So now we have a lower limit for p. Are there lower limits for r and s, too? Let's go back to the reduced power conditions and ask the question in terms of quantifiers

questions =  MapThread[ 
    Exists[#1, ForAll[{pp, pr, ps}, reducedconds, #2 > #1]] &,
    {{lowerpr, lowerps}, {pr, ps}}
  ]

Are there lower limits for r and s?

and let Mathematica resolve the questions for us

Resolve /@ questions
(* {True, True} *)

So there are lower limits for r and s, too. Nice! Since we're lazy we let Mathematica do the work of finding the highest lower limit for which the conditions are still satisfied:

VariableGreaterThan[var_, threshold_] := Resolve[
    ForAll[{pp, pr, ps}, reducedconds, var > threshold]
  ]
lowerpowerlimits = FindMaxValue[
    {th, VariableGreaterThan[#, th] \[And] th \[Element] Integers},
    {th, 1}
  ] & /@ {pp, pr, ps}
(* 832., 256., 4096. *)

so the lower limits of p, r, s are

lowerlimits = Log[2, lowerpowerlimits]
(* {9.70044, 8., 12.} *)

Our plot of the solution space from above with the new tight bounds

RegionPlot3D[
    conds,
    {p, #1, #1 + 10}, {r, #2, #2 + 10}, {s, #3, #3 + 10}, 
    AxesLabel -> {p, r, s}
  ] & @@ lowerlimits

solution space with tighter bounds

share|improve this answer
    
Thank you very much for the thoughtful response, your answer was the most useful for actually answering my question so I am accepting it (although the other ones were also very insightful as well!) –  Samuel Reid Jul 4 '12 at 18:50
    
Thanks for the positive feedback, glad that it was helpful to you! –  Thies Heidecke Jul 4 '12 at 22:21
add comment

Just to clarify, you keep mentioning speed, but there is no issue with speed, but fundamental solvability. Both of this formulation will almost momentarily report about solvability impasse:

eq = 2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 
   2^(p - 8) && 2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 
   2^(p - 4); eq // TraditionalForm

enter image description here

Solve[eq, {r, s}, Reals]

enter image description here

Reduce[eq, {r, s}, Reals]

enter image description here

So, to reiterate, this is not the issue of time, but solvability. You should always try to tweak your problem to make it solvable. For example set some numerical values for some parameters and see if solution makes sense. Following the @belisarius advice in the comments, try specific instances:

FindInstance[2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 2^(p - 8) && 
  2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 
   2^(p - 4) && p == 256 && 0 < r <= s, {p, r, s}, Reals, 10]

enter image description here

Or Try visualization:

RegionPlot3D[eq, {p, 10, 15}, {r, 9, 10}, {s, 13, 15}, Mesh -> 8, 
 MeshFunctions -> {Function[{x, y, z}, Norm[{x, y, z}]]}, 
 MeshShading -> {Directive[Yellow, Opacity[0.4]], FaceForm[Cyan, Red]}]

enter image description here

share|improve this answer
1  
Try FindInstance[ 2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 2^(p - 8) && 2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 2^(p - 4) && p == 256 && 0 < r <= s, {p, r, s}, Reals, 10] –  belisarius Jul 4 '12 at 4:30
1  
For some detail RegionPlot3D[eq, {p, 10, 15}, {r, 8, 10}, {s, 12, 15}] –  belisarius Jul 4 '12 at 4:39
    
@belisarius thanks, nice catch - I updated the post, gave you credit. Still there is no issue with time as author claims. –  Vitaliy Kaurov Jul 4 '12 at 6:52
    
Yep. You are right –  belisarius Jul 4 '12 at 12:30
    
@VitaliyKaurov: Thanks for clearing up my concern about how I thought the computation was using a bad algorithm since it was taking so long to do. –  Samuel Reid Jul 4 '12 at 18:52
add comment

FindInstance may give us many solutions but no information on the solution space. So this is not a very welcome approach. Therefore we would rather like bounds for p,r,s working with Reduce.

We get rid of 2^p, 2^r, 2^s changing them respectively to x, y, z.

ineq= 2^(p - s + 4) + 2^(p - r) + 2^(p - r - s + 4) + 13/4 < 2^(p - 8) && 
      2^(p - r + 4) + 2^(p - s + 8) + 2^(p - r - s + 8) + 13/4 < 2^(p - 4)

ineq1 = ineq /. Thread[ {p, r, s} -> Log2 @ {x, y, z}]
 13/4 + x/y + (16 x)/z + (16 x)/(y z) < x/256 && 
 13/4 + (16 x)/y + (256 x)/z + (256 x)/(y z) < x/16

and we solve the inequalities with respect to y , z assuming them to be real and positive :

Reduce[ ineq1 && y > 0 && z > 0 && x > 0, {y, z}, Reals]
 x > 832 && y > (256 x)/(-832 + x) && z > (4096 x + 4096 x y)/(-256 x - 832 y + x y)

To proceed further we can do this

x > 832 && y > (256 x)/(-832 + x) &&
z > (4096 x + 4096 x y)/(-256 x - 832 y + x y) /. {x -> 2^p, y -> 2^r, z -> 2^s}
2^p > 832 && 2^r > 2^(8 + p)/(-832 + 2^p) &&
2^s > (2^(12 + p) + 2^(12 + p + r))/(-2^(8 + p) - 13 2^(6 + r) + 2^(p + r))

Instead of putting this output to Reduce and getting

Reduce::nsmet: This system cannot be solved with the methods available to Reduce. >>

we'll do this :

Reduce[2^p > 832, p, Reals]
p > (6 Log[2] + Log[13])/Log[2]

or

Reduce[2^p > 832, p, Integers]
p ∈ Integers && p >= 10
(6 Log[2] + Log[13])/Log[2] // N
9.70044

Next e.g. we can find bounds for r and s assuming values of p :

Reduce[p == # && 2^r > 2^(8 + p)/(-832 + 2^p) && 
       2^s > (2^(12 + p) + 2^(12 + p + r))/(-2^(8 + p) - 13 2^(6 + r) + 2^(p + r)),   
       {r, s}, Reals] & /@ Range[10, 13] 

enter image description here

If we assume the domain of r ,s to be Integers that will lead to this message Reduce::nsmet: ....

RegionPlot3D[ineq, {p, 8, 15}, {r, 8, 15}, {s, 11, 15}, Mesh -> 4, MeshFunctions -> {#1 &}, 
             PlotStyle -> Directive[ Specularity[0.3], Opacity[0.3], FaceForm[ Blue, Green]]]

enter image description here

share|improve this answer
1  
Have you tried your hand at Project Euler? I think you'd be good at it. –  Mr.Wizard Jul 4 '12 at 12:19
    
@Mr.Wizard Thanks, once I took a look at PE, but somehow I haven't so far returned there. –  Artes Jul 4 '12 at 12:27
2  
@Artes: That substitution $2^p \rightarrow x, 2^r \rightarrow y, 2^s \rightarrow z$ was a great idea. Thanks for the answer! –  Samuel Reid Jul 4 '12 at 18:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.