How does Matlab perform large integer modular arithmetics using Symbolic Math Toolbox?

I have implemented an ECC (Elliptic Curve Cryptography) model using Matlab symbolic tool by which the large integer arithmetics can be manipulated. Now I want to implement the algorithm with a 32-bit processor. I am looking for the algorithms that Matlab is using to implement modular addition, subtraction, multiplication and inverse, etc..

Answer 1

[John D'Errico]

You won't get the exact algorithms. MathWorks does not hand out their internal code for this sort of thing, unless you have a job there.

Answer 2

[Walter Roberson]

S1 = char(evalin(symengine, 'expose(symobj::powermod)'));
S1 = regexprep(S1, '\\n', '\n')

S1 = 
    'proc(pow : DOM_EXPR, m) : Type::Union(DOM_INT, stdlib::Undefined)
       name symobj::powermod;
       local a, n, res;
     begin
       assert(op(pow, 0) = #power); 
       [a, n] := [op(pow)]; 
       if ~testtype(a, Type::Integer) then
         error(message(\"symbolic:numlib:FirstArgumentInteger\"))
       end_if; 
       if ~testtype(n, Type::Integer) then
         error(message(\"symbolic:arithmetic:ExpectingInteger2\"))
       end_if; 
       if ~testtype(m, Type::NonNegInt) then
         error(message(\"symbolic:arithmetic:ExpectingNonnegativeInteger3\"))
       end_if; 
       res := powermod(a, n, m); 
       if res = FAIL then
         undefined
       else 
         res
       end_if
     end_proc'

S2 = char(evalin(symengine, 'expose(powermod)'));
S2 = regexprep(S2, '\\n', '\n')

S2 = 
    'proc(p, n, m)
       name powermod;
     begin
       if args(0) < 1 then
         error(message(\"symbolic:arithmetic:IncorrectNumberOfArguments\"))
       else 
         if p::dom::powermod <> FAIL then
           return(p::dom::powermod(args()))
         end_if
       end_if; 
       if args(0) <> 3 then
         error(message(\"symbolic:arithmetic:IncorrectNumberOfArguments\"))
       end_if; 
       case domtype(m)
         of DOM_INT do
           if domtype(n) <> DOM_INT then
             error(message(\"symbolic:arithmetic:ExpectingInteger2\"))
           end_if; 
           if iszero(m) then
             return(p^n)
           end_if; 
           case domtype(p)
             of DOM_INT do
               
             of DOM_RAT do
               if n < 0 then
                 return(stdlib::powermod(1/p, -n, m))
               else 
                 return(stdlib::powermod(args()))
               end_if
             of DOM_POLY do
               return(poly(poly(p, IntMod(m))^n, op(p, 2..3)))
             otherwise
               return(op(poly(p, IntMod(m))^n, 1))
           end_case
         of DOM_POLY do
           if testargs() then
             if nops(op(m, 2)) <> 1 then
               error(message(\"symbolic:arithmetic:ExpectingUnivariatePolynomial3\"))
             else 
               if domtype(n) <> DOM_INT then
                 error(message(\"symbolic:arithmetic:ExpectingInteger2\"))
               end_if
             end_if
           end_if; 
           if domtype(p) <> DOM_POLY then
             if p = FAIL then
               FAIL
             else 
               op(powermod(poly(p, op(m, 2..3)), n, m), 1)
             end_if
           else 
             if op(p, 2..3) = op(m, 2..3) then
               case n
                 of 0 do
                   return(p^0)
                 of 1 do
                   return(divide(p, m, Rem))
               end_case; 
               faclib::powermod_poly(args())
             else 
               if op(p, 3) = op(m, 3) then
                 poly(powermod(poly(p, op(m, 2..3)), n, m), op(p, 2..3))
               else 
                 error(message(\"symbolic:arithmetic:PolynomialTypesDiffer\"))
               end_if
             end_if
           end_if; 
           break
         of DOM_FAIL do
           return(FAIL)
         otherwise
           m := poly(m); 
           if testargs() then
             if type(m) <> DOM_POLY then
               error(message(\"symbolic:arithmetic:CannotConvertToPolynomial3\"))
             end_if; 
             if type(n) <> DOM_INT then
               error(message(\"symbolic:arithmetic:ExpectingInteger2\"))
             end_if
           end_if; 
           return(powermod(p, n, m))
       end_case
     end_proc'

S3 = char(evalin(symengine, 'expose(stdlib::powermod)'));
S3 = regexprep(S3, '\\n', '\n')

S3 = 'builtin(1047, NIL, \"powermod\", NIL)'

So... at least some of the cases are built-in, source not published.