[推荐]常用数论函数

cjsh

常用数论函数在MAGMA中归类：像求整函数 Truncate(n1) =12345678901111 AbsoluteValue(n) : RngIntElt -> RngIntElt Abs(n) : RngIntElt -> RngIntElt Absolute value of the integer n. Ilog2(n) : RngIntElt -> RngIntElt The integral part of the logarithm to the base two of the positive integer n. Ilog(b, n) : RngIntElt, RngIntElt -> RngIntElt The integral part of the logarithm to the base b of the positive integer n i.e., the largest integer k such that bk ≤n. The integer b must be greater than or equal to two. Quotrem(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt Returns both the quotient q and remainder r obtained upon dividing the integer m by the integer n, that is, m = q.n + r, where 0 ≤r < n if n>0 and n RngIntElt, RngIntElt The valuation of the integer x at the prime p. This is the largest integer v for which pv divides x. If x = 0 then v = ∞. The optional second return value is the integer u such that x = pv u. Iroot(a, n) : RngIntElt, RngIntElt -> RngIntElt Given a positive integer a, return the integer b= ⌊root n of a⌋, i.e. the integral part of the n-th root of a. To obtain the actual root (as a real number), a must e coerced into a real field and the function Root applied. Sign(n) : RngIntElt -> RngIntElt Returns -1, 0 or 1 depending upon whether the integer n is negative, zero or positive, respectively. Ceiling(n) : RngIntElt -> RngIntElt The ceiling of the integer n, that is, n itself. Floor(n) : RngIntElt -> RngIntElt The floor of the integer n, that is, n itself. Round(n) : RngIntElt -> RngIntElt This function rounds the integer n to itself. Truncate(n) : RngIntElt -> RngIntElt This function returns the integer truncation of the integer n, that is, n itself. SquarefreeFactorization(n) : RngIntElt -> RngIntElt, RngIntElt Given a non-negative integer n, return a squarefree integer x as well as a positive integer y, such that n=xy2. Isqrt(n) : RngIntElt -> RngIntElt Lcm(s, t) : RngIntEltFact, RngIntEltFact -> RngIntEltFact Gcd(s, t) : RngIntEltFact, RngIntEltFact -> RngIntEltFact SquarefreeFactorization(f) : RngIntEltFact -> RngIntEltFact, RngIntEltFact MoebiusMu(f) : RngIntEltFact -> RngIntElt Divisors(f) : RngIntEltFact -> SeqEnum PrimeDivisors(f) : RngIntEltFact -> SeqEnum NumberOfDivisors(f) : RngIntEltFact -> RngIntElt SumOfDivisors(f) : RngIntEltFact -> RngIntElt IsOne(s) : RngIntEltFact -> BoolElt IsOdd(s) : RngIntEltFact -> BoolElt IsEven(s) : RngIntEltFact -> BoolElt IsUnit(s) : RngIntEltFact -> BoolElt IsPrime(s) : RngIntEltFact -> BoolElt IsPrimePower(s) : RngIntEltFact -> BoolElt IsSquare(s) : RngIntEltFact -> BoolElt IsSquarefree(s) : RngIntEltFact -> BoolElt Modexp(n, k, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt The modular power nk mod m, where n is an integer, k is an integer and m is an integer greater than one. If k is negative, n must have an inverse i modulo m, and the result is then i - k mod m. The result is always an integer r with 0≤r< m. n mod m : RngIntElt, RngIntElt -> RngIntElt Remainder upon dividing the integer n by the integer m. The result always has the same sign as m. An error results if m is zero. Modinv(n, m) : RngIntElt, RngIntElt -> RngIntElt InverseMod(n, m) : RngIntElt, RngIntElt -> RngIntElt Given an integer n and a positive integer m, such that n and m are coprime, return an inverse u of n modulo m, that is, return an integer 1≤u BoolElt, RngIntElt Given an integer n and an integer m ≥2, this function returns an integer b such that 0 ≤b < m and b2 = n mod m if such b exists; an error results if no such root exists. Modorder(n, m) : RngIntElt, RngIntElt -> RngIntElt For integers n and m, m > 1, the function returns the least integer k ≥1 such that nk = 1 mod m, or zero if gcd(n, m) != 1. IsPrimitive(n, m) : RngIntElt, RngIntElt -> BoolElt Returns true if n is a primitive root for m, false otherwise (0 < n < m). PrimitiveRoot(m) : RngIntElt -> RngIntElt Given an integer m > 1, this function returns an integer value defined as follows: If Z/mZ has a primitive root and the function is successful in finding it, the root a is returned. If Z/mZ has a primitive root but the algorithm does not succeed in finding it, or Z/mZ does not possess a primitive root, then zero is returned. The Solution of Modular Equations The functions described here can be used if an occasional modular operation is required; the results are integers again. For more extensive modular arithmetic it is preferable to convert to residue class ring arithmetic. See section Residue Class Rings for details. Solution(a, b, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt If a solution exists to the linear congruence ax = b mod m, then returns x0, k such that x = x0 + i * k represents the complete set of solutions, where i can be any integer. Otherwise, returns -1. ChineseRemainderTheorem(X, N) : [RngIntElt], [RngIntElt] -> RngIntElt CRT(X, N) : [RngIntElt], [RngIntElt] -> RngIntElt Apply the Chinese Remainder Theorem to the integer sequences X and N. The sequences must have the same length, k say. The function returns the unique integer x in the range 0 ≤x < LCM(N[1].... .N[k]) such that x = X mod N. The elements of N must all be positive integers greater than one. If there is no solution, then -1 is returned. Solution(A, B, N) : [RngIntElt], [RngIntElt],[RngIntElt] -> RngIntElt Return a solution x to the system of simultaneous linear congruences defined by the integer sequences A, B and N. Each of these sequences must have the same number of terms, k say. The elements of N must all be positive integers greater than one. The i-th congruence is A .x = B mod N. The solution x will satisfy 0 ≤x < LCM(N[1].... .N[k]). If no solution exists, -1 is returned. NormEquation(d, m) : RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt NormEquation(d, m: parameters)) : RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt Factorization: [] Default: [ ]Given a positive integer d and a non-negative integer m, return true and two non-negative integers x and y, such that x2 + y2d = m, if such a solution exists. If such a solution does not exists only the value false is returned. If the factorization of m is known, it may be supplied as the value of the parameter Factorization to speed up the computation. Truncate(n1) 12345678901111

cjsh

PARI/GP 中的：
addprimes     bestappr      bezout        bezoutres     bigomega
binomial      chinese       content       contfrac      contfracpnqn
core          coredisc      dirdiv        direuler      dirmul
divisors      eulerphi      factor        factorback    factorcantor
factorff      factorial     factorint     factormod     ffinit
fibonacci     gcd           hilbert       isfundamental ispower
isprime       ispseudoprime issquare      issquarefree  kronecker
lcm           moebius       nextprime     numbpart      numdiv
omega         precprime     prime         primepi       primes
qfbclassno    qfbcompraw    qfbhclassno   qfbnucomp     qfbnupow
qfbpowraw     qfbprimeform  qfbred        qfbsolve      quadclassunit
quaddisc      quadgen       quadhilbert   quadpoly      quadray
quadregulator quadunit      removeprimes  sigma         sqrtint
zncoppersmith znlog         znorder       znprimroot    znstar
[br][br]-=-=-=-=- 以下内容由 cjsh 在 时添加 -=-=-=-=-
bezout(12345,54321)
%14 = [3617, -822, 3]
x= 12345 = 3 × 5 × 823
y= 54321 = 3 × 19 × 953
最大公因式(x,y) = 3 = 3
最小公倍数(x,y) = 223530915 = 3 × 5 × 19 × 823 × 953
Bezout 关系: 3617x + (-822) y = 3
以 y为除数的 x的辗转相除的过程序列:
被除数   商   除数  余数  
12345  =  0  × 54321  +  12345  
54321  =  4  × 12345  +  4941  
12345  =  2  × 4941  +  2463  
4941  =  2  × 2463  +  15  
2463  =  164  × 15  +  3  
15  =  5  × 3  +  0  
多项式的：连商带余都给了
(14:33) gp > ?bezoutres
bezoutres(x,y): gives a 3-dimensional row vector [u,v,d] such that
d=resultant(x,y) and u*x+v*y=d, where x and y are polynomials.
(14:35) gp > x=p^4+p^3+3
%1 = p^4 + p^3 + 3
(14:36) gp > y=p+1
%2 = p + 1
(14:36) gp > bezoutres(x,y)
%3 = [1, -p^3, 3]
孙子：
(16:10) gp > chinese(Mod(18,115),Mod(21,71))
%13 = Mod(7263, 8165)