### Saturday, March 28, 2009

## JSH: Quadratic residues and large composite factoring

I've been brainstorming a factoring idea for less than 24 hours which involves using quadratic residues to factor, relying on the fact that non-square residues should be shared by two large prime factors for a particular quadratic residue only roughly 50% of the time.

The idea is bizarrely simple, given a target composite T, where T=p_1*p_2, where the p's are large primes and p_1>p_2,

with m = [sqrt(T)] + 1, find residues r(n) = (n*m)^2 mod T, from n=1, to some relatively small number, like 1000 or 10000, and take the mean of r(n).

For approximately 50% of the cases the non-square quadratic residues for p_1 and p_2 will match, and for those case r(n) will tend to be LESS than p_2.

For the other approximately 50% of the cases the non-square quadratic residues for p_1 and p_2 will not match—or "bump" as I like to say—and for those cases r(n) will tend to be GREATER than p_2.

So the mean should approximately give p_2 itself!!!

What a remarkably simple idea for finding approximately what the value of p_2 is for large prime factors!!!

Anyone heard of this before? I've been brainstorming it out for, what, I think about, 16 hours now.

I'm curious about whether or not it's new.

Anyone wonder why it would be useful for factoring if you approximately new p_2? After all, you need to know it exactly, right?

Ok, short answer is that then you can just use Newton-Raphson's method with an appropriate multiplier.

The idea is bizarrely simple, given a target composite T, where T=p_1*p_2, where the p's are large primes and p_1>p_2,

with m = [sqrt(T)] + 1, find residues r(n) = (n*m)^2 mod T, from n=1, to some relatively small number, like 1000 or 10000, and take the mean of r(n).

For approximately 50% of the cases the non-square quadratic residues for p_1 and p_2 will match, and for those case r(n) will tend to be LESS than p_2.

For the other approximately 50% of the cases the non-square quadratic residues for p_1 and p_2 will not match—or "bump" as I like to say—and for those cases r(n) will tend to be GREATER than p_2.

So the mean should approximately give p_2 itself!!!

What a remarkably simple idea for finding approximately what the value of p_2 is for large prime factors!!!

Anyone heard of this before? I've been brainstorming it out for, what, I think about, 16 hours now.

I'm curious about whether or not it's new.

Anyone wonder why it would be useful for factoring if you approximately new p_2? After all, you need to know it exactly, right?

Ok, short answer is that then you can just use Newton-Raphson's method with an appropriate multiplier.