0

Suppose we have a function $f(n) = 1$ when $n \equiv x mod M$ and $0$ otherwise, but I don't know $M$.

Also suppose I know $f = 0$ for a subset of $q$ natural numbers.

How I can delimit $M$? That is, $M > m1$.

There are exist a known algorithm fo such a problem?

Any clue to investigate further is welcome.

Edit: $x$ is fixed and unknown.

Edit2: One trivial algorithm is just test all possible values of M from 2 to $q$. I look for a more optimal algorithm because $M$ and $q$ can be big ($10^5$).

Alnair
  • 141

2 Answers2

0

Suppose, $f=0$ for $k$ consecutive natural numbers. Then, we can conclude $M>k$ because of $M$ consecutive integers , there must be one congruent to $x$ modulo $M$

Peter
  • 84,454
  • Yes, but the set of natural number can be not consecutive. That's the problem. – Alnair Apr 29 '19 at 12:19
  • Then, you have to find the greatest block of positive integers contained in the given set. And depending on the set, you may be able to rule out more moduli. – Peter Apr 29 '19 at 12:52
0

Thoughts/Avenues:

  • Check if their sum and/or difference are in the set, if they are, then their remainders don't add and/or subtract to x.

  • Take their gcd. if they are same remainder mod M, their gcd will be a factor of M.

etc.