📄 description of calc.htm
字号:
and y of Pell's equation x<SUP>2</SUP>-dy<SUP>2</SUP>=epsilon is returned, where
epsilon=1 or -1. z=epsilon is also returned. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Ros]">Ros</A>][382], [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Ven]">Ven</A>][62], [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Knu]">Knu</A>][359], [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Po1]">Po1</A>][359], [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Sie]">Sie</A>][296], [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Dav]">Dav</A>][109]. Also
see <A href="http://www.numbertheory.org/pdfs/pell.pdf">manuscript</A>.)
<HR>
<A
name=[22]></A><TT>z=surd(d,t,u,v,&a[],&u[],&v[],&p[],&q[])</TT>
<BR>The continued fraction of the quadratic irrationality (u+t√d)/v, d > 1,
nonsquare, v > 0, is determined as far as the period. The period length z is
returned. a[] is the array of partial quotients, u[] and v[] give the complete
convergents (u[i]+√d)/v[i], p[] and q[] give the convergents p[i]/q[i]. Output
is sent to a file <TT>surd.out</TT>. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Ros]">Ros</A>][379-381]
and [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Knu]">Knu</A>][359].)
<HR>
<A name=[23]></A><TT>z=mpower(a,b,c)</TT> <BR>z=a<SUP>b</SUP>(mod c) is
returned.
<HR>
<A name=[24]></A><TT>z=inv(a,m)</TT> <BR>z=a<SUP>-1</SUP>(mod m) is returned.
(See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Knu]">Knu</A>][325].)
<HR>
<A name=[59]></A><TT>z=elliptic(n,m,p)</TT> <BR>The elliptic curve method is
used to try to find a factor z of a composite number n. <BR>Here m, p <
2<SUP>32</SUP> and 1279 ≥ m > 10, p ≥ 1.
<HR>
<A name=[25]></A><TT>z=factor(n)</TT> <BR>The factorization of n is performed
using the multiple polynomial quadratic sieve on numbers with < 55 digits.
The elliptic curve algorithm is used on numbers of ≥ 55 digits. z=<IMG alt=omega
src="DESCRIPTION OF CALC.files/omega.gif"> (n), the number of distinct prime
factors of n. There is an option to choose the number p of elliptic curves used.
(p=7 suffices to factor 10<SUP>100</SUP>+1. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Sil]">Sil</A>][325].)
<HR>
<A name=[26]></A><TT>z=tau(n)</TT> <BR>The divisor function z=d(n) is returned.
<HR>
<A name=[27]></A><TT>z=sigma(n)</TT> <BR>z=σ(n), the sum of the divisors of n,
is returned.
<HR>
<A name=[28]></A><TT>z=mobius(n)</TT> <BR>The Möbius function z=μ(n) is
returned.
<HR>
<A name=[29]></A><TT>z=euler(n)</TT> <BR>Euler's function z=φ(n) is returned.
<HR>
<A name=[30]></A><TT>z=lprimroot(n)</TT> <BR>The least primitive root mod p, an
odd prime, is returned.
<HR>
<A name=[31]></A><TT>z=orderm(a,n)</TT> <BR>The order of a (mod n) is returned.
<HR>
<A name=[32]></A><TT>z=lucas(n)</TT> <BR>n is subjected to a strong pseudoprime
test to base 2, together with a Lucas pseudoprime test. If z=0 is returned, n is
composite, while if z=1 is returned, then n is a Lucas probable prime, as well
as a base 2 strong pseudoprime. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Pom]">Pom</A>].)
<HR>
<A name=[33]></A><TT>serret(p,&x,&y)</TT> <BR>Here p is a prime of the
form 4n+1. Serret's algorithm is used to return integers x and y such that
p=x<SUP>2</SUP>+y<SUP>2</SUP>. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Wag]">Wag</A>].)
<HR>
<A name=[34]></A><TT>collatz(x,n)</TT> <BR>Collatz' 3x+1 conjecture is tested.
(See [<A href="http://www.numbertheory.org/calc/krm_calc.html#[Lag]">Lag</A>]
and <A href="http://www.numbertheory.org/3x+1/">3x+1 page</A>.) The iterates
x,T(x),... are printed iff n is nonzero.
<HR>
<A name=[54]></A><TT>cycle()</TT> <BR>This finds cycles for the generalised
Collatz mapping T, arising from starting numbers p, |p| ≤ RANGE/2. Trajectories
containing an iterate whose magnitude exceeds a prescribed value INFINITY are
deemed not to be ultimately cycling. T(x)=int(m[i]x/d)+X[i] if x=i (mod d). Here
the d nonzero moduli m[i] and d shifts X[i] are entered from the keyboard. (See
<A href="http://www.numbertheory.org/3x+1/">3x+1 page</A>.)<BR><A
name=cycle_clarification></A>If when x ≡ i (mod d), T(x) is given in the form
T(x)=(m[i]x+r[i])/d, where d divides m[i]i+r[i], then
X[i]=(m[i]i+r[i])/d-int(m[i]i/d)=r[i]/d+{m[i]i/d}, where {t} denotes the
fractional part of t.<BR>In particular, if k is odd, the "3x+k" mapping is given
by m[0]=1, m[1]=3, X[0]=0, X[1]=(k+1)/2.<BR>The output is sent to collatz.out.
<HR>
<A name=[35]></A><TT>miller(m,b)</TT> <BR>Here m > 1,b > 1 and m does not
divide b. Miller's test to base b is applied to m.
<HR>
<A name=[36]></A><TT>hermite( )</TT> <BR>The Hermite normal form HNF(A) of
an integer matrix A is found using the Kannan-Bachem algorithm. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Sim]">Sim</A>][349-357].)
<BR>The matrix can be entered either from the keyboard or from a file such as <PRE>2 3
1 -4 -7
3 2 4</PRE>in the case of a 2 x 3 matrix. The Hermite normal form is sent to a
file called hermite.out. A unimodular integer matrix P such that PA = HNF(A) is
sent to a file hermitep.out, if desired. The last line of this file contains the
value of rank(A).
<HR>
<A name=[37]></A><TT>improvep( )</TT> <BR>The output unimodular matrix
contained in the file hermitep.out is improved using LLL-Babai method, followed
by Gauss lattice reduction. <BR>The output is sent to a file improvep.out.
<HR>
<A name=[51]></A><TT>lllhermite( )</TT> <BR>This performs a recent LLL
based Hermite normal form algorithm due to Havas, Majewski and Matthews. The
output unimodular matrix P of a <A
href="http://www.expmath.org/expmath/volumes/7/7.html">recent paper</A> is sent
to lllhermitetrans.out. The HNF(A) is sent to lllhermitebas.out. In verbose
mode, the intermediate steps are printed out.
<HR>
<A name=[52]></A><TT>shermite(N)</TT> <BR>This performs the LLL algorithm on
[I<SUB>m</SUB>|N<SUP>n</SUP>A<SUB>1</SUB>|...|NA<SUB>n</SUB>], where A is an mxn
matrix of integers. The columns are scaled down by the corresponding power of N
for viewing convenience. The output matrix, in scaled form, is sent to
shermitebas.out. <BR>
<HR>
<A name=[38]></A><TT>smith( )</TT> <BR>The Smith normal form SNF(A) of an
integer matrix A is found using a pivoting strategy due to G. Havas. A cutoff
value is requested. When coefficients grow above this value in size, the MLLL
algorithm is used to reduce coefficient explosion. MLLL is also used at the
start of searching for each invariant factor, as it often yields small vectors
with potential small invariant factor components. Unimodular matrices P and Q
are found such that PAQ = SNF(A). the invariant factors, P and Q are sent to
files smith.out, smithp.out and smithq.out, respectively, if desired.
<HR>
<A name=[39]></A><TT>mlll( )</TT> <BR>The MLLL algorithm of M. Pohst is
applied to an integer matrix whose first row is non-zero. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Po2]">Po2</A>][209-210].)
<BR>The reduced matrix and transforming matrix are sent to files mlllbas.out and
mllltran.out, respectively.
<HR>
<A name=[61]></A><TT>axb( )</TT> <BR>This solves the linear system AX=B,
where A,X,B have integer coefficients and the first column of A is nonzero. In
the case of solubility, file axb.out is either the unique solution or a short
solution or the shortest solution, depending on choice; axbbas.out is a short
basis for the nullspace of A. (See <A
href="http://www.numbertheory.org/pdfs/ax=b.pdf">preprint</A>.)
<HR>
<A name=[40]></A><TT>fp( )</TT> <BR>This is the simplest form of the
Fincke-Pohst algorithm (see [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Po2]">Po2</A>][190]). This
takes an integer matrix with LI rows and a positive integer C as input and finds
all lattice vectors X with ||X||<SUP>2</SUP> ≤ C. The vectors found are sent to
a file called fp.out. It is a good idea to start with a matrix whose rows are
LLL reduced.
<HR>
<A name=[42]></A><TT>slv( )</TT> <BR>This finds the shortest vectors in the
lattice spanned by the LI family b[1],...,b[m]. It applies Fincke-Pohst to
examine all nonzero X in L satisfying ||X||<SUP>2</SUP> < C =
||b[1]||<SUP>2</SUP>. If it finds an X shorter than b[1], the new bound
C=||X||<SUP>2</SUP> is chosen. At the end, Finke-Pohst has only the shortest
vectors to enumerate. <BR>Only the vectors with highest positive coefficient of
b[i] are given. <BR>The output is also sent to slv.out.
<HR>
<A name=[41]></A><TT>inhomfp( )</TT> <BR>The inhomogeneous version of the
Fincke-Pohst algorithm. (See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Po2]">Po2</A>][190].)
<BR>Input: An m x M integer matrix A whose first m-1 rows are LI and which are
preferably in LLL reduced form. A positive integer C is also entered. Let L be
the lattice spanned by the first m-1 rows of A and let P be the last row of A.
<BR>Output: All lattice vectors X of L such that ||X-P||<SUP>2</SUP> ≤ C.
<BR>The vectors found are sent to a file called inhomfp.out.
<HR>
<A name=[44]></A><TT>e=rsae(p,q)</TT> <BR>Here p and q are distinct odd primes,
each > 355142 and e is the least integer such that gcd(e, (p-1)(q-1))=1 and
32<SUP>e</SUP>> pq. <BR>e is for use as an RSA encryption modulus.
<HR>
<A name=[45]></A><TT>encode(e,n)</TT> <BR>Here n=p*q, a product of primes each
greater than 355142. (p*q > 126126126126.) e is the RSA encryption modulus,
found using rsae( ) above. <BR>A string of non-control characters when
entered from the keyboard or from a file consisting of lines each containing
less than 500 characters. These characters have ascii values in the range
32-126. The message string is encoded using the RSA algorithm: every 4
characters are converted to ascii, joined as strings and the resulting large
number m is encoded as n = m<SUP>e</SUP>(mod p*q). The encoded numbers are sent
to a file "encoded.out", terminated by an entry -1.
<HR>
<A name=[46]></A><TT>decode(e,p,q)</TT> <BR>This calculates the decryption
modulus d, then decodes each number n in the file "encode": m =
n<SUP>d</SUP>(mod pq). The ascii characters are split off and the original
string of message characters is reformed. <BR>The encoded message is sent to a
file "decoded.out", as well as to the screen.
<HR>
<A name=[47]></A><TT>addcubicr( )</TT> <BR>The sum of two points on the
elliptic curve
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[48]></A><TT>powercubicr( )</TT> <BR>The point nP, where P is on
the elliptic curve
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[65]></A><TT>ordercubicr( )</TT> <BR>The order of point P on the
elliptic curve:
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[62]></A><TT>addcubicm( )</TT> <BR>The sum of two points on the
elliptic curve mod p:
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[63]></A><TT>powercubicm( )</TT> <BR>The point nP, where P is on
the elliptic curve mod p:
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[64]></A><TT>ordercubicm( )</TT> <BR>The order of point P on the
elliptic curve mod p:
y<SUP>2</SUP>+a<SUB>1</SUB>xy+a<SUB>3</SUB>y=x<SUP>3</SUP>+a<SUB>2</SUB>x<SUP>2</SUP>+a<SUB>4</SUB>x+a<SUB>6</SUB>
is calculated. The discriminant is also calculated.
<HR>
<A name=[57]></A><TT>convergents(a[ ],&p[ ],&q[ ])</TT>
<BR>The convergents p[0]/q[0],...,p[n]/q[n] of the continued fraction
[a[0];a[1],...,a[n]] are returned as arrays p[ ] and q[ ]. Here a[0]
is an integer, a[1],...,a[n] are positive integers.
<HR>
<A name=[58]></A><TT>lagrange("poly",&a[ ],m)</TT> <BR>"poly" is
a polynomial with integer coefficients, having no rational roots and having
exactly one real positive root x, this being > 1. The method of Lagrange
(1769) is used to find the the first m+1 partial quotients aa[0],...,aa[m] of x.
<BR>(See Knuth, Art of computer programming, volume 2, problem 13, 4.5.3.
<BR>Also S. Lang and H. Trotter,<I>Continued fractions for some algebraic
numbers</I> J. für Math. 255 (1972) 112-134; Addendum 267 (1974) ibid. 219-220
and page 261, <I>Number Theory with Applications</I>, by R. Kumanduri and C.
Romero.<BR>P. Shiu, <I>Computation of continued fractions without input
values</I>, Math. Comp. 64 (1995), no. 211, 1307-1317,<BR>and D.G. Cantor, P.H.
Galyean, H.G. Zimmer [<A
href="http://www.numbertheory.org/calc/krm_calc.html#cantor">Can</A>].
<P>(If the root is rational, Lagrange's algorithm still finds the partial
quotients and we exit at the appropriate point.<BR>We check that poly is
squarefree, has leading coefficient positive, does not vanish at x=0 or x=1, is
not linear and has exactly one positive real root t and that t > 1.
<HR>
<A name=[60]></A><TT>z=perfectpower(n)</TT> <BR>Here n > 1. z= x if n =
x<SUP>k</SUP>, for some x, k > 1, NULL otherwise. <BR>See E. Bach and J.
Sorenson, "Sieve algorithms for perfect power testing", Algorithmica 9 (1993)
313-328.
<HR>
<A name=leastqnr></A><TT>z=leastqnr(p)</TT> <BR>Returns n<SUB>p</SUB>, the least
quadratic non-residue (mod p), if n<SUB>p</SUB> < 65536, otherwise returns 0.
<HR>
<A name=sturm></A><TT>sturm(f(X))</TT> <BR>Prints rational open intervals that
are guaranteed to each contain only one real root of the polynomial f(X).
It is assumed that f(X) has no rational roots. The output is sent to the file
sturm.out and to the screen. <BR>See ([<A
href="http://www.numbertheory.org/calc/krm_calc.html#akritas">Akr]</A>,page
341.)
<HR width="100%">
<A name=rootexp></A><TT>rootexp(f(X), m)</TT> <BR>Finds the first m partial
quotients of the continued fraction expansion of all real roots of a squarefree
polynomial f(X) with no rational roots, using Lagrange's method and a variation
presented in D.G. Cantor, P.H. Galyean, H.G. Zimmer [<A
href="http://www.numbertheory.org/calc/krm_calc.html#cantor">Can</A>],
especially pp. 785-787. The output is sent to a file rootexp.out and to the
screen. Also see D. Rosen, J. Shallit [<A
href="http://www.numbertheory.org/calc/krm_calc.html#shallit">Rosen-Shallit</A>.]
Programmed by Sean Seefried in January 2000.
<HR width="100%">
<A name=content></A><TT>content(f(X))</TT> <BR>Returns the content of a
polynomial f(X) (the gcd of the coefficients of f(X) x sign of the leading
coefficient of f(X)). eg. <BR>> content(-3X^2+6) <BR> -3
<HR width="100%">
<A name=primitive></A><TT>primitive(f(X))</TT><BR>Returns the primitive part
pp(f(X)) of a polynomial f(X), where f(X)=content(f(X))*pp(f(X)).
eg.<BR>>primitive(-3X^2+6)
<BR> X^2-2<BR>>content(-3X^2+6)<BR> -3<BR><BR>
<HR width="100%">
<!--<a NAME="log"></a><tt>log(a,b,d,u,v,e)</tt><br> This performs a discrete variant of Shank's log<sub>b</sub>a algorithm.Here d>1, 1 ≤ u < v are integers. The larger is v-u, the better chance of correctness of output. eg. v=2u is fine, but slow if u is say 500. v=u+10 isadequate. We do not guarantee the correctness of the output.<br>Roughly r partial quotients are outputted if d=10. If e=1, the convergents and decimal expansion of log<sub>b</sub>a are printed, the latter truncated correct to as many decimal places as possible: the r-1th convergent is compared with the rth convergent and the decimal expansions are truncated from where they differ. e=0 prints only the partial quotients, Output is sent to log.out. (See Algorithm 3 of [<a href="#[mat_log]">Mat_log</a>] <hr WIDTH="100%"><a NAME="log1"></a><tt>log1(a,b,d,r,e)</tt><br> This performs a discrete variant of Shank's log<sub>b</sub>a algorithm.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -