Re: JSH: Factoring and residues

[added "JSH:" to subject; cut sci.crypt and alt.math]

[Proginoskes]
...
JSH discovered modular arithmetic and quadratic residues last week, and
he is thinking that that technique will save Surrogate Factoring. He
stubbornly refuses to accept that determining whether r is a quadratic
residue of N is just as hard as factoring N.

FWIW, it's more that he keeps insisting he's found efficient ways to find
multiple useful solutions to:

x^2 = C modulo N

where it's known that C is a quadratic residue of N. Finding multiple
solutions efficiently isn't sufficient, since not every pair of roots leads
to a non-trivial factor of N (remember that James always thinks he's done as
soon as k*N has been expressed as a difference of squares x^2-y^2 -- he
always "forgets" that gcd(x +/- y, N) can be useless even so).

Case in point: his last method had no way to find anything _but_ useless
pairs of roots -- although it could do so efficiently :-)

If he thought about what he was doing, he could cut the distractions and
just try to find multiple solutions to this efficiently:

x^2 = 1 modulo N

x=1 and x=N-1 are always roots, but gcd(1 +/- 1, N) and gcd(N-1 +/- 1, N)
are useless unless N is even. You just need to find other roots ;-)


.