1
$\begingroup$

I would to determine the set of values $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ that minimizes the value of $x$ such that:

$$x\equiv a_1\mod p_1$$ $$\vdots$$ $$x\equiv a_n\mod p_n$$

where every value $a_i$ can assume $m_i<p_i-1$ values fixed a priori in $\lbrace1,\ldots,p_i-1 \rbrace$ (in my case $m_i\sim(p_i-1)/2$ and $p_i$ is the $i_{th}$ prime). Is there a better way than using the Chinese reminder theorem over all the possible combinations of $a_i$? What is the state-of-the-art algorithm for this problem?

Any help or reference would be appreciated. Thanks.

Edit: the possible sets $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ doesn't contain trivial solutions like $\lbrace 1,1,1,\ldots,1 \rbrace$.


Thanks for the answer. I noticed that my question is bad written and i try to explain better here through an example.

In my problem the possible values for every $a_i$ are only a subset of $\lbrace 1,\ldots,p_i-1\rbrace$ (containing $m_i<p_i-1$ different values of $\lbrace 1,\ldots,p_i-1\rbrace$) so no one could decide a priori if $p_{n+1}$ can be represented. For example: $$x\equiv a_1\mod 2,\qquad a_1\in\lbrace1\rbrace$$ $$x\equiv a_2\mod 3,\qquad a_2\in\lbrace1,2\rbrace$$ $$x\equiv a_3\mod 5,\qquad a_3\in\lbrace3,4\rbrace$$ $$x\equiv a_4\mod 7,\qquad a_4\in\lbrace1,6\rbrace$$

has the minimum solution $x=13$ for $a_1=1$, $a_2=1$, $a_3=3$, $a_4=6$. I found this solution through an exhaustive search over the $2^3$ combinations of $a_i$ values and I was wondering if the general case of this problem has been studied in literature and if there was a reference or an algorithm for this purpose.

In particular I faced a problem with about $100$ congruences, and every $a_i$ can take $m_i$ known and fixed values with $m_i\sim (p_i-1)/2$. I know the minimal solution is somewhere near $10^{100}$ but I don't know how to find it.

$\endgroup$
  • $\begingroup$ What about $x=1$ and $a_i=1$? $\endgroup$ – joro Nov 19 '15 at 12:31
  • 3
    $\begingroup$ Are you perhaps looking for the smallest number that's a "quadratic nonresidue" of each of the first ~100 primes? $\endgroup$ – Noam D. Elkies Nov 19 '15 at 20:28
2
$\begingroup$

Let $A_i$ be the set of allowed values for $a_i$. Then $x$ satisfying the system recurrences represents a zero of the polynomial: $$f(x) = \sum_{i=1}^n \frac{M}{p_i} \prod_{a\in A_i} (x-a)$$ modulo $M$, where $M=p_1p_2\cdots p_n$. Small zeroes of this polynomial modulo $M$ can be found with the Coppersmith method.

UPDATE. For the given example, we have $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, and $A_1=\{1\}$, $A_2=\{1,2\}$, $A_3=\{3,4\}$, $A_4=\{1,6\}$. Then $M=2\cdot 3\cdot 5\cdot 7=210$ and $$f(x) = 142\cdot x^2 - 609\cdot x + 719.$$ PARI/GP provides an implementation of the Coppersmith method and can easily find small zeros of $f(x)$ modulo $M$ (I used $\sqrt{M}$ as a bound here):

? zncoppersmith(142*x^2 - 609*x + 719, 210, sqrtint(210))

%1 = [-1, 13]

So $x=-1$ and $x=13$ are the small zeroes (with the absolute value below $\sqrt{210}$) here.

$\endgroup$
  • $\begingroup$ On pari 2.7.1 this doesn't appear to work if the bound is sufficiently large for large $n$, say $\sqrt{n}$ even if is $n$ is smooth. Does it work for you? (This is unrelated to the question). $\endgroup$ – joro Nov 19 '15 at 17:25
  • $\begingroup$ @joro: pari documentation on 'zncoppersmith' says that the bound should be smaller than $M^{1/\deg(f)}$ (for the current settings). $\endgroup$ – Max Alekseyev Nov 19 '15 at 17:29
  • $\begingroup$ Does this work for you (fails for me): n=2^1061-1;zncoppersmith(x^2-1,n,sqrtint(n)-10^8) $\endgroup$ – joro Nov 19 '15 at 17:40
  • $\begingroup$ @joro: I have no idea why it fails for your code, but using $n^{1/3}$ instead of $n^{1/2}$ seems to fix the problem here: n=2^1061-1;zncoppersmith(x^2-1,n,sqrtnint(n,3)) $\endgroup$ – Max Alekseyev Nov 19 '15 at 17:45
  • $\begingroup$ Modulo bugs in the algorithm, pari has bugs too IMHO. $\endgroup$ – joro Nov 19 '15 at 18:22
0
$\begingroup$

Not counting "trivial" is not well defined, the solution $x$ is the smallest number $x$, coprime to all $p_i$ (since you exclude zero residue).

This is $p_{n+1}$, which is roughly bounded by $n \log{n} + n(\log \log{n} - 0.9385)$.

So we have $p_{n+1} = a_i \mod p_i$, which gives the $a_i$ after you have found $p_{n+1}$.

$\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.