3
$\begingroup$

Mathematica has trouble solving this Diophantine inequality:

(* givens *)
e = 653315732497285855855422606783
f = 1697172185816328002847853765504
g = 1650189636468405601822430434691
h = 2622176396697944576102111774652
m = 10^10

FindInstance[Abs[a f (g + d h) - b h (e + c f)] < m
  && 0 < c && c < a && a < m && 0 < d && d < b && b < m,
 {a, b, c, d}, Integers]

nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.

How can we help it?

Note: if that helps, the context insures Abs[a d - b c] < m. But adding that condition does not seem to improve things.

There are at least two solutions:

{{a -> 9861328816, b -> 6913952452, c -> 6835352265, d -> 4792386648},
 {a -> 7395996612, b -> 5185464339, c -> 6835352265, d -> 4792386648}}

See this question on the Cryptography Stack for context.


Update: I simplified the problem thru some simple modular arithmetic (see how in the related question on math-SE) but still hit a wall:

(* givens *)
e = 653315732497285855855422606783
f = 1697172185816328002847853765504
g = 1650189636468405601822430434691
h = 2622176396697944576102111774652
m = 10^10

(* derived quantities *)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

FindInstance[Mod[gg s, hh]<m && Mod[ee s, ff]<m && -mm<s && s!=0 && s<mm, s, Integers]

mpwc: FindInstance was unable to convert $\left\lfloor\frac{356075003617676589725598337103\,s}{424293046454082000711963441376}\right\rfloor$ to Piecewise because the required number 4196097564 of piecewise cases sought exceeds the internal limit $MaxPiecewiseCases = 100.


Update: Problem solved! But I would love to know how to have Mathematica rather than me make the math, even for the last step!

$\endgroup$
2
  • 1
    $\begingroup$ The result of Reduce[a f (g + d h) - b h (e + c f) < m && 0 < c && c < a && a < m && 0 < d && d < b && b < m && a f (g + d h) - b h (e + c f) > -m, {a, b, c, d}, Reals] may be useful. Only the two last cases lead to integer solutions. $\endgroup$
    – user64494
    Dec 8 '20 at 18:14
  • 1
    $\begingroup$ Putting $MaxPiecewiseCases = 10^10; and executing your modified code,I obtain "FindInstance::nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.". Every soft has its limitations. $\endgroup$
    – user64494
    Dec 9 '20 at 10:09
3
$\begingroup$

This is just a simplified code of the OP answer. The method is the same. The code uses the fact that a == gg s - u hh and b == ee s - v ff so it is not necessary to re-compute them using {a = Mod[gg s, hh], b = Mod[ee s, ff]}.

(* givens *)   
e = 653315732497285855855422606783;
f = 1697172185816328002847853765504;
g = 1650189636468405601822430434691;
h = 2622176396697944576102111774652;
m = 10^10;

(*derived quantities*)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

(*find all pairs {a, b}*)
ab = Or @@ 
   And @@@ Solve[
      0 < gg s - u hh == a < m && 
       0 < ee s - v ff == b < m && -mm < s && s != 0 && s < mm, {a, b,
        s, u, v}, Integers][[All, {1, 2}]] /. Rule -> Equal

(*find all {a, b, c, d}*)
Solve[(Abs[a f (g + d h) - b h (e + c f)] < m && 0 < c < a && 
   0 < d < b && ab), {a, b, c, d}, Integers]

Output:

(a == 2465332204 && b == 1728488113) || (a == 4930664408 && 
   b == 3456976226) || (a == 7395996612 && 
   b == 5185464339) || (a == 9861328816 && b == 6913952452)

{{a -> 2465332204, b -> 1728488113, c -> 1904687857, 
  d -> 1335410422}, {a -> 4930664408, b -> 3456976226, 
  c -> 1904687857, d -> 1335410422}, {a -> 4930664408, 
  b -> 3456976226, c -> 4370020061, 
  d -> 3063898535}, {a -> 7395996612, b -> 5185464339, 
  c -> 1904687857, d -> 1335410422}, {a -> 7395996612, 
  b -> 5185464339, c -> 4370020061, 
  d -> 3063898535}, {a -> 7395996612, b -> 5185464339, 
  c -> 6835352265, d -> 4792386648}, {a -> 9861328816, 
  b -> 6913952452, c -> 1904687857, 
  d -> 1335410422}, {a -> 9861328816, b -> 6913952452, 
  c -> 4370020061, d -> 3063898535}, {a -> 9861328816, 
  b -> 6913952452, c -> 6835352265, 
  d -> 4792386648}, {a -> 9861328816, b -> 6913952452, 
  c -> 9300684469, d -> 6520874761}}
$\endgroup$
1
  • $\begingroup$ Nice! The end is more elegant than my mess. Learned useful things, including 0 < c < a $\endgroup$
    – fgrieu
    Dec 9 '20 at 14:02
3
$\begingroup$

Solved! It works better when we explicitly change Mod[gg s, hh] < m into
0<= gg s - u hh && gg s - u hh < m with some additional variable u.

I though Mathematica would know that! And would love a way to make it automagic.

(* givens *)
e = 653315732497285855855422606783;
f = 1697172185816328002847853765504;
g = 1650189636468405601822430434691;
h = 2622176396697944576102111774652;
m = 10^10;

(* derived quantities *)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

(* find the list S of solutions s *)
S = Last /@ First /@ Solve[
    0 < gg s - u hh && gg s - u hh < m &&
    0 < ee s - v ff && ee s - v ff < m &&
    -mm < s && s != 0 && s < mm, {s, u, v}, Integers];

(* show the solutions as {a,b,{list-of-solutions {c,d}} *)
MySol[s_] := Block[{a = Mod[gg s, hh], b = Mod[ee s, ff]},
  {a, b,
    Solve[ Abs[a f (g + d h) - b h (e + c f)] < m &&
    0 < c && c < a && a < m && 0 < d && d < b && b < m,
    {c, d}, Integers]
  }]
SetAttributes[MySol, Listable];
MySol[S]

Which yields (hopefully) all the 10 solutions:

{{2465332204, 1728488113, {{c -> 1904687857, d -> 1335410422}}},
 {4930664408, 3456976226, {{c -> 1904687857, d -> 1335410422},
                           {c -> 4370020061, d -> 3063898535}}},
 {7395996612, 5185464339, {{c -> 1904687857, d -> 1335410422},
                           {c -> 4370020061, d -> 3063898535},
                           {c -> 6835352265, d -> 4792386648}}},
 {9861328816, 6913952452, {{c -> 1904687857, d -> 1335410422},
                           {c -> 4370020061, d -> 3063898535},
                           {c -> 6835352265, d -> 4792386648},
                           {c -> 9300684469, d -> 6520874761}}}}
$\endgroup$
1
  • 1
    $\begingroup$ +1. The solution presented by you is very tricky. $\endgroup$
    – user64494
    Dec 9 '20 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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