### Tuesday, February 19, 2008

## Surrogate factoring and helper primes

The real story is that I was finishing out the theory on surrogate factoring.

z^2 = y^2 mod T

I wondered a few years ago if there weren't another way where you could connect factorizations, and after years of research I've found that with

z^2 = y^2 + nT,

where n is some non-zero integer I can add a few more variables using

z = x+αk, so

(x+αk)2 = y^2 + nT

and if you have k and α, and if k = 2αx then you find

x^2 = y^2 + nT - (1 + α^2)k^2.

You may recall I talked a lot recently about factors mod p, where p is an odd prime, as now is where helper primes come in allowing you to solve for k modulo p:

k^2 = (α^2+1)^{-1}(nT) mod p.

So how did I introduce prime p? Actually with

2αx = k + pr_2

so the full equation is actually

x^2 = y^2 + nT - (1 + α^2)k^2 + kpr_2

but if you find k such that the absolute value of nT - (1 + α^2)k^2 is a minimum, then you minimize the absolute value of r_2 as well, and make it 0.

So the primes help you find the factorization and then vanish without a trace, which is why I call them helper primes.

To see one in operation, let T=119 and n=1, and p = 3.

Then

k^2 = (α^2+1)^{-1}(nT) mod p = (α^2+1)^{-1}(119) mod 3.

And α = 1 works giving k^2 = 1 mod 3, so I can use any integer k coprime to 3.

And finding k such that the absolute value of 119 - 2k^2 is a minimum gives k=8.

Then I have x = 4, just like that, and substituting

16 = y^2 + 119 - 128 = y^2 - 9

so y = 5, and

z = x + αk = 4 + 8 = 12, and z-y = 12-5 = 7, and z+y = 12+5 = 17.

Notice that p=3 just helped and then vanished without a trace.

And yes, it IS possible than an RSA public key could be factored by p=3.

However you can just as well get a trivial factorization, or find that you can't use 3, as nT mod 3 must equal 2. But then you can use p=5. Or p = 7.

Or any odd prime that you liked until you broke it as the math does not care.

It is unlikely that you would need a large prime for a composite of only two prime factors.

Surrogate factoring exploits the fact that every composite factorization is connected to an infinity of other factorizations, so you can use those factorizations to factor your target.

Mathematicians focused primarily on congruences of squares that made the target the modulus while I ranged beyond that exploring an idea.

Surrogate factoring was a concept that is now a fully fleshed out theory.

z^2 = y^2 mod T

I wondered a few years ago if there weren't another way where you could connect factorizations, and after years of research I've found that with

z^2 = y^2 + nT,

where n is some non-zero integer I can add a few more variables using

z = x+αk, so

(x+αk)2 = y^2 + nT

and if you have k and α, and if k = 2αx then you find

x^2 = y^2 + nT - (1 + α^2)k^2.

You may recall I talked a lot recently about factors mod p, where p is an odd prime, as now is where helper primes come in allowing you to solve for k modulo p:

k^2 = (α^2+1)^{-1}(nT) mod p.

So how did I introduce prime p? Actually with

2αx = k + pr_2

so the full equation is actually

x^2 = y^2 + nT - (1 + α^2)k^2 + kpr_2

but if you find k such that the absolute value of nT - (1 + α^2)k^2 is a minimum, then you minimize the absolute value of r_2 as well, and make it 0.

So the primes help you find the factorization and then vanish without a trace, which is why I call them helper primes.

To see one in operation, let T=119 and n=1, and p = 3.

Then

k^2 = (α^2+1)^{-1}(nT) mod p = (α^2+1)^{-1}(119) mod 3.

And α = 1 works giving k^2 = 1 mod 3, so I can use any integer k coprime to 3.

And finding k such that the absolute value of 119 - 2k^2 is a minimum gives k=8.

Then I have x = 4, just like that, and substituting

16 = y^2 + 119 - 128 = y^2 - 9

so y = 5, and

z = x + αk = 4 + 8 = 12, and z-y = 12-5 = 7, and z+y = 12+5 = 17.

Notice that p=3 just helped and then vanished without a trace.

And yes, it IS possible than an RSA public key could be factored by p=3.

However you can just as well get a trivial factorization, or find that you can't use 3, as nT mod 3 must equal 2. But then you can use p=5. Or p = 7.

Or any odd prime that you liked until you broke it as the math does not care.

It is unlikely that you would need a large prime for a composite of only two prime factors.

Surrogate factoring exploits the fact that every composite factorization is connected to an infinity of other factorizations, so you can use those factorizations to factor your target.

Mathematicians focused primarily on congruences of squares that made the target the modulus while I ranged beyond that exploring an idea.

Surrogate factoring was a concept that is now a fully fleshed out theory.