[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

# 29. Number Theory

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

## 29.1 Functions and Variables for Number Theory

Function: bern (n)

  Returns the n'th Bernoulli number for integer n. Bernoulli numbers equal to zero are suppressed if `zerobern` is `false`.

  See also `burn`.

      (%i1) zerobern: true$
      (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
                            1  1       1      1        1
      (%o2)           [1, - -, -, 0, - --, 0, --, 0, - --]
                            2  6       30     42       30
      (%i3) zerobern: false$
      (%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
                            1  1    1   1     1   5     691   7
      (%o4)           [1, - -, -, - --, --, - --, --, - ----, -]
                            2  6    30  42    30  66    2730  6

  Categories: Number theory

Function: bernpoly (x, n)

  Returns the n'th Bernoulli polynomial in the variable x.

  Categories: Number theory

Function: bfzeta (s, n)

  Returns the Riemann zeta function for the argument s. The return value is a big float (bfloat); n is the number of digits in the return value.

  Categories: Number theory · Numerical evaluation

Function: bfhzeta (s, h, n)

  Returns the Hurwitz zeta function for the arguments s and h. The return value is a big float (bfloat); n is the number of digits in the return value.

  The Hurwitz zeta function is defined as

                              inf
                              ====
                              \        1
               zeta (s,h)  =   >    --------
                              /            s
                              ====  (k + h)
                              k = 0

  `load ("bffac")` loads this function.

  Categories: Number theory · Numerical evaluation

Function: burn (n)

  Returns a rational number, which is an approximation of the n'th Bernoulli number for integer n. `burn` exploits the observation that (rational) Bernoulli numbers can be approximated by (transcendental) zetas with tolerable efficiency:

                         n - 1  1 - 2 n
                    (- 1)      2        zeta(2 n) (2 n)!
           B(2 n) = ------------------------------------
                                      2 n
                                   %pi

  `burn` may be more efficient than `bern` for large, isolated n as `bern` computes all the Bernoulli numbers up to index n before returning. `burn` invokes the approximation for even integers n > 255. For odd integers and n <= 255 the function `bern` is called.

  `load ("bffac")` loads this function. See also `bern`.

  Categories: Number theory

Function: chinese ([r_1, …, r_n], [m_1, …, m_n])

  Solves the system of congruences `x = r_1 mod m_1`, …, `x = r_n mod m_n`. The remainders r_n may be arbitrary integers while the moduli m_n have to be positive and pairwise coprime integers.

      (%i1) mods : [1000, 1001, 1003, 1007];
      (%o1)                   [1000, 1001, 1003, 1007]
      (%i2) lreduce('gcd, mods);
      (%o2)                               1
      (%i3) x : random(apply("*", mods));
      (%o3)                         685124877004
      (%i4) rems : map(lambda([z], mod(x, z)), mods);
      (%o4)                       [4, 568, 54, 624]
      (%i5) chinese(rems, mods);
      (%o5)                         685124877004
      (%i6) chinese([1, 2], [3, n]);
      (%o6)                    chinese([1, 2], [3, n])
      (%i7) %, n = 4;
      (%o7)                              10

  Categories: Number theory

Function: cf (expr)

  Computes a continued fraction approximation. expr is an expression comprising continued fractions, square roots of integers, and literal real numbers (integers, rational numbers, ordinary floats, and bigfloats). `cf` computes exact expansions for rational numbers, but expansions are truncated at `ratepsilon` for ordinary floats and `10^(-fpprec)` for bigfloats.

  Operands in the expression may be combined with arithmetic operators. Maxima does not know about operations on continued fractions outside of `cf`.

  `cf` evaluates its arguments after binding `listarith` to `false`. `cf` returns a continued fraction, represented as a list.

  A continued fraction `a + 1/(b + 1/(c + ...))` is represented by the list `[a, b, c, ...]`. The list elements `a`, `b`, `c`, … must evaluate to integers. expr may also contain `sqrt (n)` where `n` is an integer. In this case `cf` will give as many terms of the continued fraction as the value of the variable `cflength` times the period.

  A continued fraction can be evaluated to a number by evaluating the arithmetic representation returned by `cfdisrep`. See also `cfexpand` for another way to evaluate a continued fraction.

  See also `cfdisrep`, `cfexpand`, and `cflength`.

  Examples:

  - expr is an expression comprising continued fractions and square roots of integers.

        (%i1) cf ([5, 3, 1]*[11, 9, 7] + [3, 7]/[4, 3, 2]);
        (%o1)               [59, 17, 2, 1, 1, 1, 27]
        (%i2) cf ((3/17)*[1, -2, 5]/sqrt(11) + (8/13));
        (%o2)        [0, 1, 1, 1, 3, 2, 1, 4, 1, 9, 1, 9, 2]

  - `cflength` controls how many periods of the continued fraction are computed for algebraic, irrational numbers.

        (%i1) cflength: 1$
        (%i2) cf ((1 + sqrt(5))/2);
        (%o2)                    [1, 1, 1, 1, 2]
        (%i3) cflength: 2$
        (%i4) cf ((1 + sqrt(5))/2);
        (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
        (%i5) cflength: 3$
        (%i6) cf ((1 + sqrt(5))/2);
        (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

  - A continued fraction can be evaluated by evaluating the arithmetic representation returned by `cfdisrep`.

        (%i1) cflength: 3$
        (%i2) cfdisrep (cf (sqrt (3)))$
        (%i3) ev (%, numer);
        (%o3)                   1.731707317073171

  - Maxima does not know about operations on continued fractions outside of `cf`.

        (%i1) cf ([1,1,1,1,1,2] * 3);
        (%o1)                     [4, 1, 5, 2]
        (%i2) cf ([1,1,1,1,1,2]) * 3;
        (%o2)                  [3, 3, 3, 3, 3, 6]

  Categories: Continued fractions

Function: cfdisrep (list)

  Constructs and returns an ordinary arithmetic expression of the form `a + 1/(b + 1/(c + ...))` from the list representation of a continued fraction `[a, b, c, ...]`.

      (%i1) cf ([1, 2, -3] + [1, -2, 1]);
      (%o1)                     [1, 1, 1, 2]
      (%i2) cfdisrep (%);
                                        1
      (%o2)                     1 + ---------
                                          1
                                    1 + -----
                                            1
                                        1 + -
                                            2

  Categories: Continued fractions

Function: cfexpand (x)

  Returns a matrix of the numerators and denominators of the last (column 1) and next-to-last (column 2) convergents of the continued fraction x.

      (%i1) cf (rat (ev (%pi, numer)));

      `rat' replaced 3.141592653589793 by 103993/33102 =3.141592653011902
      (%o1)                  [3, 7, 15, 1, 292]
      (%i2) cfexpand (%);
                               [ 103993  355 ]
      (%o2)                    [             ]
                               [ 33102   113 ]
      (%i3) %[1,1]/%[2,1], numer;
      (%o3)                   3.141592653011902

  Categories: Continued fractions

Option variable: cflength

  Default value: 1

  `cflength` controls the number of terms of the continued fraction the function `cf` will give, as the value `cflength` times the period. Thus the default is to give one period.

      (%i1) cflength: 1$
      (%i2) cf ((1 + sqrt(5))/2);
      (%o2)                    [1, 1, 1, 1, 2]
      (%i3) cflength: 2$
      (%i4) cf ((1 + sqrt(5))/2);
      (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
      (%i5) cflength: 3$
      (%i6) cf ((1 + sqrt(5))/2);
      (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

  Categories: Continued fractions

Function: divsum
`divsum` (n, k)
`divsum` (n)

  `divsum (n, k)` returns the sum of the divisors of n raised to the k'th power.

  `divsum (n)` returns the sum of the divisors of n.

      (%i1) divsum (12);
      (%o1)                          28
      (%i2) 1 + 2 + 3 + 4 + 6 + 12;
      (%o2)                          28
      (%i3) divsum (12, 2);
      (%o3)                          210
      (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
      (%o4)                          210

  Categories: Number theory

Function: euler (n)

  Returns the n'th Euler number for nonnegative integer n. Euler numbers equal to zero are suppressed if `zerobern` is `false`.

  For the Euler-Mascheroni constant, see `%gamma`.

      (%i1) zerobern: true$
      (%i2) map (euler, [0, 1, 2, 3, 4, 5, 6]);
      (%o2)               [1, 0, - 1, 0, 5, 0, - 61]
      (%i3) zerobern: false$
      (%i4) map (euler, [0, 1, 2, 3, 4, 5, 6]);
      (%o4)               [1, - 1, 5, - 61, 1385, - 50521, 2702765]

  Categories: Number theory

Option variable: factors_only

  Default value: `false`

  Controls the value returned by `ifactors`. The default `false` causes `ifactors` to provide information about multiplicities of the computed prime factors. If `factors_only` is set to `true`, `ifactors` returns nothing more than a list of prime factors.

  Example: See `ifactors`.

  Categories: Number theory

Function: fib (n)

  Returns the n'th Fibonacci number. `fib(0)` is equal to 0 and `fib(1)` equal to 1, and `fib (-n)` equal to `(-1)^(n + 1) * fib(n)`.

  After calling `fib`, `prevfib` is equal to `fib(n - 1)`, the Fibonacci number preceding the last one computed.

      (%i1) map (fib, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o1)           [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21]

  Categories: Number theory

Function: fibtophi (expr)

  Expresses Fibonacci numbers in expr in terms of the constant `%phi`, which is `(1 + sqrt(5))/2`, approximately 1.61803399.

  Examples:

      (%i1) fibtophi (fib (n));
                                 n             n
                             %phi  - (1 - %phi)
      (%o1)                  -------------------
                                 2 %phi - 1
      (%i2) fib (n-1) + fib (n) - fib (n+1);
      (%o2)          - fib(n + 1) + fib(n) + fib(n - 1)
      (%i3) fibtophi (%);
                  n + 1             n + 1       n             n
              %phi      - (1 - %phi)        %phi  - (1 - %phi)
      (%o3) - --------------------------- + -------------------
                      2 %phi - 1                2 %phi - 1
                                                n - 1             n - 1
                                            %phi      - (1 - %phi)
                                          + ---------------------------
                                                    2 %phi - 1
      (%i4) ratsimp (%);
      (%o4)                           0

  Categories: Number theory

Function: ifactors (n)

  For a positive integer n returns the factorization of n. If `n=p1^e1..pk^nk` is the decomposition of n into prime factors, ifactors returns `[[p1, e1], ... , [pk, ek]]`.

  Factorization methods used are trial divisions by primes up to 9973, Pollard's rho and p-1 method and elliptic curves.

  The value returned by `ifactors` is controlled by the option variable `factors_only`. The default `false` causes `ifactors` to provide information about the multiplicities of the computed prime factors. If `factors_only` is set to `true`, `ifactors` simply returns the list of prime factors.

      (%i1) ifactors(51575319651600);
      (%o1)     [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]]
      (%i2) apply("*", map(lambda([u], u[1]^u[2]), %));
      (%o2)                        51575319651600
      (%i3) ifactors(51575319651600), factors_only : true;
      (%o3)                   [2, 3, 5, 1583, 9050207]

  Categories: Number theory

Function: igcdex (n, k)

  Returns a list `[a, b, u]` where u is the greatest common divisor of n and k, and u is equal to `a n + b k`. The arguments n and k must be integers.

  `igcdex` implements the Euclidean algorithm. See also `gcdex`.

  The command `load(gcdex)` loads the function.

  Examples:

      (%i1) load(gcdex)$

      (%i2) igcdex(30,18);
      (%o2)                      [- 1, 2, 6]
      (%i3) igcdex(1526757668, 7835626735736);
      (%o3)            [845922341123, - 164826435, 4]
      (%i4) igcdex(fib(20), fib(21));
      (%o4)                   [4181, - 2584, 1]

  Categories: Number theory

Function: inrt (x, n)

  Returns the integer n'th root of the absolute value of x.

      (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
      (%i2) map (lambda ([a], inrt (10^a, 3)), l);
      (%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]

  Categories: Number theory

Function: inv_mod (n, m)

  Computes the inverse of n modulo m. `inv_mod (n,m)` returns `false`, if n is a zero divisor modulo m.

      (%i1) inv_mod(3, 41);
      (%o1)                           14
      (%i2) ratsimp(3^-1), modulus = 41;
      (%o2)                           14
      (%i3) inv_mod(3, 42);
      (%o3)                          false

  Categories: Number theory

Function: isqrt (x)

  Returns the "integer square root" of the absolute value of x, which is an integer.

  Categories: Mathematical functions

Function: jacobi (p, q)

  Returns the Jacobi symbol of p and q.

      (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
      (%i2) map (lambda ([a], jacobi (a, 9)), l);
      (%o2)         [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]

  Categories: Number theory

Function: lcm (expr_1, …, expr_n)

  Returns the least common multiple of its arguments. The arguments may be general expressions as well as integers.

  `load ("functs")` loads this function.

  Categories: Number theory

Function: lucas (n)

  Returns the n'th Lucas number. `lucas(0)` is equal to 2 and `lucas(1)` equal to 1, and `lucas(-n)` equal to `(-1)^(-n) * lucas(n)`.

      (%i1) map (lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o1)             [7, - 4, 3, - 1, 2, 1, 3, 4, 7, 11, 18, 29, 47]

  After calling `lucas`, the global variable `next_lucas` is equal to `lucas (n + 1)`, the Lucas number following the last returned. The example shows how Fibonacci numbers can be computed via `lucas` and `next_lucas`.

      (%i1) fib_via_lucas(n) :=
               block([lucas : lucas(n)],
               signum(n) * (2*next_lucas - lucas)/5 )$
      (%i2) map (fib_via_lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
      (%o2)             [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21]

  Categories: Number theory

Function: mod (x, y)

  If x and y are real numbers and y is nonzero, return `x - y * floor(x / y)`. Further for all real x, we have `mod (x, 0) = x`. For a discussion of the definition `mod (x, 0) = x`, see Section 3.4, of "Concrete Mathematics," by Graham, Knuth, and Patashnik. The function `mod (x, 1)` is a sawtooth function with period 1 with `mod (1, 1) = 0` and `mod (0, 1) = 0`.

  To find the principal argument (a number in the interval `(-%pi, %pi]`) of a complex number, use the function `x |-> %pi - mod (%pi - x, 2*%pi)`, where x is an argument.

  When x and y are constant expressions (`10 * %pi`, for example), `mod` uses the same big float evaluation scheme that `floor` and `ceiling` uses. Again, it's possible, although unlikely, that `mod` could return an erroneous value in such cases.

  For nonnumerical arguments x or y, `mod` knows several simplification rules:

      (%i1) mod (x, 0);
      (%o1)                           x
      (%i2) mod (a*x, a*y);
      (%o2)                      a mod(x, y)
      (%i3) mod (0, x);
      (%o3)                           0

  Categories: Mathematical functions

Function: next_prime (n)

  Returns the smallest prime bigger than n.

      (%i1) next_prime(27);
      (%o1)                       29

  Categories: Number theory

Function: partfrac (expr, var)

  Expands the expression expr in partial fractions with respect to the main variable var. `partfrac` does a complete partial fraction decomposition. The algorithm employed is based on the fact that the denominators of the partial fraction expansion (the factors of the original denominator) are relatively prime. The numerators can be written as linear combinations of denominators, and the expansion falls out.

      (%i1) 1/(1+x)^2 - 2/(1+x) + 2/(2+x);
                            2       2        1
      (%o1)               ----- - ----- + --------
                          x + 2   x + 1          2
                                          (x + 1)
      (%i2) ratsimp (%);
                                       x
      (%o2)                 - -------------------
                               3      2
                              x  + 4 x  + 5 x + 2
      (%i3) partfrac (%, x);
                            2       2        1
      (%o3)               ----- - ----- + --------
                          x + 2   x + 1          2
                                          (x + 1)

Function: power_mod (a, n, m)

  Uses a modular algorithm to compute `a^n mod m` where a and n are integers and m is a positive integer. If n is negative, `inv_mod` is used to find the modular inverse.

      (%i1) power_mod(3, 15, 5);
      (%o1)                          2
      (%i2) mod(3^15,5);
      (%o2)                          2
      (%i3) power_mod(2, -1, 5);
      (%o3)                          3
      (%i4) inv_mod(2,5);
      (%o4)                          3

  Categories: Number theory

Function: primep (n)

  Primality test. If `primep (n)` returns `false`, n is a composite number and if it returns `true`, n is a prime number with very high probability.

  For n less than 341550071728321 a deterministic version of Miller-Rabin's test is used. If `primep (n)` returns `true`, then n is a prime number.

  For n bigger than 341550071728321 `primep` uses `primep_number_of_tests` Miller-Rabin's pseudo-primality tests and one Lucas pseudo-primality test. The probability that a non-prime n will pass one Miller-Rabin test is less than 1/4. Using the default value 25 for `primep_number_of_tests`, the probability of n beeing composite is much smaller that 10^-15.

  Categories: Predicate functions · Number theory

Option variable: primep_number_of_tests

  Default value: 25

  Number of Miller-Rabin's tests used in `primep`.

  Categories: Number theory

Function: primes (start, end)

  Returns the list of all primes from start to end.

      (%i1) primes(3, 7);
      (%o1)                     [3, 5, 7]

  Categories: Number theory

Function: prev_prime (n)

  Returns the greatest prime smaller than n.

      (%i1) prev_prime(27);
      (%o1)                       23

  Categories: Number theory

Function: qunit (n)

  Returns the principal unit of the real quadratic number field `sqrt (n)` where n is an integer, i.e., the element whose norm is unity. This amounts to solving Pell's equation `a^2 - n b^2 = 1`.

      (%i1) qunit (17);
      (%o1)                     sqrt(17) + 4
      (%i2) expand (% * (sqrt(17) - 4));
      (%o2)                           1

  Categories: Number theory

Function: totient (n)

  Returns the number of integers less than or equal to n which are relatively prime to n.

  Categories: Number theory

Option variable: zerobern

  Default value: `true`

  When `zerobern` is `false`, `bern` excludes the Bernoulli numbers and `euler` excludes the Euler numbers which are equal to zero. See `bern` and `euler`.

  Categories: Number theory

Function: zeta (n)

  Returns the Riemann zeta function. If n is a negative integer, 0, or a positive even integer, the Riemann zeta function simplifies to an exact value. For a positive even integer the option variable `zeta%pi` has to be `true` in addition (See `zeta%pi`). For a floating point or bigfloat number the Riemann zeta function is evaluated numerically. Maxima returns a noun form `zeta (n)` for all other arguments, including rational noninteger, and complex arguments, or for even integers, if `zeta%pi` has the value `false`.

  `zeta(1)` is undefined, but Maxima knows the limit `limit(zeta(x), x, 1)` from above and below.

  The Riemann zeta function distributes over lists, matrices, and equations.

  See also `bfzeta` and `zeta%pi`.

  Examples:

      (%i1) zeta([-2, -1, 0, 0.5, 2, 3, 1+%i]);
                                                   2
                  1     1                       %pi
      (%o1) [0, - --, - -, - 1.460354508809586, ----, zeta(3),
                  12    2                        6
                                                          zeta(%i + 1)]
      (%i2) limit(zeta(x),x,1,plus);
      (%o2)                          inf
      (%i3) limit(zeta(x),x,1,minus);
      (%o3)                         minf

  Categories: Number theory

Option variable: zeta%pi

  Default value: `true`

  When `zeta%pi` is `true`, `zeta` returns an expression proportional to `%pi^n` for even integer `n`. Otherwise, `zeta` returns a noun form `zeta (n)` for even integer `n`.

  Examples:

      (%i1) zeta%pi: true$
      (%i2) zeta (4);
                                       4
                                    %pi
      (%o2)                         ----
                                     90
      (%i3) zeta%pi: false$
      (%i4) zeta (4);
      (%o4)                        zeta(4)

  Categories: Number theory

Function: zn_add_table (n)

  Shows an addition table of all elements in (Z/nZ).

  See also `zn_mult_table`, `zn_power_table`.

  Categories: Number theory

Function: zn_characteristic_factors (n)

  Returns a list containing the characteristic factors of the totient of n.

  Using the characteristic factors a multiplication group modulo n can be expressed as a group direct product of cyclic subgroups.

  In case the group itself is cyclic the list only contains the totient and using `zn_primroot` a generator can be computed. If the totient splits into more than one characteristic factors `zn_factor_generators` finds generators of the corresponding subgroups.

  Each of the `r` factors in the list divides the right following factors. For the last factor `f_r` therefore holds `a^f_r = 1 (mod n)` for all `a` in the group.

  If `n > 2`, then `totient(n)/2^r` is the number of quadratic residues, and each of these has `2^r` square roots.

  See also `totient`, `zn_primroot`, `zn_factor_generators`.

  Examples:

  The multiplication group modulo `14` is cyclic and its `6` elements can be generated by a primitive root.

      (%i1) [zn_characteristic_factors(14), phi: totient(14)];
      (%o1)                              [[6], 6]
      (%i2) [zn_factor_generators(14), g: zn_primroot(14)];
      (%o2)                              [[3], 3]
      (%i3) M14: makelist(power_mod(g,i,14), i,0,phi-1);
      (%o3)                         [1, 3, 9, 13, 11, 5]

  The multiplication group modulo `15` is not cyclic and its `8` elements can be generated by two factor generators.

      (%i1) [[f1,f2]: zn_characteristic_factors(15), totient(15)];
      (%o1)                             [[2, 4], 8]
      (%i2) [[g1,g2]: zn_factor_generators(15), zn_primroot(15)];
      (%o2)                           [[11, 7], false]
      (%i3) UG1: makelist(power_mod(g1,i,15), i,0,f1-1);
      (%o3)                               [1, 11]
      (%i4) UG2: makelist(power_mod(g2,i,15), i,0,f2-1);
      (%o4)                            [1, 7, 4, 13]
      (%i5) M15: create_list(mod(i*j,15), i,UG1, j,UG2);
      (%o5)                      [1, 7, 4, 13, 11, 2, 14, 8]

  For the last characteristic factor `4` it holds that `a^4 = 1 (mod 15)` for all `a` in `M15`.

  `M15` has two characteristic factors and therefore `8/2^2` quadratic residues, and each of these has `2^2` square roots.

      (%i6) zn_power_table(15);
                                     [ 1   1  1   1 ]
                                     [              ]
                                     [ 2   4  8   1 ]
                                     [              ]
                                     [ 4   1  4   1 ]
                                     [              ]
                                     [ 7   4  13  1 ]
      (%o6)                          [              ]
                                     [ 8   4  2   1 ]
                                     [              ]
                                     [ 11  1  11  1 ]
                                     [              ]
                                     [ 13  4  7   1 ]
                                     [              ]
                                     [ 14  1  14  1 ]
      (%i7) map(lambda([i], zn_nth_root(i,2,15)), [1,4]);
      (%o7)                   [[1, 4, 11, 14], [2, 7, 8, 13]]

  Categories: Number theory

Function: zn_determinant (matrix, p)

  Uses the technique of LU-decomposition to compute the determinant of matrix over (Z/pZ). p must be a prime.

  However if the determinant is equal to zero the LU-decomposition might fail. In that case `zn_determinant` computes the determinant non-modular and reduces thereafter.

  See also `zn_invert_by_lu`.

  Examples:

      (%i1) m : matrix([1,3],[2,4]);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 2  4 ]
      (%i2) zn_determinant(m, 5);
      (%o2)                               3
      (%i3) m : matrix([2,4,1],[3,1,4],[4,3,2]);
                                     [ 2  4  1 ]
                                     [         ]
      (%o3)                          [ 3  1  4 ]
                                     [         ]
                                     [ 4  3  2 ]
      (%i4) zn_determinant(m, 5);
      (%o4)                               0

  Categories: Number theory

Function: zn_factor_generators (n)

  Returns a list containing factor generators corresponding to the characteristic factors of the totient of n.

  For remarks and examples see `zn_characteristic_factors`.

  Categories: Number theory

Function: zn_invert_by_lu (matrix, p)

  Uses the technique of LU-decomposition to compute the modular inverse of matrix over (Z/pZ). p must be a prime and matrix invertible. `zn_invert_by_lu` returns `false` if matrix is not invertible.

  See also `zn_determinant`.

  Example:

      (%i1) m : matrix([1,3],[2,4]);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 2  4 ]
      (%i2) zn_determinant(m, 5);
      (%o2)                               3
      (%i3) mi : zn_invert_by_lu(m, 5);
                                      [ 3  4 ]
      (%o3)                           [      ]
                                      [ 1  2 ]
      (%i4) matrixmap(lambda([a], mod(a, 5)), m . mi);
                                      [ 1  0 ]
      (%o4)                           [      ]
                                      [ 0  1 ]

  Categories: Number theory

Function: zn_log
`zn_log` (a, g, n)
`zn_log` (a, g, n, [[p1, e1], …, [pk, ek]])

  Computes the discrete logarithm. Let (Z/nZ)* be a cyclic group, g a primitive root modulo n and let a be a member of this group. `zn_log (a, g, n)` then solves the congruence `g^x = a mod n`.

  The applied algorithm needs a prime factorization of `totient(n)`. This factorization might be time consuming as well and in some cases it can be useful to factor first and then to pass the list of factors to `zn_log` as the fourth argument. The list must be of the same form as the list returned by `ifactors(totient(n))` using the default option `factors_only : false`.

  The algorithm uses a Pohlig-Hellman-reduction and Pollard's Rho-method for discrete logarithms. The run time of `zn_log` primarily depends on the bitlength of the totient's greatest prime factor.

  See also `zn_primroot`, `zn_order`, `ifactors`, `totient`.

  Examples:

  `zn_log (a, g, n)` solves the congruence `g^x = a mod n`.

      (%i1) n : 22$
      (%i2) g : zn_primroot(n);
      (%o2)                               7
      (%i3) ord_7 : zn_order(7, n);
      (%o3)                              10
      (%i4) powers_7 : makelist(power_mod(g, x, n), x, 0, ord_7 - 1);
      (%o4)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
      (%i5) zn_log(21, g, n);
      (%o5)                               5
      (%i6) map(lambda([x], zn_log(x, g, n)), powers_7);
      (%o6)                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  The optional fourth argument must be of the same form as the list returned by `ifactors(totient(n))`. The run time primarily depends on the bitlength of the totient's greatest prime factor.

      (%i1) (p : 2^127-1, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors(p - 1)$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                              43
      (%i4) a : power_mod(g, 1234567890, p)$
      (%i5) zn_log(a, g, p, ifs);
      (%o5)                          1234567890
      (%i6) time(%o5);
      (%o6)                            [1.204]
      (%i7) f_max : last(ifs);
      (%o7)                       [77158673929, 1]
      (%i8) slength( printf(false, "~b", f_max[1]) );
      (%o8)                              37

  Categories: Number theory

Function: zn_mult_table
`zn_mult_table` (n)
`zn_mult_table` (n, all)

  Without the optional argument all `zn_mult_table(n)` shows a multiplication table of all elements in (Z/nZ)* which are all elements invertible modulo n.

  The optional argument all causes the table to be printed for all non-zero elements.

  See also `zn_add_table`, `zn_power_table`.

  Examples:

      (%i1) zn_mult_table(4);
                                      [ 1  3 ]
      (%o1)                           [      ]
                                      [ 3  1 ]
      (%i2) zn_mult_table(4, all);
                                     [ 1  2  3 ]
                                     [         ]
      (%o2)                          [ 2  0  2 ]
                                     [         ]
                                     [ 3  2  1 ]

  Categories: Number theory

Function: zn_nth_root
`zn_nth_root` (x, n, m)
`zn_nth_root` (x, n, m, [[p1, e1], …, [pk, ek]])

  Returns a list containing the n-th roots of x if it is a member of the multiplication group (Z/mZ)*, i.e. coprime to m, and if it is an n-th power of a member of (Z/mZ)*. Otherwise `zn_nth_root` returns `false`.

  `zn_nth_root` uses an algorithm by Adleman, Manders and Miller and needs a prime factorization of the modulus m. In case the factorization of m is known the list of factors can be passed as the fourth argument. This optional argument must be of the same form as the list returned by `ifactors(m)` using the default option `factors_only: false`.

  Examples:

  A power table of the multiplication group modulo `14` followed by a list of lists containing all n-th roots of `1` with n from `1` to `6`.

      (%i1) zn_power_table(14);
                               [ 1   1   1   1   1   1 ]
                               [                       ]
                               [ 3   9   13  11  5   1 ]
                               [                       ]
                               [ 5   11  13  9   3   1 ]
      (%o1)                    [                       ]
                               [ 9   11  1   9   11  1 ]
                               [                       ]
                               [ 11  9   1   11  9   1 ]
                               [                       ]
                               [ 13  1   13  1   13  1 ]
      (%i2) makelist(zn_nth_root(1,n,14), n,1,6);
      (%o2)  [[1], [1, 13], [1, 9, 11], [1, 13], [1], [1, 3, 5, 9, 11, 13]]

  In this RSA-like example the factorization of the modulus is known and passed as the fourth argument.

      (%i1) p: 2^107-1$  q: 2^127-1$  N: p*q$

      (%i4) ibase: obase: 16$

      (%i5) msg: 11223344556677889900aabbccddeeff$

      (%i6) enc: power_mod(msg, 10001, N);
      (%o6)    1a8db7892ae588bdc2be25dd5107a425001fe9c82161abc673241c8b383
      (%i7) zn_nth_root(enc, 10001, N, [[p,1],[q,1]]);
      (%o7)               [11223344556677889900aabbccddeeff]

  Categories: Number theory

Function: zn_order
`zn_order` (x, n)
`zn_order` (x, n, [[p1, e1], …, [pk, ek]])

  Returns the order of x if it is a unit of the finite group (Z/nZ)* or returns `false`. x is a unit modulo n if it is coprime to n.

  The applied algorithm needs a prime factorization of `totient(n)`. This factorization might be time consuming in some cases and it can be useful to factor first and then to pass the list of factors to `zn_log` as the third argument. The list must be of the same form as the list returned by `ifactors(totient(n))` using the default option `factors_only : false`.

  See also `zn_primroot`, `ifactors`, `totient`.

  Examples:

  `zn_order` computes the order of the unit x in (Z/nZ)*.

      (%i1) n : 22$
      (%i2) g : zn_primroot(n);
      (%o2)                               7
      (%i3) units_22 : sublist(makelist(i,i,1,21), lambda([x], gcd(x, n) = 1));
      (%o3)              [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
      (%i4) (ord_7 : zn_order(7, n)) = totient(n);
      (%o4)                            10 = 10
      (%i5) powers_7 : makelist(power_mod(g,i,n), i,0,ord_7 - 1);
      (%o5)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
      (%i6) map(lambda([x], zn_order(x, n)), powers_7);
      (%o6)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
      (%i7) map(lambda([x], ord_7/gcd(x, ord_7)), makelist(i, i,0,ord_7 - 1));
      (%o7)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
      (%i8) totient(totient(n));
      (%o8)                               4

  The optional third argument must be of the same form as the list returned by `ifactors(totient(n))`.

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                               3
      (%i4) is( (ord_3 : zn_order(g, p, ifs)) = totient(p) );
      (%o4)                             true
      (%i5) map(lambda([x], ord_3/zn_order(x, p, ifs)), makelist(i,i,2,15));
      (%o5)        [22, 1, 44, 10, 5, 2, 22, 2, 8, 2, 1, 1, 20, 1]

  Categories: Number theory

Function: zn_power_table
`zn_power_table` (n)
`zn_power_table` (n, opt_1, opt_2)

  Without any optional argument `zn_power_table(n)` shows a power table of all elements in (Z/nZ)* which are all elements invertible modulo n. The exponent loops from `1` to the greatest characteristic factor of `totient(n)` and the table ends with a column of ones on the right side.

  The optional arguments can be `all` and/or a positive integer `i` in any order.

  The argument `all` causes the table to be printed for all non-zero elements. One more column is added and in case the modulus factors into different primes the last column is equal to the first.

  If an additional integer argument `i` is given the exponent loops from `1` to `i`.

  See also `zn_add_table`, `zn_mult_table`.

  Examples:

      (%i1) zn_power_table(6);
                                      [ 1  1 ]
      (%o1)                           [      ]
                                      [ 5  1 ]
      (%i2) zn_power_table(6, all);
                                     [ 1  1  1 ]
                                     [         ]
                                     [ 2  4  2 ]
                                     [         ]
      (%o2)                          [ 3  3  3 ]
                                     [         ]
                                     [ 4  4  4 ]
                                     [         ]
                                     [ 5  1  5 ]
      (%i3) zn_power_table(6,all,5);
                                  [ 1  1  1  1  1 ]
                                  [               ]
                                  [ 2  4  2  4  2 ]
                                  [               ]
      (%o3)                       [ 3  3  3  3  3 ]
                                  [               ]
                                  [ 4  4  4  4  4 ]
                                  [               ]
                                  [ 5  1  5  1  5 ]

  Categories: Number theory

Function: zn_primroot
`zn_primroot` (n)
`zn_primroot` (n, [[p1, e1], …, [pk, ek]])

  If the multiplicative group (Z/nZ)* is cyclic, `zn_primroot` computes the smallest primitive root modulo n. (Z/nZ)* is cyclic if n is equal to `2`, `4`, `p^k` or `2*p^k`, where `p` is prime and greater than `2` and `k` is a natural number. `zn_primroot` performs an according pretest if the option variable `zn_primroot_pretest` (default: `false`) is set to `true`. In any case the computation is limited by the upper bound `zn_primroot_limit`.

  If (Z/nZ)* is not cyclic or if there is no primitive root up to `zn_primroot_limit`, `zn_primroot` returns `false`.

  The applied algorithm needs a prime factorization of `totient(n)`. This factorization might be time consuming in some cases and it can be useful to factor first and then to pass the list of factors to `zn_log` as an additional argument. The list must be of the same form as the list returned by `ifactors(totient(n))` using the default option `factors_only : false`.

  See also `zn_primroot_p`, `zn_order`, `ifactors`, `totient`.

  Examples:

  `zn_primroot` computes the smallest primitive root modulo n or returns `false`.

      (%i1) n : 14$
      (%i2) g : zn_primroot(n);
      (%o2)                               3
      (%i3) zn_order(g, n) = totient(n);
      (%o3)                             6 = 6
      (%i4) n : 15$
      (%i5) zn_primroot(n);
      (%o5)                             false

  The optional second argument must be of the same form as the list returned by `ifactors(totient(n))`.

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) g : zn_primroot(p, ifs);
      (%o3)                               3
      (%i4) [time(%o2), time(%o3)];
      (%o4)                    [[15.556972], [0.004]]
      (%i5) is(zn_order(g, p, ifs) = p - 1);
      (%o5)                             true
      (%i6) n : 2^142 + 216$
      (%i7) ifs : ifactors(totient(n))$
      (%i8) zn_primroot(n, ifs),
            zn_primroot_limit : 200, zn_primroot_verbose : true;
      `zn_primroot' stopped at zn_primroot_limit = 200
      (%o8)                             false

  Categories: Number theory

Option variable: zn_primroot_limit

  Default value: `1000`

  If `zn_primroot` cannot find a primitve root, it stops at this upper bound. If the option variable `zn_primroot_verbose` (default: `false`) is set to `true`, a message will be printed when `zn_primroot_limit` is reached.

  Categories: Number theory

Function: zn_primroot_p
`zn_primroot_p` (x, n)
`zn_primroot_p` (x, n, [[p1, e1], …, [pk, ek]])

  Checks whether x is a primitive root in the multiplicative group (Z/nZ)*.

  The applied algorithm needs a prime factorization of `totient(n)`. This factorization might be time consuming and in case `zn_primroot_p` will be consecutively applied to a list of candidates it can be useful to factor first and then to pass the list of factors to `zn_log` as a third argument. The list must be of the same form as the list returned by `ifactors(totient(n))` using the default option `factors_only : false`.

  See also `zn_primroot`, `zn_order`, `ifactors`, `totient`.

  Examples:

  `zn_primroot_p` as a predicate function.

      (%i1) n : 14$
      (%i2) units_14 : sublist(makelist(i,i,1,13), lambda([i], gcd(i, n) = 1));
      (%o2)                     [1, 3, 5, 9, 11, 13]
      (%i3) zn_primroot_p(13, n);
      (%o3)                            false
      (%i4) sublist(units_14, lambda([x], zn_primroot_p(x, n)));
      (%o4)                            [3, 5]
      (%i5) map(lambda([x], zn_order(x, n)), units_14);
      (%o5)                      [1, 6, 6, 3, 3, 2]

  The optional third argument must be of the same form as the list returned by `ifactors(totient(n))`.

      (%i1) (p : 2^142 + 217, primep(p));
      (%o1)                             true
      (%i2) ifs : ifactors( totient(p) )$
      (%i3) sublist(makelist(i,i,1,50), lambda([x], zn_primroot_p(x, p, ifs)));
      (%o3)      [3, 12, 13, 15, 21, 24, 26, 27, 29, 33, 38, 42, 48]
      (%i4) [time(%o2), time(%o3)];
      (%o4)                   [[7.748484], [0.036002]]

  Categories: Predicate functions · Number theory

Option variable: zn_primroot_pretest

  Default value: `false`

  The multiplicative group (Z/nZ)* is cyclic if n is equal to `2`, `4`, `p^k` or `2*p^k`, where `p` is prime and greater than `2` and `k` is a natural number.

  `zn_primroot_pretest` controls whether `zn_primroot` will check if one of these cases occur before it computes the smallest primitive root. Only if `zn_primroot_pretest` is set to `true` this pretest will be performed.

  Categories: Number theory

Option variable: zn_primroot_verbose

  Default value: `false`

  Controls whether `zn_primroot` prints a message when reaching `zn_primroot_limit`.

  Categories: Number theory

[ << ] | [ >> ] |  |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

This document was generated by Robert Dodier on September, 17 2015 using texi2html 1.76.