mersenneforum.org math gcd problem need help
 Register FAQ Search Today's Posts Mark Forums Read

2017-09-21, 12:15   #23
Dr Sardonicus

Feb 2017
Nowhere

415610 Posts

Quote:
 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?

Last fiddled with by Dr Sardonicus on 2017-09-21 at 12:20

 2017-09-21, 12:21 #24 crack11   Sep 2017 23·3 Posts yes DR Sardonicus sir same crypto/conax cabletv scrambled system need calculating gcd please help me to solve this issu.. Thanks
2017-09-21, 15:22   #25
Dr Sardonicus

Feb 2017
Nowhere

103C16 Posts

Quote:
 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

Last fiddled with by Dr Sardonicus on 2017-09-21 at 15:50

2017-09-21, 18:16   #26
CRGreathouse

Aug 2006

135118 Posts

Quote:
 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:

Code:
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.

 2017-09-21, 19:55 #27 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 352710 Posts What am I missing? YAFU can solve gcd of all three smaller exponent elements in less than a minute: Code: $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. Code: $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... 2017-09-21, 20:05 #28 bsquared "Ben" Feb 2007 336010 Posts Quote:  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... 2017-09-21, 21:47 #29 Dr Sardonicus Feb 2017 Nowhere 22·1,039 Posts Quote:  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. 2017-09-21, 22:25 #30 EdH "Ed Hall" Dec 2009 Adirondack Mtns 3,527 Posts Quote:  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: Code: $ ./yafu

09/21/17 18:12:37 v1.35-beta @ localhost.localdomain, System/Build Info:
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

 2017-09-22, 10:28 #31 WMHalsdorf     Feb 2005 Bristol, CT 51310 Posts I don't know of any computer capable of handling numbers that have 2.7 * 10^15 digits. Code: 17592186175489*log(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572)=2.707268856097308*10^15 Last fiddled with by bsquared on 2017-09-22 at 12:28 Reason: code tags
 2017-09-22, 12:39 #32 crack11   Sep 2017 23·3 Posts 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]]
2017-09-22, 12:42   #33
Dr Sardonicus

Feb 2017
Nowhere

22×1,039 Posts

Quote:
 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post dabler Miscellaneous Math 1 2018-07-28 14:03 ET_ Operazione Doppi Mersennes 4 2012-09-20 19:33 jasong Homework Help 10 2012-04-21 01:09 jinydu Puzzles 4 2003-12-13 06:00 daxm Miscellaneous Math 5 2003-07-20 19:32

All times are UTC. The time now is 15:41.

Fri Jan 15 15:41:48 UTC 2021 up 43 days, 11:53, 0 users, load averages: 1.70, 1.76, 1.75