.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "ntheory 3pm" .TH ntheory 3pm "2014-10-21" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" ntheory \- Number theory utilities .SH "SEE" .IX Header "SEE" See Math::Prime::Util for complete documentation. .SH "QUICK REFERENCE" .IX Header "QUICK REFERENCE" .SS "\s-1PRIMALITY\s0" .IX Subsection "PRIMALITY" .Vb 7 \& is_prob_prime(n) primality test (BPSW) \& is_prime(n) primality test (BPSW + extra) \& is_provable_prime(n) primality test with proof \& is_provable_prime_with_cert(n) primality test: (isprime,cert) \& prime_certificate(n) as above with just certificate \& verify_prime(cert) verify a primality certificate \& is_aks_prime AKS deterministic test (slow) .Ve .SS "\s-1PROBABLE PRIME TESTS\s0" .IX Subsection "PROBABLE PRIME TESTS" .Vb 11 \& is_pseudoprime(n,bases) Fermat probable prime tests \& is_strong_pseudoprime(n,bases) Miller\-Rabin tests to bases \& is_lucas_pseudoprime(n) Lucas test \& is_strong_lucas_pseudoprime(n) strong Lucas test \& is_almost_extra_strong_lucas_pseudoprime(n, [incr]) AES Lucas test \& is_extra_strong_lucas_pseudoprime(n) extra strong Lucas test \& is_frobenius_pseudoprime(n, [a,b]) Frobenius quadratic test \& is_perrin_pseudoprime(n) Perrin test \& is_frobenius_underwood_pseudoprime(n) combined PSP and Lucas \& is_bpsw_prime(n) combined SPSP\-2 and ES Lucas \& miller_rabin_random(n, ntests) perform random\-base MR tests .Ve .SS "\s-1PRIMES\s0" .IX Subsection "PRIMES" .Vb 10 \& primes([start,] end) array ref of primes \& twin_primes([start,] end) array ref of twin primes \& next_prime(n) next prime > n \& prev_prime(n) previous prime < n \& prime_count(n) count of primes <= n \& prime_count(start, end) count of primes in range \& prime_count_lower(n) fast lower bound for prime count \& prime_count_upper(n) fast upper bound for prime count \& prime_count_approx(n) fast approximate count of primes \& nth_prime(n) the nth prime (n=1 returns 2) \& nth_prime_lower(n) fast lower bound for nth prime \& nth_prime_upper(n) fast upper bound for nth prime \& nth_prime_approx(n) fast approximate nth prime \& twin_prime_count(n) count of twin primes <= n \& twin_prime_count(start, end) count of twin primes in range \& twin_prime_count_approx(n) fast approx count of twin primes \& nth_twin_prime(n) the nth twin prime (n=1 returns 3) \& nth_twin_prime_approx(n) fast approximate nth twin prime \& legendre_phi(n,a) # below n not div by first a primes \& prime_precalc(n) precalculate primes to n .Ve .SS "\s-1FACTORING\s0" .IX Subsection "FACTORING" .Vb 7 \& factor(n) array of prime factors of n \& factor_exp(n) array of [p,k] factors p^k \& divisors(n) array of divisors of n \& divisor_sum(n) sum of divisors \& divisor_sum(n,k) sum of k\-th power of divisors \& divisor_sum(n,sub{...}) sum of code run for each divisor \& znlog(a, g, p) solve k in a = g^k mod p .Ve .SS "\s-1ITERATORS\s0" .IX Subsection "ITERATORS" .Vb 9 \& forprimes { ... } [start,] end loop over primes in range \& forcomposites { ... } [start,] end loop over composites in range \& foroddcomposites {...} [start,] end loop over odd composites in range \& fordivisors { ... } n loop over the divisors of n \& forpart { ... } n [,{...}] loop over integer partitions \& forcomb { ... } n, k loop over combinations \& forperm { ... } n loop over permutations \& prime_iterator returns a simple prime iterator \& prime_iterator_object returns a prime iterator object .Ve .SS "\s-1RANDOM PRIMES\s0" .IX Subsection "RANDOM PRIMES" .Vb 10 \& random_prime([start,] end) random prime in a range \& random_ndigit_prime(n) random prime with n digits \& random_nbit_prime(n) random prime with n bits \& random_strong_prime(n) random strong prime with n bits \& random_proven_prime(n) random n\-bit prime with proof \& random_proven_prime_with_cert(n) as above and include certificate \& random_maurer_prime(n) random n\-bit prime w/ Maurer\*(Aqs alg. \& random_maurer_prime_with_cert(n) as above and include certificate \& random_shawe_taylor_prime(n) random n\-bit prime with S\-T alg. \& random_shawe_taylor_prime_with_cert(n) as above including certificate .Ve .SS "\s-1MATH\s0" .IX Subsection "MATH" .Vb 10 \& vecsum(@list) integer sum of list \& vecprod(@list) integer product of list \& vecmin(@list) minimum of list of integers \& vecmax(@list) maximum of list of integers \& vecreduce { ... } @list reduce / left fold applied to list \& is_power(n) return k if n = p^k for integer p \& gcd(@list) greatest common divisor \& lcm(@list) least common multiple \& gcdext(x,y) return (u,v,d) where u*x+v*y=d \& chinese([a,mod1],[b,mod2],...) Chinese Remainder Theorem \& primorial(n) product of primes below n \& pn_primorial(n) product of first n primes \& factorial(n) product of first n integers: n! \& binomial(n,k) binomial coefficient \& partitions(n) number of integer partitions \& valuation(n,k) number of times n is divisible by k \& hammingweight(n) population count (# of binary 1s) \& kronecker(a,b) Kronecker (Jacobi) symbol \& invmod(a,n) inverse of a modulo n \& moebius(n) Moebius function of n \& moebius(beg, end) array of Moebius in range \& mertens(n) sum of Moebius for 1 to n \& euler_phi(n) Euler totient of n \& euler_phi(beg, end) Euler totient for a range \& jordan_totient(n,k) Jordan\*(Aqs totient \& carmichael_lambda(n) Carmichael\*(Aqs Lambda function \& exp_mangoldt exponential of Mangoldt function \& liouville(n) Liouville function \& znorder(a,n) multiplicative order of a mod n \& znprimroot(n) smallest primitive root \& chebyshev_theta(n) first Chebyshev function \& chebyshev_psi(n) second Chebyshev function \& consecutive_integer_lcm(n) lcm(1 .. n) \& lucas_sequence(n, P, Q, k) (U_k,V_k,Q_k) for Lucas(P,Q) mod n \& bernfrac(n) Bernoulli number as (num,den) \& bernreal(n) Bernoulli number as BigFloat \& stirling(n,m,[type]) Stirling numbers of 1st or 2nd type .Ve .SS "NON-INTEGER \s-1MATH\s0" .IX Subsection "NON-INTEGER MATH" .Vb 6 \& ExponentialIntegral(x) Ei(x) \& LogarithmicIntegral(x) li(x) \& RiemannZeta(x) X(s)\-1, real\-valued Riemann Zeta \& RiemannR(x) Riemann\*(Aqs R function \& LambertW(k) Lambert W: solve for W in k = W exp(W) \& Pi([n]) The constant X (NV or n digits) .Ve .SS "\s-1SUPPORT\s0" .IX Subsection "SUPPORT" .Vb 3 \& prime_get_config gets hash ref of current settings \& prime_set_config(%hash) sets parameters \& prime_memfree frees any cached memory .Ve .SH "COPYRIGHT" .IX Header "COPYRIGHT" Copyright 2011\-2014 by Dana Jacobsen .PP This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.