a) I have established three squares that equal RSA230(750 bit number).
b) I’m trying to use E. Catalan’s equation to reduce them to two squares, which would factor RSA230 (if it is 1 mod 4 semiprime)
c) I’ve had the solve[] command doing this run for a week on my Raspberry PI, to no answer, as most would expect.
My question is, if you look at the Solve command below
-
this solve command works in around 15 seconds for a 180 bit modulus. 200 bits is about the limit my Raspberry PI mathematica can factor. It is as if Mathematica is trying to factor a number, probably: 2 s == alpha^2 + beta^2 + sq3^2. After it factors this number it derive the 90 bit roots very quickly. For my RSA230 number, is Mathematica trying to factor a 750 bit number (as in above equation), and is this easier than the 750 RSA230 number, which is a hard semiprime. In other words, has the three squares equalling RSA230 and the use of Catalan’s equations transformed factoring RSA230 from a hard 750 bit semiprime factorisation to a theoretically easier 750 bit other type of number factorisation.
-
Or is Mathematica not trying to factor 2 s == alpha^2 + beta^2 + sq3^2, and is simply stuck enumerating through very large numbers looking for integer solutions, in which case Catalan’s equations are not helpful to factoring RSA230.
RSA230= 17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689
sq1 = 1059443675295336206903990032177460807418972848557933447798562577562645416414595037181025050793827302992107472819164
sq2 = 3776571573920219939515093763531383887422242718192208743361060316544426926673520279457864260379607843037554625909088
sq3 = 16076622294112434910748179495734459488112653361946457701785676314739439621472137233436060406493556443939160932757439
rt1 = IntegerPart[RSA230^(1/2)]
Solve[sq1 == x + alpha && sq2 == y - beta && x == s p + beta theta &&
y == s q + alpha theta && 2 s == alpha^2 + beta^2 + sq3^2 &&
beta q - alpha p == 1&&x>0&&y>0&&x<rt1&&y<rt1 && (GCD[alpha,beta]==1||GCD[alpha,beta]==-1), {x, y}, Integers]