Message Boards Message Boards

Is Solve[] command trying to factor a 750 bit number when it may not haveto

GROUPS:

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 1) 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.

2) 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]
POSTED BY: Paul Cheffers
Answer
27 days ago

Group Abstract Group Abstract