 Computational complexity of modular exponentiation

 New to topics? Read the documentation here!

 Top articles  Latest articles + New article in topic

Computational complexity of modular exponentiation by

Ciro Santilli 34  Updated 2024-12-15  +Created 1970-01-01

math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:

b^{n} m o d m

can be calculated in:

l o g (m)^{2} l o g (n)

Remember that

l o g (m)

and

l o g (n)

are the lengths in bits of

m

and

n

, so in terms of the length in bits

M

and

N

we'd get:

M^{2} N

 Read the full article