NAME

ntheory - Number theory utilities

SEE

SeeMath::Prime::Util for complete documentation.

QUICK REFERENCE

Tags: :all to import almost all functions :rand to import rand, srand, irand, irand64

PRIMALITY

is_prob_prime(n)                    primality test (BPSW)is_prime(n)                         primality test (BPSW + extra)is_provable_prime(n)                primality test with proofis_provable_prime_with_cert(n)      primality test: (isprime,cert)prime_certificate(n)                as above with just certificateverify_prime(cert)                  verify a primality certificateis_mersenne_prime(p)                is 2^p-1 prime or compositeis_aks_prime(n)                     AKS deterministic test (slow)is_ramanujan_prime(n)               is n a Ramanujan prime

PROBABLE PRIME TESTS

is_pseudoprime(n,bases)                  Fermat probable prime testis_euler_pseudoprime(n,bases)            Euler test to basesis_euler_plumb_pseudoprime(n)            Euler Criterion testis_strong_pseudoprime(n,bases)           Miller-Rabin test to basesis_lucas_pseudoprime(n)                  Lucas testis_strong_lucas_pseudoprime(n)           strong Lucas testis_almost_extra_strong_lucas_pseudoprime(n, [incr])   AES Lucas testis_extra_strong_lucas_pseudoprime(n)     extra strong Lucas testis_frobenius_pseudoprime(n, [a,b])       Frobenius quadratic testis_frobenius_underwood_pseudoprime(n)    combined PSP and Lucasis_frobenius_khashin_pseudoprime(n)      Khashin's 2013 Frobenius testis_perrin_pseudoprime(n [,r])            Perrin testis_catalan_pseudoprime(n)                Catalan testis_bpsw_prime(n)                         combined SPSP-2 and ES Lucasmiller_rabin_random(n, ntests)           perform random-base MR tests

PRIMES

primes([start,] end)                array ref of primestwin_primes([start,] end)           array ref of twin primessemi_primes([start,] end)           array ref of semiprimesramanujan_primes([start,] end)      array ref of Ramanujan primessieve_prime_cluster(start, end, @C) list of prime k-tuplessieve_range(n, width, depth)        sieve out small factors to depthnext_prime(n)                       next prime > nprev_prime(n)                       previous prime < nprime_count(n)                      count of primes <= nprime_count(start, end)             count of primes in rangeprime_count_lower(n)                fast lower bound for prime countprime_count_upper(n)                fast upper bound for prime countprime_count_approx(n)               fast approximate count of primesnth_prime(n)                        the nth prime (n=1 returns 2)nth_prime_lower(n)                  fast lower bound for nth primenth_prime_upper(n)                  fast upper bound for nth primenth_prime_approx(n)                 fast approximate nth primetwin_prime_count(n)                 count of twin primes <= ntwin_prime_count(start, end)        count of twin primes in rangetwin_prime_count_approx(n)          fast approx count of twin primesnth_twin_prime(n)                   the nth twin prime (n=1 returns 3)nth_twin_prime_approx(n)            fast approximate nth twin primesemiprime_count(n)                  count of semiprimes <= nsemiprime_count(start, end)         count of semiprimes in rangesemiprime_count_approx(n)           fast approximate count of semiprimesnth_semiprime(n)                    the nth semiprimenth_semiprime_approx(n)             fast approximate nth semiprimeramanujan_prime_count(n)            count of Ramanujan primes <= nramanujan_prime_count(start, end)   count of Ramanujan primes in rangeramanujan_prime_count_lower(n)      fast lower bound for Ramanujan countramanujan_prime_count_upper(n)      fast upper bound for Ramanujan countramanujan_prime_count_approx(n)     fast approximate Ramanujan countnth_ramanujan_prime(n)              the nth Ramanujan prime (Rn)nth_ramanujan_prime_lower(n)        fast lower bound for Rnnth_ramanujan_prime_upper(n)        fast upper bound for Rnnth_ramanujan_prime_approx(n)       fast approximate Rnlegendre_phi(n,a)                   # below n not div by first a primesinverse_li(n)                       integer inverse logarithmic integralprime_precalc(n)                    precalculate primes to nsum_primes([start,] end)            return summation of primes in rangeprint_primes(start,end[,fd])        print primes to stdout or fd

FACTORING

factor(n)                           array of prime factors of nfactor_exp(n)                       array of [p,k] factors p^kdivisors(n)                         array of divisors of ndivisor_sum(n)                      sum of divisorsdivisor_sum(n,k)                    sum of k-th power of divisorsdivisor_sum(n,sub{...})             sum of code run for each divisorznlog(a, g, p)                      solve k in a = g^k mod p

ITERATORS

forprimes { ... } [start,] end      loop over primes in rangeforcomposites { ... } [start,] end  loop over composites in rangeforoddcomposites {...} [start,] end loop over odd composites in rangeforsemiprimes {...} [start,] end    loop over semiprimes in rangeforfactored {...} [start,] end      loop with factorsforsquarefree {...} [start,] end    loop with factors of square-free nfordivisors { ... } n               loop over the divisors of nforpart { ... } n [,{...}]          loop over integer partitionsforcomp { ... } n [,{...}]          loop over integer compositionsforcomb { ... } n, k                loop over combinationsforperm { ... } n                   loop over permutationsformultiperm { ... } \@n            loop over multiset permutationsforderange { ... } n                loop over derangementsforsetproduct { ... } \@a[,...]     loop over Cartesian product of listsprime_iterator                      returns a simple prime iteratorprime_iterator_object               returns a prime iterator objectlastfor                             stop iteration of for.... loop

RANDOM NUMBERS

irand                               random 32-bit integerirand64                             random 64-bit integerdrand([limit])                      random NV in [0,1) or [0,limit)random_bytes(n)                     string with n random bytesentropy_bytes(n)                    string with n entropy-source bytesurandomb(n)                         random integer less than 2^nurandomm(n)                         random integer less than ncsrand(data)                        seed the CSPRNG with binary datasrand([seed])                       simple seed (exported with :rand)rand([limit])                       alias for drand (exported with :rand)random_factored_integer(n)          random [1..n] and array ref of factors

RANDOM PRIMES

random_prime([start,] end)          random prime in a rangerandom_ndigit_prime(n)              random prime with n digitsrandom_nbit_prime(n)                random prime with n bitsrandom_strong_prime(n)              random strong prime with n bitsrandom_proven_prime(n)              random n-bit prime with proofrandom_proven_prime_with_cert(n)    as above and include certificaterandom_maurer_prime(n)              random n-bit prime w/ Maurer's alg.random_maurer_prime_with_cert(n)    as above and include certificaterandom_shawe_taylor_prime(n)        random n-bit prime with S-T alg.random_shawe_taylor_prime_with_cert(n) as above including certificaterandom_unrestricted_semiprime(n)    random n-bit semiprimerandom_semiprime(n)                 as above with equal size factors

LISTS

vecsum(@list)                       integer sum of listvecprod(@list)                      integer product of listvecmin(@list)                       minimum of list of integersvecmax(@list)                       maximum of list of integersvecextract(\@list, mask)            select from list based on maskvecreduce { ... } @list             reduce / left fold applied to listvecall { ... } @list                return true if all are truevecany { ... } @list                return true if any are truevecnone { ... } @list               return true if none are truevecnotall { ... } @list             return true if not all are truevecfirst { ... } @list              return first value that evals truevecfirstidx { ... } @list           return first index that evals true

MATH

todigits(n[,base[,len]])            convert n to digit array in basetodigitstring(n[,base[,len]])       convert n to string in basefromdigits(\@d,[,base])             convert base digit vector to numberfromdigits(str,[,base])             convert base digit string to numbersumdigits(n)                        sum of digits, with optional baseis_square(n)                        return 1 if n is a perfect squareis_power(n)                         return k if n = c^k for integer cis_power(n,k)                       return 1 if n = c^k for integer c, kis_power(n,k,\$root)                as above but also set $root to c.is_prime_power(n)                   return k if n = p^k for prime pis_prime_power(n,\$p)               as above but also set $p to pis_square_free(n)                   return true if no repeated factorsis_carmichael(n)                    is n a Carmichael numberis_quasi_carmichael(n)              is n a quasi-Carmichael numberis_primitive_root(r,n)              is r a primitive root mod nis_pillai(n)                        v where  v! % n == n-1  and  n % v != 1is_semiprime(n)                     does n have exactly 2 prime factorsis_polygonal(n,k)                   is n a k-polygonal numberis_polygonal(n,k,\$root)            as above but also set $rootis_fundamental(d)                   is d a fundamental discriminantis_totient(n)                       is n = euler_phi(x) for some xsqrtint(n)                          integer square rootrootint(n,k)                        integer k-th rootrootint(n,k,\$rk)                   as above but also set $rk to r^klogint(n,b)                         integer logarithmlogint(n,b,\$be)                    as above but also set $be to b^e.gcd(@list)                          greatest common divisorlcm(@list)                          least common multiplegcdext(x,y)                         return (u,v,d) where u*x+v*y=dchinese([a,mod1],[b,mod2],...)      Chinese Remainder Theoremprimorial(n)                        product of primes below npn_primorial(n)                     product of first n primesfactorial(n)                        product of first n integers: n!factorialmod(n,m)                   factorial mod mbinomial(n,k)                       binomial coefficientpartitions(n)                       number of integer partitionsvaluation(n,k)                      number of times n is divisible by khammingweight(n)                    population count (# of binary 1s)kronecker(a,b)                      Kronecker (Jacobi) symboladdmod(a,b,n)                       a + b mod nmulmod(a,b,n)                       a * b mod ndivmod(a,b,n)                       a / b mod npowmod(a,b,n)                       a ^ b mod ninvmod(a,n)                         inverse of a modulo nsqrtmod(a,n)                        modular square rootmoebius(n)                          Moebius function of nmoebius(beg, end)                   array of Moebius in rangemertens(n)                          sum of Moebius for 1 to neuler_phi(n)                        Euler totient of neuler_phi(beg, end)                 Euler totient for a rangeinverse_totient(n)                  image of Euler totientjordan_totient(n,k)                 Jordan's totientcarmichael_lambda(n)                Carmichael's Lambda functionramanujan_sum(k,n)                  Ramanujan's sumexp_mangoldt                        exponential of Mangoldt functionliouville(n)                        Liouville functionznorder(a,n)                        multiplicative order of a mod nznprimroot(n)                       smallest primitive rootchebyshev_theta(n)                  first Chebyshev functionchebyshev_psi(n)                    second Chebyshev functionhclassno(n)                         Hurwitz class number H(n) * 12ramanujan_tau(n)                    Ramanujan's Tau functionconsecutive_integer_lcm(n)          lcm(1 .. n)lucasu(P, Q, k)                     U_k for Lucas(P,Q)lucasv(P, Q, k)                     V_k for Lucas(P,Q)lucas_sequence(n, P, Q, k)          (U_k,V_k,Q_k) for Lucas(P,Q) mod nbernfrac(n)                         Bernoulli number as (num,den)bernreal(n)                         Bernoulli number as BigFloatharmfrac(n)                         Harmonic number as (num,den)harmreal(n)                         Harmonic number as BigFloatstirling(n,m,[type])                Stirling numbers of 1st or 2nd typenumtoperm(n,k)                      kth lexico permutation of n elemspermtonum([a,b,...])                permutation number of given permrandperm(n,[k])                     random permutation of n elemsshuffle(...)                        random permutation of an array

NON-INTEGER MATH

ExponentialIntegral(x)              Ei(x)LogarithmicIntegral(x)              li(x)RiemannZeta(x)                      ζ(s)-1, real-valued Riemann ZetaRiemannR(x)                         Riemann's R functionLambertW(k)                         Lambert W: solve for W in k = W exp(W)Pi([n])                             The constant π (NV or n digits)

SUPPORT

prime_get_config                    gets hash ref of current settingsprime_set_config(%hash)             sets parametersprime_memfree                       frees any cached memory

COPYRIGHT

Copyright 2011-2018 by Dana Jacobsen <dana@acm.org>

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.