GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
ntheory(3) User Contributed Perl Documentation ntheory(3)
 

ntheory - Number theory utilities

See Math::Prime::Util for complete documentation.

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

  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_mersenne_prime(p)                is 2^p-1 prime or composite
  is_aks_prime(n)                     AKS deterministic test (slow)
  is_ramanujan_prime(n)               is n a Ramanujan prime

  is_pseudoprime(n,bases)                  Fermat probable prime test
  is_euler_pseudoprime(n,bases)            Euler test to bases
  is_euler_plumb_pseudoprime(n)            Euler Criterion test
  is_strong_pseudoprime(n,bases)           Miller-Rabin test 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_frobenius_underwood_pseudoprime(n)    combined PSP and Lucas
  is_frobenius_khashin_pseudoprime(n)      Khashin's 2013 Frobenius test
  is_perrin_pseudoprime(n [,r])            Perrin test
  is_catalan_pseudoprime(n)                Catalan test
  is_bpsw_prime(n)                         combined SPSP-2 and ES Lucas
  miller_rabin_random(n, ntests)           perform random-base MR tests

  primes([start,] end)                array ref of primes
  twin_primes([start,] end)           array ref of twin primes
  semi_primes([start,] end)           array ref of semiprimes
  ramanujan_primes([start,] end)      array ref of Ramanujan primes
  sieve_prime_cluster(start, end, @C) list of prime k-tuples
  sieve_range(n, width, depth)        sieve out small factors to depth
  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
  semiprime_count(n)                  count of semiprimes <= n
  semiprime_count(start, end)         count of semiprimes in range
  semiprime_count_approx(n)           fast approximate count of semiprimes
  nth_semiprime(n)                    the nth semiprime
  nth_semiprime_approx(n)             fast approximate nth semiprime
  ramanujan_prime_count(n)            count of Ramanujan primes <= n
  ramanujan_prime_count(start, end)   count of Ramanujan primes in range
  ramanujan_prime_count_lower(n)      fast lower bound for Ramanujan count
  ramanujan_prime_count_upper(n)      fast upper bound for Ramanujan count
  ramanujan_prime_count_approx(n)     fast approximate Ramanujan count
  nth_ramanujan_prime(n)              the nth Ramanujan prime (Rn)
  nth_ramanujan_prime_lower(n)        fast lower bound for Rn
  nth_ramanujan_prime_upper(n)        fast upper bound for Rn
  nth_ramanujan_prime_approx(n)       fast approximate Rn
  legendre_phi(n,a)                   # below n not div by first a primes
  inverse_li(n)                       integer inverse logarithmic integral
  prime_precalc(n)                    precalculate primes to n
  sum_primes([start,] end)            return summation of primes in range
  print_primes(start,end[,fd])        print primes to stdout or fd

  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

  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
  forsemiprimes {...} [start,] end    loop over semiprimes in range
  forfactored {...} [start,] end      loop with factors
  forsquarefree {...} [start,] end    loop with factors of square-free n
  fordivisors { ... } n               loop over the divisors of n
  forpart { ... } n [,{...}]          loop over integer partitions
  forcomp { ... } n [,{...}]          loop over integer compositions
  forcomb { ... } n, k                loop over combinations
  forperm { ... } n                   loop over permutations
  formultiperm { ... } \@n            loop over multiset permutations
  forderange { ... } n                loop over derangements
  forsetproduct { ... } \@a[,...]     loop over Cartesian product of lists
  prime_iterator                      returns a simple prime iterator
  prime_iterator_object               returns a prime iterator object
  lastfor                             stop iteration of for.... loop

  irand                               random 32-bit integer
  irand64                             random 64-bit integer
  drand([limit])                      random NV in [0,1) or [0,limit)
  random_bytes(n)                     string with n random bytes
  entropy_bytes(n)                    string with n entropy-source bytes
  urandomb(n)                         random integer less than 2^n
  urandomm(n)                         random integer less than n
  csrand(data)                        seed the CSPRNG with binary data
  srand([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_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's 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
  random_unrestricted_semiprime(n)    random n-bit semiprime
  random_semiprime(n)                 as above with equal size factors

  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
  vecextract(\@list, mask)            select from list based on mask
  vecreduce { ... } @list             reduce / left fold applied to list
  vecall { ... } @list                return true if all are true
  vecany { ... } @list                return true if any are true
  vecnone { ... } @list               return true if none are true
  vecnotall { ... } @list             return true if not all are true
  vecfirst { ... } @list              return first value that evals true
  vecfirstidx { ... } @list           return first index that evals true

  todigits(n[,base[,len]])            convert n to digit array in base
  todigitstring(n[,base[,len]])       convert n to string in base
  fromdigits(\@d,[,base])             convert base digit vector to number
  fromdigits(str,[,base])             convert base digit string to number
  sumdigits(n)                        sum of digits, with optional base
  is_square(n)                        return 1 if n is a perfect square
  is_power(n)                         return k if n = c^k for integer c
  is_power(n,k)                       return 1 if n = c^k for integer c, k
  is_power(n,k,\$root)                as above but also set $root to c.
  is_prime_power(n)                   return k if n = p^k for prime p
  is_prime_power(n,\$p)               as above but also set $p to p
  is_square_free(n)                   return true if no repeated factors
  is_carmichael(n)                    is n a Carmichael number
  is_quasi_carmichael(n)              is n a quasi-Carmichael number
  is_primitive_root(r,n)              is r a primitive root mod n
  is_pillai(n)                        v where  v! % n == n-1  and  n % v != 1
  is_semiprime(n)                     does n have exactly 2 prime factors
  is_polygonal(n,k)                   is n a k-polygonal number
  is_polygonal(n,k,\$root)            as above but also set $root
  is_fundamental(d)                   is d a fundamental discriminant
  is_totient(n)                       is n = euler_phi(x) for some x
  sqrtint(n)                          integer square root
  rootint(n,k)                        integer k-th root
  rootint(n,k,\$rk)                   as above but also set $rk to r^k
  logint(n,b)                         integer logarithm
  logint(n,b,\$be)                    as above but also set $be to b^e.
  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!
  factorialmod(n,m)                   factorial mod m
  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
  addmod(a,b,n)                       a + b mod n
  mulmod(a,b,n)                       a * b mod n
  divmod(a,b,n)                       a / b mod n
  powmod(a,b,n)                       a ^ b mod n
  invmod(a,n)                         inverse of a modulo n
  sqrtmod(a,n)                        modular square root
  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
  inverse_totient(n)                  image of Euler totient
  jordan_totient(n,k)                 Jordan's totient
  carmichael_lambda(n)                Carmichael's Lambda function
  ramanujan_sum(k,n)                  Ramanujan's sum
  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
  hclassno(n)                         Hurwitz class number H(n) * 12
  ramanujan_tau(n)                    Ramanujan's Tau function
  consecutive_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 n
  bernfrac(n)                         Bernoulli number as (num,den)
  bernreal(n)                         Bernoulli number as BigFloat
  harmfrac(n)                         Harmonic number as (num,den)
  harmreal(n)                         Harmonic number as BigFloat
  stirling(n,m,[type])                Stirling numbers of 1st or 2nd type
  numtoperm(n,k)                      kth lexico permutation of n elems
  permtonum([a,b,...])                permutation number of given perm
  randperm(n,[k])                     random permutation of n elems
  shuffle(...)                        random permutation of an array

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

  prime_get_config                    gets hash ref of current settings
  prime_set_config(%hash)             sets parameters
  prime_memfree                       frees any cached memory

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.
2018-11-15 perl v5.28.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.