2
$\begingroup$

Given positive integers $a$, $b$, and $c$, and the function $f(x) = (5^a x)\ \%\ 2^b$, where $x\ \%\ y = x - y\lfloor \frac{x}{y} \rfloor$, what is the minimum of $f(x)$ the range $1 \leq x < 2^c$, with $x$ also integer?

Alternatively, given the inequality $(5^a x)\ \%\ 2^b < 2^d$, what is the minimum $x$ such that this is true?

This can be 'trivially' computed by trying all possible values for x, but I'm interested in cases where $a$, $b$, and $c$ are all large such that it is not possible to try all possible values of $x$ in reasonable time. I have run a couple of examples with a program I wrote:

$a = 43, b = 97, c = 27: \mathrm{min}\ f(x) = 723839456393370823360$ $a = 44, b = 99, c = 27: \mathrm{min}\ f(x) = 31872086829510029993510$

I have looked for various combinations of product, congruence, and inequality, minimum on Google as well as here. I've tried Wolfram Alpha, which didn't give me anything useful (e.g. link).

At this point I'm not even sure there is a better solution than brute force $O(2^c)$. Even if there's no direct way to compute the result, I'd also accept an algorithm that takes less than linear time (e.g., $O(\sqrt{2^c})$ or $O(log(2^c))$).

$\endgroup$
0
$\begingroup$

By trial and error I've discovered an algorithm that gives me the correct output for all the cases I've looked at, and that isn't brute force. Here's my Java code. I haven't been yet been able to prove correctness.

BigInteger pow5 = BigInteger.valueOf(5).pow(28); BigInteger pow2 = BigInteger.ONE.shiftLeft(17); BigInteger max = BigInteger.ONE.shiftLeft(11); BigInteger min3 = BigInteger.ZERO; BigInteger pow5inv = pow5.modInverse(pow2); BigInteger a = pow5.mod(pow2); BigInteger b = pow2.mod(a); outer: while (true) { while (b.compareTo(a) > 0) { b = b.mod(a); } while (a.compareTo(b) > 0) { // Note that this loop implements a = a.mod(b), but does so step by step. a = a.subtract(b); BigInteger orig = a.multiply(p5inv).mod(pow2); if (orig.compareTo(max) > 0) { break outer; } min = a; } }

$\endgroup$

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.