Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Testing the Fermat two perfect square factoring method with a large semi-pr
Replies: 1   Last Post: Sep 14, 2012 7:13 AM

 Messages: [ Previous | Next ]
 dan73 Posts: 468 From: ct Registered: 6/14/08
Testing the Fermat two perfect square factoring method with a large semi-pr
Posted: Sep 13, 2012 10:08 PM

Testing the Fermat two perfect square factoring method with a large semi-prime composite.

This also proves both divisors are prime by finding the smallest perfect square.

Two primes that equal a composite that
resides on the same index in the triangle number
matrix as rsa2048 so this semi-prime composite is
called rsa2048a.

The two prime factors of rsa2048a =
1.39217341082921058677288768867238372573809795563710257489517055857993201220738681318910991346780329416529302048744061453625778120956967353310289415912208309060801996693275531345613622629039095337902228625313915337784981965401853830542389780277063595193710164147516684113360149151676539190751701045063944086637e+308
*
1.80982543407797376280475399527409884345952734232823334736372172615391161586960285714584288750814428241488092663367279889713511557244057559303376240685870784312935129353118487664347505039969641698745529780023658648477844394503316445073776083703194466034321212888030425307656471216317798428381146383995799130021e+308

Testing these for the Fermat perfect square method
to see if Python can handle finding perfect squares this
large.

The semi-prime composite and its square root =
2.5195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952616748956511060786683768720836984004964129263675822930808863122985917441516894744288970788437001065808221249142714385792119936134975231968672483221759112051629377e+616
1.58732191050391204174482508661063007579358463444809715795726627753579970080749948404278643259568101132671402056190021464753419480472816840646168575222628934671405739213477439533870489791038973166834068736234020361664820266987726919453356824138007381985796493621233035112849373047484148339095287142097834807844e+308
gap between the two primes /2
=
2.0882601162438158801593315330085755886071469334556538623427558378698980183110802197836648702017049412479395307311609218043866718143545102996543412386831237626066566329921478159366941205465273180421650577354871655346431214550731307265693151713065435420305524370256870597148161032320629618814722669465927521692e+307
^2 + above composite =
target largest square =
2.5631991506967357035269961411510774700550173547619101812873280606282879247989073171660895769597951829345722594655756689381036418826758080003818636047151028525677428842770690723666642659217452131225042535267070420255957647538390327737960253183214673563123685735437541727804749212928885800417489377903151755506402938017771884007676753712695657299451132255427076104353593097922900466138116336085863287056818610151753538334486737637454311315170958593286947727043396211486320107402333012527939392725415569139792153231212444988852162426507869986694186763262562698082276565570902554507488585996504305268494949125161182172241e+616
square root it =
1.60099942245359217478882084197324128459881264898266796112944614236692181403849483516747640048797378829008697356055670671669644839100512456306832828299039546686868563023197009504980563834504368518323879202668786993131413179952585137808082931990129030614015688517773554710508310183997168809566423714529871608329e+308
-1000000 for a starting point of the test =

(a,b,c) are the only starting variables in my Python code
a =
1.60099942245359217478882084197324128459881264898266796112944614236692181403849483516747640048797378829008697356055670671669644839100512456306832828299039546686868563023197009504980563834504368518323879202668786993131413179952585137808082931990129030614015688517773554710508310183997168809566423714529870608329e+308
b =
4.36083031309463541242778171462376129120891421415069785096142770239217227281477615396877243717167422427431953406241607191737859677581895501010146927078183532990036035482913987695224311947190234850027563442379255178344267679294627640629793434406245161326256634795083035987554094182764285244834745620934565318969264876903288984423217198976693960122912334650075767204379779323507943346801642641950681624350141096664120936941778671519976446114741093725934695333273517849212926699554330563286379024249657705563884848363059176574815739337509531859418068200268858483991875747095745767184456683653203748582667623832472542864e+614
c =
3.20199884490718434957764168394648256919762529796533592225889228473384362807698967033495280097594757658017394712111341343339289678201024912613665656598079093373737126046394019009961127669008737036647758405337573986262826359905170275616165863980258061228031377035547109421016620367994337619132847429059741216659e+308

a = the starting point is much > sqrt(rsa2048a)
b = sum that will eventually leads to a perfect square.
c = the progressive gap of +2 between the terms in b.

Making this and all Fermat perfect square test in any
semi-prime calculation where sequence (b) is a
3rd degree monic polynomial.

A print out of the results that proves both divisors
are prime and the smallest perfect square (b) is also
found along with (a) when squared (-) the
semi-prime = (b).

The listed results with the only key paramiters (a,b,c) =
a=
160099942245359217478882084197324128459881264898266796112944614236692181403849483516747640048797378829008697356055670671669644839100512456306832828299039546686868563023197009504980563834504368518323879202668786993131413179952585137808082931990129030614015688517773554710508310183997168809566423714529871608329
b=
436083031309463541242778171462376129120891421415069785096142770239217227281477615396877243717167422427431953406241607191737859677581895501010146927078183532990036035482913987695224311947190234850027563442379255178344267679294627640629793434406245161326256634795083035987554094182764285244834745620934885518853755595338246748591611847233613722652708868242301656432853163686315642313835137922048276382008158491376232278285117961198177471027354759382532774426647254975259320718564291690955387761286305463969222422349322002934720909613125697723398326261496889861027422856516762387552451021272336596011727366049130542864
c=
320199884490718434957764168394648256919762529796533592225889228473384362807698967033495280097594757658017394712111341343339289678201024912613665656598079093373737126046394019009961127669008737036647758405337573986262826359905170275616165863980258061228031377035547109421016620367994337619132847429059743216659
Total number of passes = 1000001

Where a^2 - rsa2048a = (b) and (b) = a perfect square.
(b) + rsa2048a = a^2

How large an integer can Python or any other programming
language handle to find perfect squares without
producing any false positives?

Without gmpy, this would not be possible in Python.

This semi-prime rsa2048a has 617 digits.

My next test involve two semi-prime composites that
have both large and small primes that are very
close to each other and will appear in the same
test that will produce a total of four prime factors
for both semi-primes.

Dan

Date Subject Author
9/13/12 dan73
9/14/12 dan73