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

3 views (last 30 days)
mehdi kilani
mehdi kilani on 11 Jan 2022
Answered: Walter Roberson on 12 Jan 2022
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..

Answers (2)

John D'Errico
John D'Errico on 12 Jan 2022
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.

Walter Roberson
Walter Roberson on 12 Jan 2022
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!