 Impressum / Publisher

# Using MPIs in Tcl

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.

## Representing MPIs in Tcl

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 number starts with 0x or 0X it will be interpreted as hexadecimal
• if it starts with 0 it will be interpreted as octal
• any other first digit will be interpreted as start of a decimal number

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.

## The MPI namespace

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).

## ::mpi::expr

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.

## Basic mathematical functions

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

## Test functions

 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

## binary functions

 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)

## logical functions

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).

## number theoretical functions

 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

## full alphabethical list of functions

 ::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 ab, 0 if a==b, -1 if 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

Webmaster: webmaster AT silmor DOT de