# Reversing MODULO operation ? system of equations

i have 1000 prime numbers p1 ... p1000 .. which i use to encode a value

 v % p1 = r1
v % p2 = r2
v % p3 = r3
....
v % p1000 = r1000


then I pick the 20 PRIMES which gives the SMALLEST reminders and store them.

Later I want to be able to recover back the VALUE (or approximate value) by only having the 20 PRIMES available, and knowing they give the smallest reminders out of the 1000.

if it also helps I pick the sequence of 1000 primes above number N ... and for ease of use I encode a NEW_VALUE = VALUE + BIGGEST_PRIME

  def encode(self, value) :
mods = (value + self.max_prime) % self.primes
return np.argsort(mods)[:20]


@lulu

finding multiple values that match the prime-mods, should be ok too ... not 100% but i suspect i will use values in range .. 1-100, 1-1000 or any other , so I can narrow it down to that range.

I dont want to , but If I have to ;(

... may be some sort of constraint satisfaction

my final goal is to generate sparse 1000 bit binary based the position of the small-reminder primes

 self.primes = np.array(nprimes(start=11,cnt=1000), dtype=DTYPE)
np.random.shuffle(self.primes)


Looking for the decode() part !

• Do the 980 other prime numbers give strictly greater reminders? Jun 29, 2020 at 16:16
• yeah they give greater reminders ... unless 'strictly' has some other meaning
– sten
Jun 29, 2020 at 16:20
• Not sure I understand what you are saying, but as I read this what you are asking is not possible. For instance let $N$ satisfy $N\equiv 0 \pmod {p_i}$ for $i\in\{1,\cdots, 20\}$ and $N\equiv 1\pmod {p_i}$ if $i>20$. Then let $M$ satisfy $M\equiv 0 \pmod {p_i}$ for $i\in\{1,\cdots, 20\}$ and $M\equiv 2\pmod {p_i}$ if $i>20$. In each case you would just hand me the list $\{p_1, \cdots, p_{20}\}$, yes? So how could I distinguish $N$ from $M$?
– lulu
Jun 29, 2020 at 17:10
• @lulu ... yeah that is ok...if I can find N,M,... because it is mod it is possible the solution/s is multiple numbers not just one .. which is also Ok, because I suspect there will be some connection between them ..
– sten
Jun 29, 2020 at 17:57
• But there are many such, I just wrote down two. Just knowing that $N\equiv 0 \pmod {p_i}$ for $i\in\{1,\cdots, 20\}$ tells us nothing other than that those primes divide $N$...and of course, you don't even know that since, as I understand it, all you have is the list $\{p_1, \cdots, p_{20}\}$.
– lulu
Jun 29, 2020 at 18:04