Modular Exponentiation

A modular exponentiation subroutine in X86 assembly (for nasm):

;; Performs the modular exponentiation a^m mod n and returns the result
;; a, m, and n are given as arguments
modular_exp:
    push ebp
    xor ebx, ebx                 ; C = 0
    mov esi, [esp+16]            ; Load variable 'n' from arguments
    mov edx, ebx                 ; D = 0
    mov edi, [esp+12]            ; Load variable 'm' from arguments
    inc edx                      ; D += 1
    mov ebp, [esp+8]             ; Load variable 'a' in base pointer reg
    bsr ecx, edi                 ; Get most signif. bit of m that is not 0
    inc ecx                      ; Step past it by one
    ror edi, cl                  ; Put that bit in position 0
  .bitloop:
    rol edi, 1                   ; Rotate next bit into position 0
    shl ebx, 1                   ; C *= 2

    mov eax, edx
    mul edx                      ; Calculate D^2 and zero out edx for division
    div esi                      ; Divide by n, remainder is in edx

    test edi, 0x01               ; See if current bit is set
    je .bitnotset
    inc ebx                      ; C += 1
    mov eax, ebp                 ; Load variable 'a' into eax
    mul edx                      ; D * a ...
    div esi                      ; ... mod n
  .bitnotset:
    loop .bitloop

    pop ebp
    mov eax, edx
    ret                          ; return variable D (in eax)

I haven't tried calling it from C but if you wanted to do it you'd need this:

extern unsigned int modular_exp(unsigned int a, unsigned int m, unsigned int n);

You'd also need to push ebx, esi, and edi and pop them before returning.