On Mon, Sep 29, 2014 at 10:24 AM, Mike Stay <metaweta@gmail.com> wrote:
Say you know the Jacobi symbol of x modulo various numbers n > x. Each symbol should give roughly one bit of information about x. (The symbol 0 gives more information.) Assuming all the symbols are either +/-1, I think that ceil(log_2(x)) symbols are necessary; does that number of symbols always suffice?
I'd be surprised if it did. It seems like there ought to be some algorithm like Berlekamp-Massey where you're allowed to pick some string of residues and it gives you the smallest prime whose residues start with that sequence. Given such an algorithm, it would be straightforward to construct a set of ceil(log_2(x)) primes where only the first gives any information about what x is. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com