Why math.gcd compute faster than %? (original) (raw)

Hi everyone, I’m new to use math.gcd.

When I tried to compute the p,q from N in RSA, I always need to wait for a long long time to use % represented for mod. But math.gcd can compute it in less than one second. That’s too amazing! Does anyone knows how math.gcd works that it works so efficiently?

Here’s my coding:

image

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
#using %
q = (pow(a2,-e1*e2,N)_pow(c2,e1,N) - pow(a1,-e1_e2,N)pow(c1,e2,N)) % N #using math.gcd from math import gcd _q = gcd(pow(a2,-e1_e2,N)_pow(c2,e1,N) - pow(a1,-e1_e2,N)pow(c1,e2,N),N) p = N//q print(‘crypto{’,p,‘,’,q,‘}’) _q = (pow(a2,-e1_e2,N)_pow(c2,e1,N) - pow(a1,-e1_e2,N)*pow(c1,e2,N)) % N

Stefan2 (Stefan) June 8, 2025, 5:50pm 2

Please post code as formatted text, not just as image, so we can run it ourselves.

tim.one (Tim Peters) June 8, 2025, 6:31pm 3

To get the best help, please try to post a minimal, executable example, so that we can see, and try for ourselves, everything at work.

To answer your surface question, CPython uses a version of Lehmer’s GCD algorithm, which gets major speed benefits from arranging to do much of the work using very much smaller ints (it’s based on the observation that, in Euclid’s algorithm, the quotient is usually very small, and so can usually be determined by looking at only a relative few of the most-significant bits of the dividend and divisor). But the code to get this right in all cases is rather elaborate.

And there may be other things at work we can’t guess at without you posting complete executable code. For example, it’s common that newcomers get confused by that just displaying a large integer in decimal is itself an expensive operation, and that things speed up a lot if they assign to a variable instead of displaying a large int, or display it usiing hex() instead (which is much cheaper than converting to decimal notation).

popeim (Lark) June 9, 2025, 4:51am 5

Thanks Tim. That’s the answer I’m looking for!

Stefan2 (Stefan) June 9, 2025, 10:36am 6

Formatted, please. Otherwise it’s still not usable, has for example “e1e2” (not showing the * between) and invalid quotes. Also, it uses a2 which doesn’t exist.

And I’m quite certain that Tim’s answer doesn’t explain your times, because your times probably aren’t even true. Your whole code should only take a split second. And when I tried modulo and gcd with similar numbers, modulo was about five times faster. About 8 microseconds vs 40 microseconds.

tim.one (Tim Peters) June 9, 2025, 3:41pm 7

Although I didn’t try to explain them, because there was no usable info given about them. And they didn’t ask for an explanation either, just about how math.gcd() works. So that’s the part I gave clues for.

Of course you’re right that everything we’ve been told doesn’t support the idea that gcd even could be faster than mod in cases like this. The code is of the form

(pow(..., ..., N) - pow(..., ...., N)) % N

vs

gcd(pow(..., ..., N) - pow(..., ...., N), N)

and the absolute value of the difference of the pow results is necessarily less than N (being a difference of two values each in range(N)), so mod has very little to do: the result is either that difference (if it’s non-negative), or N larger (if it’s negative).

Neither is there any reason to believe that the two spellings give the same result. In fact, I see no reason to believe that the spelling using mod even gives a p that divides N (of course the spelling using gcd must return a divisor of N, but mostly likely the trivial 1 or N).

None of which the OP seems to want to discuss, and that’s fine. They did get an answer to what they did ask about :smile:.

Stefan2 (Stefan) June 9, 2025, 3:51pm 8

It’s not a difference of two pows but of two products of two pows each. Can be up to N^2.

They asked “Why math.gcd compute faster than %?” and “Does anyone knows how math.gcd works that it works so efficiently?”, both of which are asking about the claimed relative speeds of the two operations, not “just about how math.gcd() works”.

tim.one (Tim Peters) June 9, 2025, 3:59pm 9

So it is! My mistake. Thanks!

If the OP wants to discuss more, fine, but short of that I see no real value in us continuing to pick over the bones.

tim.one (Tim Peters) June 9, 2025, 4:20pm 10

Although :wink: I will note that, regardless of how large the first argument is, the first thing gcd(J, N) does is compute J % N, to reduce the problem to the closer-to-done gcd(N, J % N). But computing J % N is the whole banana for mod.

So, ya, it would be a miracle if gcd were materially faster for any inputs.

At least in CPython, which isn’t using, e.g., some form of binary GCD algorithm..

Stefan2 (Stefan) June 9, 2025, 4:57pm 11

To me it rather looks like they misunderstood you and took away the wrong lesson. They might now walk away thinking “gcd is faster than modulo because ”, when it’s not even true. That is not good. Other readers of your reply also might. That is not good. The OP also might walk away not realizing their timing mistake and keep repeating that mistake. That is not good.

I still hope they’ll provide proper code, which we can then run and then likely tell them that it’s not at all as slow as they said and ask them what they actually did that took so long. And after resolving these issues and a proper resolution of their question, then I would’ve liked to learn about the Lehmer thing.