UserManual

arith1

Miscellaneous arithmetic functions are provided.

Functions

floorsqrt(a)

Return the floor of square root of the given integer a.

floorpowerroot(n, k)

Return the floor of k-th power root of the given integer n.

legendre(a, m)

Return Legendre symbol (a/m) if m is a prime. Return Jacobi symbol otherwise.

modsqrt(a, p)

Return one of the square roots of a for mod p. p must be an odd prime.
(renamed from 'sqroot' in 0.4.1)

expand(n, m)

Return m-adic expansion for n. n and m should satisfy n > m > 0.

inverse(x, p)

Return inverse of x for modulo p.

CRT(nlist)

Return the uniquely determined integer satisfying all modulus conditions given by nlist. The modulus condition nlist is a list like [(1,2), (2,3), (3,5)], which means the number should be 1 mod 2, 2 mod 3 and 3 mod 5. All moduli must be pairwise coprime.

This function is Chinese Rmainder Theorem using Algorithm 2.1.7 of C.Pomerance and R.Crandall's book.

AGM(a, b)

Arithmetic-Geometric Mean.

_BhaskaraBrouncker(n):

Return the minimum tuple (p,q) such that:

       p ** 2 - n * q ** 2 = 1 or -1,

for positive integer n, which is not a square.

A good approximation for square root of n is given by the ratio p/q; the error is at most 1/2*q**2.

vp(n, p [,k])

The returned value is a tuple of p-adic valuation of n and its coprime part. If k is given, it is added to the valuation.

moved from prime (0.4.1).

issquare(n)

Test whether a given integer n is a square number or not. If n is a square number, the function returns its square root.
(new in 0.4.1)

log(n [,base])

Return integer part of logarithm of the given integer n to the base. The default value for base is 2. (new in 0.5.0)


Last-modified: 2006-11-21 (Ва) 15:42:37