20170921, 12:15  #23  
Feb 2017
Nowhere
110111101010_{2} Posts 
Hmm, cryptoworks... google google... like this?
Quote:
Last fiddled with by Dr Sardonicus on 20170921 at 12:20 

20170921, 12:21  #24 
Sep 2017
18_{16} Posts 
yes DR Sardonicus sir same crypto/conax cabletv scrambled system need calculating gcd please help me to solve this issu..
Thanks 
20170921, 15:22  #25  
Feb 2017
Nowhere
3562_{10} Posts 
Quote:
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 bruteforce 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(75801049599829141093943784056210816800452773289339028770189501737224318660471821659096857018984614762017692714963468739692180415904261905582480642384125542744080416549313204339685348101804092633280776996094712323671936025724303663565120968650288374354487920966943136994524637343823470109069100536001825061^65537, 75801049599829141093943784056210816800452773289339025570648982477559574792315762996651659031245640648896350035803106062332524939573225555113138356528942210052959863233666352631743605544948489669349588589762935731382353706272687862251429121203091727087209430630578779213774169437578222468020592099358198793^65537) %1 = 9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891 Last fiddled with by Dr Sardonicus on 20170921 at 15:50 

20170921, 18:16  #26  
Aug 2006
1729_{16} Posts 
Quote:
Code:
G2=9943361511736887180525193238781951852048704466124378491895895799799940176852818360584496466538746226491733937270575629104317392858375709260953122655392891; Z3mod=7580104959982914380707737866198974081289603526426728444663905520185161944615556517456155284414829089801734045676331442459189567878379004868410811939884Mod(7769917532858189300573807160645252136211403803199106971490637897656073492246460627329132405022210291064618462659663590068082649667914372368725493336150572,G2)^65537; G3=gcd(lift(Z3mod),G2) 

20170921, 19:55  #27 
"Ed Hall"
Dec 2009
Adirondack Mtns
3,373 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.35beta @ localhost.localdomain, System/Build Info: Using GMPECM 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 RabinMiller 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 Code:
$ date;./yafu;date Thu Sep 21 15:48:30 EDT 2017 09/21/17 15:48:30 v1.35beta @ localhost.localdomain, System/Build Info: Using GMPECM 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 RabinMiller 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 
20170921, 20:05  #28  
"Ben"
Feb 2007
2·17·97 Posts 
Quote:
Of course, that's all moot when the inputs have quadrillions of digits... 

20170921, 21:47  #29 
Feb 2017
Nowhere
2×13×137 Posts 
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 equallyold version of PariGP. It uses a "modified binary shift" algorithm for integer gcd's. I do have Pari using GMP as a multiprecision core.

20170921, 22:25  #30  
"Ed Hall"
Dec 2009
Adirondack Mtns
3,373 Posts 
Quote:
I just thought a tenfold 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.35beta @ localhost.localdomain, System/Build Info: Using GMPECM 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 RabinMiller 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 

20170922, 10:28  #31 
Feb 2005
Bristol, CT
3^{3}·19 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 20170922 at 12:28 Reason: code tags 
20170922, 12:39  #32 
Sep 2017
30_{8} 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]] 
20170922, 12:42  #33  
Feb 2017
Nowhere
2×13×137 Posts 
Quote:
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... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A new problem similar to the Collatz problem  dabler  Miscellaneous Math  1  20180728 14:03 
Math  ET_  Operazione Doppi Mersennes  4  20120920 19:33 
Runescape math problem  jasong  Homework Help  10  20120421 01:09 
Help with Math Problem  jinydu  Puzzles  4  20031213 06:00 
Need help with math problem re: searching for all primes.  daxm  Miscellaneous Math  5  20030720 19:32 