# 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)
• 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)
• Re: GOLDBACH Conjecture - Some news on X = 0 (6)
... primes we can find the even numbers more inclined to violate Goldbach's conjecture. ... They are the even numbers 2k, that support more substractions before a prime difference appears. ... number which do not verify GOLDBACH is multiple of 6, ...
(sci.math)