Re: JSH: Understanding quadratic residues result

On Sat, 21 Nov 2009 11:54:20 -0800, Enrico wrote:


This is not disagreement. I looked at my spreadsheet and decribed what I
saw. Remember, I start with k=0, 1, 2, 3, ... and k^2 mod N in the first
two columns on my spreadsheet. additional columns apply your equations.
Its a brute force, show everything, tweak anything research tool.

Given q mod N, k matters. With N the product of 2 primes and k, q
coprime to N, I can find 4 values of k that work in every interval of N.
Thats where the 4/N comes from.


Enrico

If N is the product of two odd primes then every k such that k^2=q mod N
will be matched by another k (call it l) such that l^2=q mod N. Proof
provided on request but basically (k-l) will be a multiple of one of the
primes and (k+l) a multiple of the other prime.

Given each k^2 = q mod N is also matched by (N-k)^2 = q mod N then we
have four solutions: k, l, N-k, N-l. This is why you are finding four
values.

Regards, Michael W.

.

Relevant Pages

  • Re: JSH: Understanding quadratic residues result
    ... Its a brute force, show everything, tweak anything research ... With N the product of 2 primes and k, ... primes and a multiple of the other prime. ...
    (sci.crypt)
  • Re: Square root algorithms and complexity
    ... >>> Finding a way to get another ten fold increase would be helpful. ... That's up to several dozen small primes, ... >>factors of 2^B-1 where B is a small multiple of the word width. ... > indicating whether that can or cannot be a the residue of a square. ...
    (sci.math)
  • Re: Review of Mueckenheims book.
    ... >> able to multiply three primes. ... They both refer to finding a common multiple, ... > finite multitude, it could be assigned, or why could it not? ... He did not call that infinite, but in act it is what we call ...
    (sci.math)
  • Conjecture on the relationship of Prime distribution to Perfect Square Distribution
    ... number of perfect squares less than x, ... and the Complimentary Set is all the other numbers are composites so ... So for 100 wherein 25 are primes and then the compliment of 75 are ... So some multiple, call it Y we have for the Composite ...
    (sci.math)
  • Re: questions about a "proof" of the Goldbach Conjecture.
    ... I'll call a set S of positive integers a "Goldbach set" if every even ... actually uses the fact that S is a set of primes. ... numbers that would have to be composite to make 10^100 a counter ... so every prime number offset from 9 by a multiple of 3 is also ...
    (sci.math)