4 ms·
Quite a bit of that code can be eliminated if you use the 3 argument form of Python’s pow() function. pow(a, b, n) efficiently computes (a ** b) % n and
by tzs 5y ago
Quite a bit of that code can be eliminated if you use the 3 argument form of Python’s pow() function.
pow(a, b, n)
efficiently computes
(a ** b) % n
and
pow(a, -1, n)
finds b such that
(a * b) % n == 1
- nxpnsv 5y agoI had no idea, that's awesome!
- bvrmn 5y agoA minor note: pow is able to calculate modulo inverse (pow(a, -1, n)) starting from python3.8.
- tzs 5y agoA minor note to your minor note: if you are on an earlier Python but happen to know ϕ(n), you can use Euler's theorem [1] to replace pow(a, -1, n) with pow(a, ϕ(n)-1, n). [1] if a and n are relatively prime then a^ϕ(n) ≡ 1 mod n. Edit: someone replied to this wondering how Python implemented (a, -1, n). I looked into this once, remembered that I found it was reasonable, but did not remember how it actually did it. I took another look to answer that comment, but the comment has been deleted. The answer is that it uses the extended Euclidean algorithm. The function long_invmod in Objects/longobject.c does the deed.
- deleted 5y ago[deleted]
- vmilner 5y agoYes, I deleted it because I was being an idiot :) I was momentarily thinking pow(a,-1,n) would need to calculate phi(n) internally (a hard thing to do in general) but the EEA will of course do it very cheaply without needing to know phi(n).
- deleted 5y ago[deleted]
- chrisseaton 5y agoWhy isn't Python using the more efficient code automatically when you write '(a * b) % n'? Seems like something that is the language's job.
- karatinversion 5y agoPython allows for overloading these operators, and has dynamic types, so cannot produce the more efficient byte code on load. Most python interpreters also don't have JIT compilers that could do the optimization on the fly.
- chrisseaton 5y agoHmm.. when you compile to byte code you could emit a single POW_MOD instruction, and then dispatch to the more efficient code if both methods remain un-redefined, or call the full methods if one or more has been redefined.
- omegalulw 5y agoIs finding b such that (a * b) % n really that much work? It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
- tzs 5y agoI think you are looking to find b such that a + b = 1 mod n. The problem is to find b such that a x b = 1 mod n. That only has a solution if a is relatively prime to n, and generally the best way to find that solution is to use the extended Euclidean algorithm [1]. Briefly because a and n are relatively prime, there exists integers x and y such that ax + ny = 1 [2]. The extended Euclidean algorithm finds x and y. But ax + ny mod n is just ax mod n, and so we have ax = 1 mod n. The b we seek is x. [1] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm [2] https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
- omegalulw 5y agoThanks! Reading my comment again it's clear I had a brain fart during writing the comment but I was indeed trying to solve: find b such that (a + b) % n == 1. Of course, assume a and n are relatively prime. Then this is equivalent to finding a b such that (a % n + b % n) % n == 1. We already know that 0 < a % n < n so simply picking b = n + 1 - a % n works. In fact, b = zn + 1 - a % n for any positive integer z works. Your solution makes sense to me too but I wonder if I'm missing something obvious above?
- omegalulw 5y agoSry, I had a brain fart again. My solution won't work, it's for a different problem. I can't delete comments from my phone and I think for the addition problem it's a reasonable solution so I'll just leave it.