miller_rabin_2

miller_rabin_2:
;;Performs a Miller-Rabin probable prime test, with base 2
;;Input: HL
;; NC if failed, C if passed
    ld b,h  ;
    ld c,l  ;
    dec hl  ;
    ld a,l  ;
    rrca    ;
    ccf     ;
    ret nc  ;
    or h    ;
    ret z   ;
    ld de,2 ;
    ld a,17 ;
    dec a       ;\
    add hl,hl   ; |Get size while prepping for modular exponentiation by repeated squaring
    jr nc,$-2   ;/
mr2_loop:
    push af
    ld a,h      ;\
    or l        ; |If HL is zero, time to go to part 2 of the test
    jr z,mr2sqr ;/
    call sqr_mod;  DE*DE mod (mod)
    add hl,hl   ; |If incoming bit is 1,
    jr nc,$+18  ;/ mul DE by 2, else skip
    ex de,hl    ;\
    add hl,hl   ; |Mul DE by 2,
    jr nc,$+8   ; |\
    or a        ; | |
    sbc hl,bc   ; | |Now MOD
    jp $+8      ; | |
    sbc hl,bc   ; | |
    jr nc,$+3   ; | |
    add hl,bc   ; |/
    ex de,hl    ;/
    pop af
    dec a
    jp mr2_loop
mr2sqr:
    ;;if DE = 1, or BC-1, then return c flag set
    pop hl  ;counter in H
    or d
    jr nz,$+7
    or e
    dec a
    scf
    ret z
    or a
    ex de,hl
    inc hl
    sbc hl,bc
    ccf
    ret z
    add hl,bc
    dec hl
    ex de,hl
mr2sqr_loop:
    call sqr_mod
    ;;if DE = 1, return NC
    ;;If DE = BC-1, return C
    ld a,d
    or a
    jr nz,$+5
    dec e
    ret z
    inc e
    inc de
    ex de,hl
    sbc hl,bc
    ccf
    ret z
    add hl,bc
    dec hl
    ex de,hl
    dec h
    jr nz,mr2sgr_loop
    ret

sqr_mod:
;;DE*DE mod BC, DE<BC
;;1343.625cc avg
    push hl
    ld hl,0
    ld a,d
    rla \ jr nc,$+4 \ ld h,d \ ld l,e
    call sqr_mod_sub0+3 ;577.125 avg
    ld a,e
    call sqr_mod_sub0   ;662cc avg
    ex de,hl
    pop hl
    ret
sqr_mod_sub0:
;;662cc avg
    call sqr_mod_sub
    call sqr_mod_sub
    call sqr_mod_sub
    call sqr_mod_sub
    call sqr_mod_sub
    call sqr_mod_sub
    call sqr_mod_sub
sqr_mod_sub:
;;max: 110cc
;;min: 38
;;avg: 67.875cc
;;38+{0,14}     ;.5     *45
;;79+{0,14}     ;.25    *86
;;81+{0,14}+{0,15};.25  *95.5
    add hl,hl \ jr nc,$+5 \ ccf \ sbc hl,bc
    rla \ ret nc
    add hl,de \ jr nc,$+8 \ ccf \ sbc hl,bc \ ret
    sbc hl,bc \ ret nc \ add hl,bc
    ret