mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Closed Thread
 
Thread Tools
Old 2017-09-21, 12:15   #23
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1101111010102 Posts
Default

Hmm, cryptoworks... google google... like this?
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
Dr Sardonicus is offline  
Old 2017-09-21, 12:21   #24
crack11
 
Sep 2017

1816 Posts
Default

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

Thanks
crack11 is offline  
Old 2017-09-21, 15:22   #25
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

356210 Posts
Default

Quote:
Originally Posted by crack11 View Post
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
Dr Sardonicus is offline  
Old 2017-09-21, 18:16   #26
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172916 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
CRGreathouse is online now  
Old 2017-09-21, 19:55   #27
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3,373 Posts
Default

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...
EdH is offline  
Old 2017-09-21, 20:05   #28
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·17·97 Posts
Default

Quote:
Originally Posted by EdH View Post
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...
bsquared is offline  
Old 2017-09-21, 21:47   #29
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×13×137 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
Dr Sardonicus is offline  
Old 2017-09-21, 22:25   #30
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3,373 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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: 
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...
EdH is offline  
Old 2017-09-22, 10:28   #31
WMHalsdorf
 
WMHalsdorf's Avatar
 
Feb 2005
Bristol, CT

33·19 Posts
Default

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
WMHalsdorf is offline  
Old 2017-09-22, 12:39   #32
crack11
 
Sep 2017

308 Posts
Default

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]]
crack11 is offline  
Old 2017-09-22, 12:42   #33
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×13×137 Posts
Default

Quote:
Originally Posted by EdH View Post
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...
Dr Sardonicus is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new problem similar to the Collatz problem dabler Miscellaneous Math 1 2018-07-28 14:03
Math ET_ Operazione Doppi Mersennes 4 2012-09-20 19:33
Runescape math problem jasong Homework Help 10 2012-04-21 01:09
Help with Math Problem jinydu Puzzles 4 2003-12-13 06:00
Need help with math problem re: searching for all primes. daxm Miscellaneous Math 5 2003-07-20 19:32

All times are UTC. The time now is 03:25.

Fri Oct 23 03:26:00 UTC 2020 up 43 days, 36 mins, 0 users, load averages: 2.10, 1.76, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.