math gcd problem need help

[Dr Sardonicus]

Hmm, cryptoworks... google google... like this?

The modules SPM-PS/ CryptoWorks/Conax, SPM-PST/ CryptoWorks/Conax and SPM-PSI are DVB-S reception modules for the conversion of QPSK modulated programs into AV signals. Afterwards the AV signal is converted into a TV channel by a modulator from the SPM series. The modulator is connected with the inserted digital module by a Sub-D connection.

Er, ah, what's the purpose for your question?

[crack11]

yes DR Sardonicus sir same crypto/conax cabletv scrambled system need calculating gcd please help me to solve this issu..

Thanks

[Dr Sardonicus]

Originally Posted by crack11

yes DR Sardonicus sir same crypto/conax cabletv scrambled system need calculating gcd please help me to solve this issu..

Thanks

And what, pray tell, do you "need" this for, exactly? Given the Cryptoworks hardware in question, my concern is that the computation is for something illegal, like a DIY descrambler to avoid paying for for pay TV.

Your gcd problem appears to be for the purpose of determining an unknown RSA modulus. For that purpose, it is theoretically sound, assuming you know the input, the exponent, and the output. But the only situation I could envision in which you might know both the input and output of an RSA cipher but not the modulus was, if the computation was being done by some sort of proprietary device, which the user would basically have to view as a "black box." I am having difficulty imagining how you would know the exponent but not the modulus in that situation, but then I didn't read the manual. The exponent might be accessible, I dunno.

I am also at a bit of a loss as to why you want the gcd for three integers, rather than two.

In any case, there is no way to solve your gcd problem with the exponent 17592186175489 by brute-force computation. The numbers are just way too big. This has already been pointed out. So please quit asking for help with this calculation.

P.S. I ran a gcd calculation with just two of the integers in your example with exponent 65537, and got the same answer you got from the gcd of three integers. The computation took a little over 40 minutes on my old computer.

? gcd(7580104959982914109394378405621081680045277328933902877018950173722431866047182165909685701898461476201769271496346873969218041590426190558248064238412-5542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^65537,
7580104959982914109394378405621081680045277328933902557064898247755957479231576299665165903124564064889635003580310606233252493957322555511313835652894-2210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^65537)

%1 = 9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891

[CRGreathouse]

Originally Posted by Dr Sardonicus

P.S. I ran a gcd calculation with just two of the integers in your example with exponent 65537, and got the same answer you got from the gcd of three integers. The computation took a little over 40 minutes on my old computer.

? gcd(7580104959982914109394378405621081680045277328933902877018950173722431866047182165909685701898461476201769271496346873969218041590426190558248064238412-5542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^65537,
7580104959982914109394378405621081680045277328933902557064898247755957479231576299665165903124564064889635003580310606233252493957322555511313835652894-2210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^65537)

%1 = 9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891

You did all the hard work, once you have that it's easy to find the full GCD:

G2=9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891;
Z3mod=7580104959982914380707737866198974081289603526426728444663905520185161944615556517456155284414829089801734045676331442459189567878379004868410811939884-Mod(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572,G2)^65537;
G3=gcd(lift(Z3mod),G2)

But of course you already did this when you checked that the given GCD divides all three numbers.

[EdH]

What am I missing? YAFU can solve gcd of all three smaller exponent elements in less than a minute:

$ cd Math/yafu
[duser@localhost yafu]$ date;./yafu;date
Thu Sep 21 15:43:46 EDT 2017


09/21/17 15:43:46 v1.35-beta @ localhost.localdomain, System/Build Info: 
Using GMP-ECM 7.0.3, Powered by GMP 6.1.1
detected AMD Athlon(tm) 64 X2 Dual Core Processor 6000+
detected L1 = 65536 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 2110.076610
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> gcd((7580104959982914109394378405621081680045277328933902877018950173722431866047182165909685701898461476201769271496346873969218041590426190558248064238412-(5542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^65537)),(7580104959982914109394378405621081680045277328933902557064898247755957479231576299665165903124564064889635003580310606233252493957322555511313835652894-(2210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^65537)),(7580104959982914380707737866198974081289603526426728444663905520185161944615556517456155284414829089801734045676331442459189567878379004868410811939884-(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572^65537)))

9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891
>> quit
Thu Sep 21 15:44:26 EDT 2017

Yet, the larger exponent kills gmp within two seconds.

$ date;./yafu;date
Thu Sep 21 15:48:30 EDT 2017


09/21/17 15:48:30 v1.35-beta @ localhost.localdomain, System/Build Info: 
Using GMP-ECM 7.0.3, Powered by GMP 6.1.1
detected AMD Athlon(tm) 64 X2 Dual Core Processor 6000+
detected L1 = 65536 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 1540.776870
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> gcd((7580104959982914109394378405621081680045277328933902877018950173722431866047182165909685701898461476201769271496346873969218041590426190558248064238412-(5542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^17592186175489)),(7580104959982914109394378405621081680045277328933902557064898247755957479231576299665165903124564064889635003580310606233252493957322555511313835652894-(2210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^17592186175489)),(7580104959982914380707737866198974081289603526426728444663905520185161944615556517456155284414829089801734045676331442459189567878379004868410811939884-(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572^17592186175489)))

gmp: overflow in mpz type
Aborted (core dumped)
Thu Sep 21 15:48:32 EDT 2017

Perhaps I should slink away and not bother you guys...

[bsquared]

Originally Posted by EdH

What am I missing? YAFU can solve gcd of all three smaller exponent elements in less than a minute:

YAFU uses GMP functions, which as of some-recent-version uses a sub-quadratic GCD algorithm. Perhaps that's the difference from what Dr. Sardonicus did.

Of course, that's all moot when the inputs have quadrillions of digits...

[Dr Sardonicus]

Originally Posted by EdH

What am I missing? YAFU can solve gcd of all three smaller exponent elements in less than a minute

I did say "my old computer." It's ten years old. I'm sure it's not ideal for doing serious number crunching. Also, I'm using an almost equally-old version of Pari-GP. It uses a "modified binary shift" algorithm for integer gcd's. I do have Pari using GMP as a multiprecision core.

[EdH]

Originally Posted by Dr Sardonicus

I did say "my old computer." It's ten years old. I'm sure it's not ideal for doing serious number crunching. Also, I'm using an almost equally-old version of Pari-GP. It uses a "modified binary shift" algorithm for integer gcd's. I do have Pari using GMP as a multiprecision core.

Sorry! The machine I used is also over 10 years old and I'm often reminded by members here how "ancient" all my equipment is.

I just thought a ten-fold difference seemed a bit odd and that maybe what I missed was that you had solved for the greater elements.

I have also discovered that I was in error as to YAFU solving three entries with its gcd() function. This test shows that it only solves for the last two integers provided:

$ ./yafu


09/21/17 18:12:37 v1.35-beta @ localhost.localdomain, System/Build Info: 
Using GMP-ECM 7.0.3, Powered by GMP 6.1.1
detected AMD Athlon(tm) 64 X2 Dual Core Processor 6000+
detected L1 = 65536 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 1751.629150
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> gcd(18,25,125)

25
>> gcd(16,18,25,125)

25
>> gcd(125,25,18,16)

2
>> quit

Slinking away...

[WMHalsdorf]

I don't know of any computer capable of handling numbers that have 2.7 * 10^15 digits.

17592186175489*log(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572)=2.707268856097308*10^15

[crack11]

Dear all,

Z1:= (7580104959982914109394378405621081680045277328933902877018950173722431866047182165909685701898461476201769271496346873969218041590426190558248064238412-(5542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^65537));
Z2:= (7580104959982914109394378405621081680045277328933902557064898247755957479231576299665165903124564064889635003580310606233252493957322555511313835652894-(2210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^65537));

ToUpperCase[IntegerString[(GCD[Z1,Z2]),16]] this is 2 integer string he give result in just 12 seconds in my laptop but problem is my new exp is very big and calculating not start he show error
i need this string to find gcd:Z1:= (7580104959982914123117804044806461820154572036369549529405552162648856956231245030405896783337631871321017085933334306430501343909365379890910193903441-(7601611438277968963930435339966375537762723788929138241505092335032216337024111944145650540579951639515460945444623092013993572866002842083492323809287290^17592186175489));
Z2:= (7580104959982914123117804044806461820154572036369549301773204651044654156328611994019678602790933052049997074737942147009504600337458372628655015658163-(5472021051232020294637156058031796107019454396525172260491306567922450488302345750910648307191204110931670031994886144725045972546892458995859985546716414^17592186175489));
ToUpperCase[IntegerString[(GCD[Z1,Z2]),16]]

[Dr Sardonicus]

Originally Posted by EdH

Sorry! The machine I used is also over 10 years old and I'm often reminded by members here how "ancient" all my equipment is.

I just thought a ten-fold difference seemed a bit odd and that maybe what I missed was that you had solved for the greater elements.

Hmm, a ten-fold difference does seem a bit much. Usually times for routine calculations on my old machine aren't that far out of line.

Well, the main reason I even tried the calculation was to see whether it would actually work. In particular, I was curious as to whether the Pari stack would overflow. It didn't. But it is possible that, if I allocated more stack space and did the calculation again, it would go faster. Often I have found that, if Mr. Computer is taking longer than expected to do something, it's running short of some critical resource...