Hacker News Reader

Comment by tzs | Hacker News Reader

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

View on HN

A minor note: pow is able to calculate modulo inverse (pow(a, -1, n)) starting from python3.8.

A 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.

Yes, 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).

I had no idea, that's awesome!

Why isn't Python using the more efficient code automatically when you write '(a * b) % n'? Seems like something that is the language's job.

Python 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.

Hmm.. 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.

Is 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?

I 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

[2] https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

Thanks! 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?

Sry, 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.

Reply on news.ycombinator.com