Natural Science Forum / Physics / General Physics / March 2007

On 31 Mar, 19:03, "Douglas Eagleson" <eaglesondoug...@yahoo.com>
wrote:

How long would it take to factor RSA 704 with your method, using your
current CPU?

Here you have it
74037563479561712828046796097429573142593188889231
28908493623263897276503402826627689199641962511784
39958943305021275853701189680982867331732731089309
00552505116877063299072396380786710086096962537934
650563796359

Did you read James Harris latest surrogate factoring method how does
it relate to your idea?

Quote: James
Harris................................................................................
Abstracting to the gist of surrogate factoring I realized it says that
for every factorization of a composite T, with difference of squares

x2 ≡ y2 mod T
which of course is the same as, (x-y)(x+y) ≡ 0 mod T, and is for that
reason a factorization, there is an alternate factorization of an
integer S, where

S ≡ (α + 1)k2 mod T

and alpha and k are defined by

αk ≡ 2x mod T

as then trivially you can multiply both sides of that relation by k,
add back to the original difference of squares, add k2 to both sides
and find

(x+k)2 ≡ y2 + (α + 1)k2 mod T

explaining the second factorization, as now you have a factorization
of this alternate number using the same x, y and this
extra variable k:

(x+k - y)(x+k+y) ≡ (α + 1)k2 mod T

So for EVERY composite factorization of T using difference of square
that algebra tosses a factorization of ANOTHER composite (α + 1)k2 mod
T back at you!!!

It's just been there all the time. There has just been another
factorization out there all along with difference of squares and I
call the second factorization the surrogate factorization.

But hey, that goes both ways! I like to use T as the target, and S as
the surrogate, but what if you reverse the equations so that you pick
some surrogate and factor it to see how easily you can factor the
target T?

Equations then become

x2 ≡ y2 mod S and αk = 2x mod S gives you

(x+k)2 ≡ y2 + (α + 1)k2 mod S

and now, of course, you'd want to choose
(α + 1)k2 mod S ≡ 0 mod T

and you can go explicit to start solving everything, so I have

x2 ≡ y2 + aS

αk = 2x + u1S, so α = (2x + u1S)/k, and ((2x + u1S)/k + 1)k2 + (a
+u1k)S ≡ 0 mod T, so

2xk + 2u1Sk + k2 + aS ≡ 0 mod T

so you can collect to get
k2 + 2(x + u1S)k + u2S ≡ 0 mod T and now complete the square to get
(k + x + u1S)2 ≡ (x + u1S)2 + aS mod T

and now you have a fairly trivial way to solve for k, as u1  and aS
are integers of your choice, so you can, intriguingly enough, simply
CHOOSE two quadratic residues of T, and get their difference to
determine aS, and in that way determine x and y.  Then it's just a
matter of selecting u1 such that you get the first residue.

Let r1 and r2 be residues modulo T, and further let
aS = r22 - r12 so once you pick residues you can determine aS and then
find x and y, and then let

x + u1S ≡ r1 mod T

And you are free to pick u1 so now you can just solve for

u1 ≡ (r1 - x)(S)-1 mod T

and finally you can get k with
k + x + u1S ≡ r2 mod T

What makes this reversal fascinating to me is that it turns the
factoring problem on its head, where instead of searching for
quadratic residues modulo T, like most major factoring methods work to
do to solve the congruence of squares, you just pick pick them. You
pick quadratic residues of your target T, and use a surrogate
factorization to get a difference of squares with your target, so then
you should have a 50% chance of non-trivially factoring your target
with that choice,

(x+k)2 ≡ y2 + (α + 1)k2 mod S
as then also you will have an alternate factorization, the surrogate
factorization

(x+k)2 ≡ y2 mod T

as shown above with trivial algebra.

Quote: end James Harris

So will you implement your factorization method and James in Eiffel
Douglas?
How long would it take solve RSA 704 with your and James method
JT ;D