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

On 29/09/2014 20:26, W. Edwin Clark wrote:

Say that n ~ m if for each of the first 1000 primes p we have legendre(n,p) = legendre(m,p)

Each line below is an equivalence class with more than two elements where n and m are each <= 500.

If m,n are multiples of the same set of primes and their ratio is the square of a rational number, then legendre(m,p) = legendre(n,p) for *all* p. It seems like it's worth filtering out these cases. Brief inspection suggests that in fact all your equivalence classes are of this form, but I haven't done the actual calculations to check in more than a handful of easy-by-eye cases. -- g

This has been studied a lot. You might look at "Integer Sequences having prescribed quadratic character" by D.H. and Emma Lehmer and Dan Shanks, in Math. Comp. vol 24, April 1970 (page 433---), in which they look at this from a computational point of view. If m,n are your two integer which have the same set of values for quadratic residues of a bunch primes, use quadratic reciprocity of the Jacobi symbol (assume, for convenience that m,n are odd): (m/p_i) = +/- (p_i/m) (where the sign comes from quadratic reciprocity). Then look at chi(r) = (r/m)*(r/n) (i.e the product of the two quadratic residue symbols. Your hypothesis is that chi(p_i) = 1 for all i. The conductor of this character is <= 4*m*n. The generalized RH says that if it's non-trivial (not identically 1) then there is an integer q <= C*log^2 (4*m*n), for some absolute constant C (I believe that Eric Bach showed that you can take C=2), so that chi(q) != 1. If you don't assume the generalized RH, the bound is something like C*sqrt(4*m*n) log(4*m*n). Victor On Mon, Sep 29, 2014 at 3:58 PM, Andy Latto <andy.latto@pobox.com> wrote:

The quadratic character of a wrt N depends only on the residue class of a mod N.

So if you know the residue class of a for a set of values N_i, the best you can do is reconstruct a up to a multiple of the lcm of the N_i.

Andy Latto andy.latto@gmail.com

On Mon, Sep 29, 2014 at 12:49 PM, Henry Baker <hbaker1@pipeline.com> wrote:

...

The following question occurred to me on a long bike ride (?!?) yesterday:

Suppose I know the quadratic character of a wrt N for lots of different N's.

Under what conditions can I reconstruct N ?

I.e., is there a "Chinese Remainder Theorem" for quadratic residues?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Andy.Latto@pobox.com

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun