Jump to content

Is this a factor?


Trurl

Recommended Posts

I know the moderators don’t like it when I post blocks of numbers.

However, I am only asking if this number is the correct factor. I know I should know if I could actually factor. But to prove my method I tried to factor a 2048 bit number. This is what I got in about 15 minutes work.

 

1.165633406571949X10^409

 

Is the smallest factor of

 

5.998490465869536X10^615

 

 

Need more accuracy

 

Let me know if I have successfully factored

 

So so I need more digits accuracy than just 15 digits. 

But this gives the first 16 digits and the magnitude of 1.1*10^409.

So it does eliminate possibilities. Not perfect, but let me know if it is close.

Link to comment
Share on other sites

6 hours ago, Trurl said:

1.165633406571949X10^409

 

Is the smallest factor of

 

5.998490465869536X10^615

I'm probably missing something. I thought that the smallest factor of [math]5.998490465869536*10^{615}[/math], except for 1, is 2 ?  

 

Edited by Ghideon
Link to comment
Share on other sites

8 hours ago, Trurl said:

However, I am only asking if this number is the correct factor. I know I should know if I could actually factor. But to prove my method I tried to factor a 2048 bit number. This is what I got in about 15 minutes work.

You can't factor large numbers like this using floating point arithmetic. Which is what you seem to be doing, unless these two numbers really do both end in hundreds of zeros.

Link to comment
Share on other sites

14 hours ago, Trurl said:

So so I need more digits accuracy than just 15 digits. 

You need the all digits.. 

 

If you have binary integer like 2^x-1

e.g. %11111111 (x=8) (decimal 255)

and x can be factored,

it is easy to calculate if number has factors and what they are.

Because they will be made of series of digits like for example (pattern is visible in binary format):

%00010001 * %1111 = %11111111 (decimal 17*15=255)

%01010101 * %11 = %11111111 (decimal 85*3=255)

When x is prime number you can use technique used during calculation of Mersenne prime number 

https://en.m.wikipedia.org/wiki/Mersenne_prime

 

Edited by Sensei
Link to comment
Share on other sites

15 hours ago, Trurl said:

Need more accuracy

So it does eliminate possibilities. Not perfect, but let me know if it is close.

You yourself call it a `2048 bit number'. Which means that it can be written in binary notation as a string of 0's and 1's of length 2048. Now observe that to decide whether 2 is a factor or not, the first 2047 bits have nothing to say about it whatsoever. The only thing that matters is whether the final 2048'th bit is a 0 or a 1. To decide whether 2 is the smallest non-trivial factor (one that is larger than 1) is the same thing as to decide whether 2 is a factor at all. If you write the same number in usual decimal notation, all that matters again is to be able to decide whether the last digit is an even or odd digit. The point being that the `most significant' digits may be the most useless when you try to decide about factorization. 

Link to comment
Share on other sites

3 hours ago, taeto said:

You yourself call it a `2048 bit number'. Which means that it can be written in binary notation as a string of 0's and 1's of length 2048. Now observe that to decide whether 2 is a factor or not, the first 2047 bits have nothing to say about it whatsoever. The only thing that matters is whether the final 2048'th bit is a 0 or a 1. To decide whether 2 is the smallest non-trivial factor (one that is larger than 1) is the same thing as to decide whether 2 is a factor at all. If you write the same number in usual decimal notation, all that matters again is to be able to decide whether the last digit is an even or odd digit. The point being that the `most significant' digits may be the most useless when you try to decide about factorization. 

I think it is me calling it the wrong thing. I still confuse how many bits a key is long. But I have the number I used here in this post. If I can get the digits of accuracy I believe I can factor this number. I know I can factor smaller numbers within a margin of error. But to prove I can factor I have to break this number. That is why when I said "the right magnitude" I mean the factor will occur at 410 digits. Obviously that is a lot still to use recursion to divide. But if I can maintain the entire 410 digit number I could factor within a smaller margin of error.

You see the only way to prove that I can factor is to factor a large number. But large semi-Primes are hard to find. And yes the nomenclature of this math confuses me. But I hope to clear it up in this post.

 

5998490465869535958493457351726585769768780414997827819458162457365131\

2784688425167331506121500202224441992715357138367051061653638169409727\

8529613415310827009512503742906575348939074378824943398287900272839718\

1012226608631723752258738079635407385665857943917136911564807480973854\

0477603441448614459671016259991520028750578991648135327261214372672798\

0903767703277168633339347967002362666965628644859661675221629352149974\

9737800846524363691459902238665732702744582185179531226365443974338304\

5939787842818642200160191894955133225326542363885702300787221019449943\

58570309218509180305727137122851736117179378654706701977

 

 

 

This is the semi-Prime I used.

 

You are right that it is shortening my value in Mathematica and making it displayed as a float point. But the thing is Mathematica does have the precision. I tried to get to use the accuracy, but even though Mathematica can have the accuracy, it again comes out in scientific notation.

But did I make the magnitude? I am saying that 1.165633406571949 is the first 16 digits or the smallest factor that has 410 digits.

So if anyone knows anything about Mathematica and how to keep the precision let me know.

Link to comment
Share on other sites

7 minutes ago, Trurl said:

Obviously that is a lot still to use recursion to divide. But if I can maintain the entire 410 digit number I could factor within a smaller margin of error.

The only way to do the calculation without losing accuracy is to use large enough integer values. A 410 (decimal) digit number requires about 1400 bits to represent it. There are arithmetic libraries for most languages (Python, C#, etc) for doing this sort of thing. Or there are math applications that can handle arbitrary precision arithmetic.

https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software

19 minutes ago, Trurl said:

So if anyone knows anything about Mathematica and how to keep the precision let me know.

Sorry, didn't see this bit before.

This might be what you want: https://uk.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic

Link to comment
Share on other sites

9 hours ago, Trurl said:

You are right that it is shortening my value in Mathematica and making it displayed as a float point. But the thing is Mathematica does have the precision. I tried to get to use the accuracy, but even though Mathematica can have the accuracy, it again comes out in scientific notation.

But did I make the magnitude? I am saying that 1.165633406571949 is the first 16 digits or the smallest factor that has 410 digits.

So if anyone knows anything about Mathematica and how to keep the precision let me know.

So far as I understand it, you have to avoid setting any accuracy in Mathematica. The computations are supposed to be exact by default. It is if you set a degree of accuracy that the calculations are not made exactly, but only to the degree of precision that you require. The relevant documentation page is reference.wolfram.com/language/guide/PrecisionAndAccuracyControl.html . I admit that the documentation is not always easy to read.

I hope that when we talk about factorization here, the aim is to express your given number as a product of smaller natural numbers? You suggested that your 615-digit number has a factor which is a 410-digit number. There must be other factors in the factorization, what are they? 

Edited by taeto
Link to comment
Share on other sites

Well I found the reason I couldn't get accuracy was because you have to have the accuracy in all numbers you use. For example when I plugged it into the equation and say divide by q, q needed more "accuracy". It makes sense but makes it more difficult. But I will post my numbers here. Tell me if I am in reasonable estimate. It is probably guaranteed to fail, but I did put some effort and though into it. Here I used the full size. Also there is a normal distribution between PNP and estimated PNP. This normal distribution will help when guessing q. Yes, you are guessing q, but it is an educated guess. But if I did do a correct factorization this should equal the smaller semi-Prime. But there are no guarantees in math, especially when I wield the chalk.

 

 

In[87]:= PNP = \
5998490465869535958493457351726585769768780414997827819458162457365131\
2784688425167331506121500202224441992715357138367051061653638169409727\
8529613415310827009512503742906575348939074378824943398287900272839718\
1012226608631723752258738079635407385665857943917136911564807480973854\
0477603441448614459671016259991520028750578991648135327261214372672798\
0903767703277168633339347967002362666965628644859661675221629352149974\
9737800846524363691459902238665732702744582185179531226365443974338304\
5939787842818642200160191894955133225326542363885702300787221019449943\
58570309218509180305727137122851736117179378654706701977

q = 100111140657194927673100202970050001121410737599782781945816245736\
5131278468842516733150612150020222444199271535713836705106165363816940\
9727852961341531082700951250374290657534893907437882494339828790027283\
9718101222660863172375225873807963540738566585794391713691156480748097\
3854047760344144861445967101625999152002875057899164813532726121437267\
2798090376770327716863333305727137122851736117179378654706701977

(Sqrt[((((q^2 * PNP^4 + 2* PNP^2 * q^5) + q^8) / 
      PNP^4) * ((PNP^2/ q^2)))])




Out[87]= 5998490465869535958493457351726585769768780414997827819458162\
4573651312784688425167331506121500202224441992715357138367051061653638\
1694097278529613415310827009512503742906575348939074378824943398287900\
2728397181012226608631723752258738079635407385665857943917136911564807\
4809738540477603441448614459671016259991520028750578991648135327261214\
3726727980903767703277168633339347967002362666965628644859661675221629\
3521499749737800846524363691459902238665732702744582185179531226365443\
9743383045939787842818642200160191894955133225326542363885702300787221\
01944994358570309218509180305727137122851736117179378654706701977

Out[88]= 1001111406571949276731002029700500011214107375997827819458162\
4573651312784688425167331506121500202224441992715357138367051061653638\
1694097278529613415310827009512503742906575348939074378824943398287900\
2728397181012226608631723752258738079635407385665857943917136911564807\
4809738540477603441448614459671016259991520028750578991648135327261214\
372672798090376770327716863333305727137122851736117179378654706701977

Out[89]= 3598289120705448492680059328834150322334448001622207912714128\
6270306210690982540842543166403185241528795593766557486803136707938239\
9271568942784642138646253353005635251855229982611082096617495327278988\
6034138314595363712227903179098321332099042432094688889127255335934193\
9910144822398803499036502791144788509725289029463011569872361246547341\
6704558693865441793928494373571600592379630273961383590475105039969803\
4486006253937796053837292199526847062983929041955904851574667653698032\
3857793905098071574856310703189698344331355376605289838666116963502002\
6997060484687691461523482749370524184741214446654994931729474157718575\
2841702466111288399698046811183489665378322814876150691592558659206780\
2286418935629292572033313994010480687164705289161159744459388883459593\
5417694325251091407974625486305114294619946100659923237342349281588128\
5015922425899569331395553047909343109656577179687855701640487791877470\
2183218224730158957774351157867826711168016592832118240706695248547427\
3761140291569496246525045715862623693727981640129087695758751448931583\
9404145850115356336230295181816945324724356322936413641186755171066366\
3522872281703641670265347320445417438356191517766072467035543617922477\
292918483946522593224083703496041911554568355770362/\
5998490465869535958493457351726585769768780414997827819458162457365131\
2784688425167331506121500202224441992715357138367051061653638169409727\
8529613415310827009512503742906575348939074378824943398287900272839718\
1012226608631723752258738079635407385665857943917136911564807480973854\
0477603441448614459671016259991520028750578991648135327261214372672798\
0903767703277168633339347967002362666965628644859661675221629352149974\
9737800846524363691459902238665732702744582185179531226365443974338304\
5939787842818642200160191894955133225326542363885702300787221019449943\
58570309218509180305727137122851736117179378654706701977

In[90]:= 



PNP - 3598289120705448492680059328834150322334448001622207912714128627\
0306210690982540842543166403185241528795593766557486803136707938239927\
1568942784642138646253353005635251855229982611082096617495327278988603\
4138314595363712227903179098321332099042432094688889127255335934193991\
0144822398803499036502791144788509725289029463011569872361246547341670\
4558693865441793928494373571600592379630273961383590475105039969803448\
6006253937796053837292199526847062983929041955904851574667653698032385\
7793905098071574856310703189698344331355376605289838666116963502002699\
7060484687691461523482749370524184741214446654994931729474157718575284\
1702466111288399698046811183489665378322814876150691592558659206780228\
6418935629292572033313994010480687164705289161159744459388883459593541\
7694325251091407974625486305114294619946100659923237342349281588128501\
5922425899569331395553047909343109656577179687855701640487791877470218\
3218224730158957774351157867826711168016592832118240706695248547427376\
1140291569496246525045715862623693727981640129087695758751448931583940\
4145850115356336230295181816945324724356322936413641186755171066366352\
2872281703641670265347320445417438356191517766072467035543617922477292\
918483946522593224083703496041911554568355770362/
  59984904658695359584934573517265857697687804149978278194581624573651\
3127846884251673315061215002022244419927153571383670510616536381694097\
2785296134153108270095125037429065753489390743788249433982879002728397\
1810122266086317237522587380796354073856658579439171369115648074809738\
5404776034414486144596710162599915200287505789916481353272612143726727\
9809037677032771686333393479670023626669656286448596616752216293521499\
7497378008465243636914599022386657327027445821851795312263654439743383\
0459397878428186422001601918949551332253265423638857023007872210194499\
4358570309218509180305727137122851736117179378654706701977

Out[90]= -(\
1003337926762389049221126796215583044111287392509572407957361630075276\
9505131574604802375389492124492898548849744921866438826479970845253166\
5286371164639751196966576858129600921807606026358615662532610138182538\
3636765498759821676246069237032957534374432336610334560127204527283356\
3999143594559687482446004256128329553814501088092018965233439791910082\
2846991619424657099049350300585147978932265245231395879838950171324512\
2970817464138978364753024470618424771102246294259091573015051471283229\
1081100169373970495499690724467160987209063036567035108939022149134886\
2517355182826636423935614329522097000601647962594541064070461627390134\
7536657230472436382754096021417129062587067688590412252385403913508714\
1961325083408245209320940098986654344561959190907809042686958196441030\
3899437797648943140246355017712110654807887087624921809884308040202223\
9996383269290296202903487456758097609903645061411424222739152682711747\
0322353005743890894510415982298620570596253483316856775695754866581314\
3664508949852483173726698633100818473785829707870858896643911724929114\
4859482370915211019498575494065439836529883870306766859074115080141713\
8666208933121978732291153355129507645934297155764596339013578313268902\
46560926762406703208585328968060061833/
   5998490465869535958493457351726585769768780414997827819458162457365\
1312784688425167331506121500202224441992715357138367051061653638169409\
7278529613415310827009512503742906575348939074378824943398287900272839\
7181012226608631723752258738079635407385665857943917136911564807480973\
8540477603441448614459671016259991520028750578991648135327261214372672\
7980903767703277168633339347967002362666965628644859661675221629352149\
9749737800846524363691459902238665732702744582185179531226365443974338\
3045939787842818642200160191894955133225326542363885702300787221019449\
94358570309218509180305727137122851736117179378654706701977)

In[91]:= 


q - (10033379267623890492211267962155830441112873925095724079573616300\
7527695051315746048023753894921244928985488497449218664388264799708452\
5316652863711646397511969665768581296009218076060263586156625326101381\
8253836367654987598216762460692370329575343744323366103345601272045272\
8335639991435945596874824460042561283295538145010880920189652334397919\
1008228469916194246570990493503005851479789322652452313958798389501713\
2451229708174641389783647530244706184247711022462942590915730150514712\
8322910811001693739704954996907244671609872090630365670351089390221491\
3488625173551828266364239356143295220970006016479625945410640704616273\
9013475366572304724363827540960214171290625870676885904122523854039135\
0871419613250834082452093209400989866543445619591909078090426869581964\
4103038994377976489431402463550177121106548078870876249218098843080402\
0222399963832692902962029034874567580976099036450614114242227391526827\
1174703223530057438908945104159822986205705962534833168567756957548665\
8131436645089498524831737266986331008184737858297078708588966439117249\
2911448594823709152110194985754940654398365298838703067668590741150801\
4171386662089331219787322911533551295076459342971557645963390135783132\
6890246560926762406703208585328968060061833/
    599849046586953595849345735172658576976878041499782781945816245736\
5131278468842516733150612150020222444199271535713836705106165363816940\
9727852961341531082700951250374290657534893907437882494339828790027283\
9718101222660863172375225873807963540738566585794391713691156480748097\
3854047760344144861445967101625999152002875057899164813532726121437267\
2798090376770327716863333934796700236266696562864485966167522162935214\
9974973780084652436369145990223866573270274458218517953122636544397433\
8304593978784281864220016019189495513322532654236388570230078722101944\
994358570309218509180305727137122851736117179378654706701977) / q 

Out[91]= 6005157227595078439406835238794066464166217361556872908440991\
1282976544749217352966095305064260976131204390106416093998394042208854\
7593647838596486806269285487124538411876902031290465184358522934882710\
7468932015125430085020735266385041418658401844011223865199560944341434\
4382977176112915945427311858818259246049722738902468149157934513552061\
9997688297974236046666408569893388019019418263378453571233264289205298\
0480472873653140396089108178522939945009442689406711806507044965048418\
8748542472073681797599573830861480964578658197776249730088320427676273\
6418233713375287621166773563131993803042568857955930966082301794497535\
4422340480161776806362976983653377730194820252303936196500528833754719\
9077913968987780900871348721284098276417837541324502971810887802119298\
3741091413474024436422904784647114333872970673475514338028366026036503\
6450734925328262248208337288071391792959821279837279132465988631047083\
9237550307052196288077036452576036598708270768314556635456479313448765\
326486828739519000000000000000000000000000000000000000/\
5998490465869535958493457351726585769768780414997827819458162457365131\
2784688425167331506121500202224441992715357138367051061653638169409727\
8529613415310827009512503742906575348939074378824943398287900272839718\
1012226608631723752258738079635407385665857943917136911564807480973854\
0477603441448614459671016259991520028750578991648135327261214372672798\
0903767703277168633339347967002362666965628644859661675221629352149974\
9737800846524363691459902238665732702744582185179531226365443974338304\
5939787842818642200160191894955133225326542363885702300787221019449943\
58570309218509180305727137122851736117179378654706701977

In[92]:= N[%91]

Out[92]= 1.001111406571949*10^409

smallest factor

 

Link to comment
Share on other sites

1.00111140657194927673100202970050001121410737599782781945816245736513\
1278468842516733150612150020222444199271535713836705106165363816940972\
7852961341531082700951250374290657534893907437882494339828790027283967\
8323968773124658157519009514402613556863757843081318031549066464063464\
8903637088626834871049426813651449824514934961323715586782698519267036\
4136957297127727185659878862942307510915960740199425171606099*10^409

This is just to clear up the difficulty reading all the input. This is my best work. I believe it is a factor in many 2048 bit Primes.

2048 was worth $200,000. To bad the prize expired, but I still want to decipher this.

So as I mentioned earlier in the post the moderators don't like me posting endless code. Here is my best work so far.ou

It should be close to the integer that factors the 2048 bit number. But if someone could verify this I would appreciate the help.

And I looked it up the product is a 2048 bit number. It has 617 digits. And if you can break a 2048 number RSA is compromised. But we must see if it works first.

Link to comment
Share on other sites

4 hours ago, Trurl said:

1.00111140657194927673100202970050001121410737599782781945816245736513\
1278468842516733150612150020222444199271535713836705106165363816940972\
7852961341531082700951250374290657534893907437882494339828790027283967\
8323968773124658157519009514402613556863757843081318031549066464063464\
8903637088626834871049426813651449824514934961323715586782698519267036\
4136957297127727185659878862942307510915960740199425171606099*10^409

It should be close to the integer that factors the 2048 bit number. But if someone could verify this I would appreciate the help.

The number in this quote is your q, right? It is an integer, so why is it represented in floating point? Are you suggesting that this number is a factor of PNP, or are you now saying that it is just  "close" to some factor? If it is close to a factor, do you agree that PNP/q (that is, PNP divided by q) is also close to a factor? 

Link to comment
Share on other sites

Yes if q is close PNP/q would also be close.

I am only guessing at q. It comes close to the smallest factor of PNP. The remaining factor should also be close. But the error would be slightly greater.

But I do have equation for the larger factor also.

I put it in scientific notation so that it is easier to read. I like seeing the magnitude, like 409.

I am doing semiPrimes but I don’t see a reason it can’t be used to factor any number.

 

You can help by giving me large PNP’s to test. I only have 3 such numbers.

Again this number needs verified. Some people own the factors. I have to find a method to verify. Finding the larger factor, even by division is a good place to start.

Link to comment
Share on other sites

1 hour ago, Trurl said:

Yes if q is close PNP/q would also be close.

I am only guessing at q. It comes close to the smallest factor of PNP. The remaining factor should also be close. But the error would be slightly greater.

But I do have equation for the larger factor also.

I put it in scientific notation so that it is easier to read. I like seeing the magnitude, like 409.

Now since PNP is \(\sim 10^{615}\) and \(q\sim 10^{410}\) we have that the ratio PNP/\(q\) is \(\sim 10^{205},\) correct, at least roughly to order of magnitude?

In your calculations that you posted before, starting from In[87] and ending with Out[92], what would happen if you had replaced your value of q by some other value, say \(q = 10^{500},\) and you had done exactly the same calculations. What would become different? In particular, based on those same calculations with the new value of q, would you again tend to conclude that \(10^{500}\) is also close to a factor of PNP? 

Edited by taeto
Link to comment
Share on other sites

If you change q then PNP actual will not equal PNP estimate.

This equation is PNP estimate:

 

(Sqrt[((((q^2 * PNP^4 + 2* PNP^2 * q^5) + q^8) / 
      PNP^4) * ((PNP^2/ q^2)))])

 

I subtract it by the actual PNP. N = N or 0 =0

q is imputed as a guess. Large numbers but usually less than 10 guess to get the right magnitude.

If you change PNP to some other integer you get a different answer. You can experiment. Follow the fist set of code and substitute different n and q.

(Sqrt[((((q^2 * PNP^4 + 2* PNP^2 * q^5) + q^8) / 
      PNP^4) * ((PNP^2/ q^2)))])

 

It should give the location of the least factor of any PNP

Link to comment
Share on other sites

Well I think this guess is relatively close to the smaller factor. Notice that I gave you a way to recreate the work. I also gave you a way to check y=(PNP^2/q) + q^2)/ PNP

Does anyone know what the actual PNP is? I can approximate but when dealing with such a large number it is difficult for me to have a check without error.

The next step is statistics. N - Nguess If you graph the N minus the guess N there is a Bell Curve (The normal distribution). This distribution also allows the use of calculus to make better math structured guesses.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.