MPIs are integer numbers with potentially thousands of bits instead of the usual 16, 32, or 64 bit. These numbers are important for certain fields of mathematics and physics. Cryptography cannot live without them.
Tcl represents normal integers (32bit) as normal Tcl variables - ie. as strings. Consequently MPIs are also represented as strings. The big difference is that a different class of functions is needed to work with these numbers, as the normal expr function is not able to deal with so large numbers.
You can enter MPIs in decimal, octal or hexadecimal form. The interpreter will determine the number type by the first characters:
If the string does not represent a valid number (eg. it contains illegal characters or spaces) the Interpreter will raise an error the first time it is used in a MPI function.
All MPI functions live in the namespace ::mpi. You can call all MPI functions by prefixing them with ::mpi:: (as in ::mpi::add) or you can import this namespace into your own namespace by doing:
namespace import ::mpi
Please be aware that this overwrites functions in your own namespace. Eg. you should not import ::mpi into the global namespace :: if you plan on using Tcls own expr function (I bet you do).
Important: the expr function does not yet exist. Use the simpler functions below instead.
::mpi::expr is a high level function that allows you to enter MPI equations as normal formulas.
Other than with the Tcl ::expr function every operator and every operand has to be its own argument to the function:
#valid expression: ::mpi::expr 123 + 456 #invalid expression: ::mpi::expr 123+456
Operators are evaluated in the order of their priority (highest priority first):
| Operator | Prio | Description |
| ( ) | 100 | parentesis: evaluates the content and is replaced by the result |
| ** | 90 | to the power of, eg. 2**3 is 16 |
| <<,>> | 90 | shift left/right, 1<<3 is 8, 8>>3 is 1 |
| * | 80 | multiply |
| / | 80 | divide |
| % | 80 | modulo (remainder) |
| &,|,^ | 60 | bitwise and, or, xor |
| + | 50 | plus |
| - | 50 | minus |
| <,>,==,!=,<>,<=,>= | 20 | comparison |
| &&,|| | 10 | logical and,or |
Please note that ::mpi::expr does not optimize! A ::mpi::expr $a ** $b % $c will first potentiate a with b and then do the modulo with c, instead of using the faster expmod algorithm. You should use the simpler functions below to do this kind of optimization.
There exist several simple functions to do basic operations on MPIs:
| add a b | adds a and b and returns result |
| sub a b | subtracts b from a and returns result |
| mul a b | multiplies a with b |
| cdiv a b | divides a by b, rounds up |
| fdiv a b | divides a by b, rounds down |
| tdiv a b | divides a by b, rounds towards zero (truncates) |
| mod a b | a modulo b |
| exp a b | a by the power of b |
| isequal a b | returns 1 if a and b are equal |
| issmaller a b | returns 1 if a is smaller than b |
| isgreater a b | returns 1 if a is greater than b |
| iszero a | returns 1 if a is zero |
| band a b | each bit of a is and'ed with the corresponding bit from b |
| bor a b | binary a or b |
| bxor a b | binary a xor b |
| bnot a | binary not a (each bit inverted) |
land, lor, lxor, lnot always return 0 or 1
lis returns 1 if its argument is non-zero, this is equivalent to lnot (no protocol spec in link).
| isprime a | returns 1 if a is a probably a prime number, 2 if it is definitely a prime |
| expmod a b c | a by the power of b, modulo c |
| ::mpi::abs | return absolute of a |
| ::mpi::add | a + b |
| ::mpi::asbase | return n as a string in base b |
| ::mpi::asdec | return n as a decimal string |
| ::mpi::ashex | return n as a hexadecimal string |
| ::mpi::asoct | return n as a octal string |
| ::mpi::band | a and b |
| ::mpi::bin | returns the binomial coefficient n over k |
| ::mpi::bnot | not a, or the two's-complement of a |
| ::mpi::bor | a or b |
| ::mpi::bxor | a xor b |
| ::mpi::cdiv | a / b, rounding up |
| ::mpi::cdivr | remainder of a / b, rounding up |
| ::mpi::clrbit | return an MPI that is a with bit n cleared |
| ::mpi::cmp | compares a and b, returns 1 if a>b, 0 if a==b, -1 if a<b |
| ::mpi::cmpabs | compares abs(a) and abs(b), returns 1 if a>b, 0 if a==b, -1 if a<b |
| ::mpi::eq | a == b |
| ::mpi::exp | b to the power of e |
| ::mpi::expmod | b to the power of e modulo n |
| ::mpi::fac | returns the factorial a! of a, a needs to be an ordinary positive integer |
| ::mpi::fdiv | a / b, rounding down |
| ::mpi::fdivr | remainder of a / b, rounding down |
| ::mpi::fib | returns the n'th Fibonacci number |
| ::mpi::frombase | convert base b string to MPI |
| ::mpi::fromdec | convert decimal string to MPI |
| ::mpi::fromhex | convert hexadecimal string to MPI |
| ::mpi::fromoct | convert octal string to MPI |
| ::mpi::gcd | returns the greatest common divisor of a and b |
| ::mpi::gcdext | returns a list {g s t} with g=gcd(a,b) and a*s+b*t=g |
| ::mpi::gt | a > b |
| ::mpi::gte | a >= b |
| ::mpi::hamdist | returns the Hamming distance between a and b, returns -1 if a and b have different sign |
| ::mpi::info | return info about any MPI function |
| ::mpi::invert | invert n under modulo m, throws an error if the inverse doesn't exist |
| ::mpi::isdiv | return 1 if a is exactly divisible by b |
| ::mpi::iseven | return 1 if n is even |
| ::mpi::isodd | return 1 if n is odd |
| ::mpi::isperfpow | returns whether a is a perfect power, ie. whether there is a pair A,B with B>1 so that a equals A raised to the power of B |
| ::mpi::isperfsquare | returns whether a is the square of an integer |
| ::mpi::isprime | test n for primality n times, returns 1 if n is probably prime, 2 if it is definitely prime |
| ::mpi::jacobi | returns the Jacobi symbol of a/b, b must be odd |
| ::mpi::kronecker | returns the Jacobi symbol of a/b with Kronecker extension |
| ::mpi::land | returns 1 if a and b are non-zero |
| ::mpi::lcm | returns the least common multiple of a and b |
| ::mpi::legendre | returns the Legendre symbol of a/p, p must be prime |
| ::mpi::lis | checks whether a is non-zero |
| ::mpi::lnot | checks whether a is zero |
| ::mpi::lor | returns 1 if a or b is non-zero |
| ::mpi::lt | a < b |
| ::mpi::lte | a <= b |
| ::mpi::luc | returns the n'th Lucas number |
| ::mpi::lxor | returns 1 if exactly one of a or b is non-zero |
| ::mpi::mod | a mod abs(b) |
| ::mpi::mul | a * b |
| ::mpi::ne | a != b |
| ::mpi::neg | return -a |
| ::mpi::nextprime | returns next prime greater than n |
| ::mpi::popcount | count the 1 bits in a, for negative it returns -1 since the amount of 1's is infinite |
| ::mpi::remove | remove all occurences of factor f in a; returns a list of {a r} with r being the number of occurences removed |
| ::mpi::root | returns a list: element 0 is the integer part of n'th root of a, element 1 is non-zero if the root-operation was perfect (ie. there was no remainder) |
| ::mpi::scan0 | scan for the first 0 bit in a from least significant to most significant, start at bit n |
| ::mpi::scan1 | scan for the first 1 bit in a from least significant to most significant, start at bit n |
| ::mpi::setbit | return an MPI that is a with bit n set |
| ::mpi::sgn | sign of a: +1 if a>0, 0 if a==0, -1 if a<0 |
| ::mpi::shl | a << b |
| ::mpi::size | return the size of n in base b |
| ::mpi::sqrt | returns truncated integer part of square root of a |
| ::mpi::sqrtrem | returns a list: element 0 is the truncated integer part of the square root of a, element 1 is the remainder of that operation |
| ::mpi::sub | a - b |
| ::mpi::tdiv | a / b, rounding towards zero |
| ::mpi::tdivr | remainder of a / b, rounding towards zero |
| ::mpi::tstbit | return whether bit n is set in a |