| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
| 29.1 Functions and Variables for Number Theory |
| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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
Returns the n'th Bernoulli polynomial in the variable x.
Categories: Number theory
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
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
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
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
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:
(%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]
cfdisrep.
(%i1) cflength: 3$ (%i2) cfdisrep (cf (sqrt (3)))$ (%i3) ev (%, numer); (%o3) 1.731707317073171
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
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
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
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
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
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
Default value: false
Controls the value returned by ifactors
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
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
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
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
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
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
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
Returns the "integer square root" of the absolute value of x, which is an integer.
Categories: Mathematical functions
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
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
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
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
Returns the smallest prime bigger than n.
(%i1) next_prime(27); (%o1) 29
Categories: Number theory
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)
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
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
Default value: 25
Number of Miller-Rabin's tests used in primep.
Categories: Number theory
Returns the greatest prime smaller than n.
(%i1) prev_prime(27); (%o1) 23
Categories: Number theory
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
Returns the number of integers less than or equal to n which are relatively prime to n.
Categories: Number theory
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
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
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
Shows an addition table of all elements in (Z/nZ).
See also zn_mult_table
zn_power_table
Categories: Number theory
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
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
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
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
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
Without the optional argument all 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 totient(n) and the table ends with
a column of ones on the right side.
The optional argument all causes the table to be printed for all
non-zero elements. In this case the exponent loops from 1 to
totient(n) + 1 and the last column is therefore equal to the first.
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 ]
Categories: Number theory
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
Default value: 1000
If zn_primroot
If the option variable zn_primroot_verbose
set to true, a message will be printed when zn_primroot_limit is reached.
Categories: Number theory
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
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
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
Default value: false
Controls whether zn_primroot
zn_primroot_limit
Categories: Number theory
| [ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated by Charlie & on July, 6 2015 using texi2html 1.76.