Khan recursive power (instead using exponentiation by squaring)

exp_by_square.jl

# Exponentiation by squaring is the standard method for modular exponentiation on big numbers in asymmetric cryptography

julia> function expbysquare(b::Int, e::Int)
          result = BigInt(1)
          bigb = BigInt(b)  
          while e > 0
              if isodd(e)
                  result *= bigb
              end
              e >>= 1 # set e to itself shifted by one bit to the right, evaluate the new e after shift 
                      # for unsigned type, the value of the most significant bit after shift is zero (confirm)
              bigb *= bigb
          end
          result
       end
            
expbysquare (generic function with 3 methods)

julia> expbysquare(2, 3)
8
                  
julia> expbysquare(2, 100)
1267650600228229401496703205376

julia> @time expbysquare(2, 1000)
  0.000013 seconds (135 allocations: 7.756 KiB)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

julia> expbysquare(2, -10) # incorrect
1

julia> expbysquare(-2, 10)
1024

julia> expbysquare(-2, 11)
-2048
                    
julia> expbysquare(-2, -10) # incorrect
1