0
$\begingroup$

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.

btw i still have access to the 1000 primes

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 !

$\endgroup$
10
  • $\begingroup$ Do the 980 other prime numbers give strictly greater reminders? $\endgroup$ Jun 29, 2020 at 16:16
  • $\begingroup$ yeah they give greater reminders ... unless 'strictly' has some other meaning $\endgroup$
    – sten
    Jun 29, 2020 at 16:20
  • $\begingroup$ 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$? $\endgroup$
    – lulu
    Jun 29, 2020 at 17:10
  • $\begingroup$ @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 .. $\endgroup$
    – sten
    Jun 29, 2020 at 17:57
  • 1
    $\begingroup$ 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}\}$. $\endgroup$
    – lulu
    Jun 29, 2020 at 18:04

1 Answer 1

1
$\begingroup$

By the Chinese Remainder theorem, you can retrieve your number modulo the product of the twenty primes. That might be enough for your number.

If not, you are stuck because you can hypothesize any combination of remainders with the other primes (that are larger than the twenty remainders) and retrieve some number.

$\endgroup$
2
  • $\begingroup$ looking .... but i don't have the reminders only the primes $\endgroup$
    – sten
    Jun 29, 2020 at 16:47
  • $\begingroup$ @sten: then my intuition tells me that this is untractable, but I can't prove it. $\endgroup$
    – user65203
    Jun 29, 2020 at 16:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .