Companion object to Prime. Represents a collection of mathematical utility methods and properties related to prime numbers.
Fields:
- BigOne: Represents a constant BigInt value of 1. May be used in various calculations involving primes.
- reciprocalPeriods: Stores data related to the reciprocal periods of numbers.
- carmichaelFile: Used for maintaining or accessing data related to Carmichael numbers.
- optionalPrime: Represents an optional instance of a Prime, used where a Prime may or may not exist.
Methods:
- coprime: Determines if two BigInt values are coprime.
- lcm: Computes the least common multiple of two BigInt values.
- totient: Computes Euler's Totient function (phi) for a given BigInt or prime power.
- reducedTotient: Computes the reduced (or Carmichael) Totient function for a given BigInt or prime power.
- primeCountingFunction: Counts the number of prime numbers less than a given BigInt.
- primeCountingFunctionExact: Precisely counts the number of primes less than a given BigInt.
- multiplicativeInverse: Computes the multiplicative inverse of a BigInt modulus n.
- primeFactors: Returns a sequence of prime factors (with repetition) of a given BigInt.
- primeFactorMultiplicity: Returns a Map with prime factors and their corresponding multiplicities.
- formatWithCommas: Formats a BigInt value with a specified delimiter string.
- apply: Constructs a new Prime instance if the value is positive. Throws an exception if the value is not positive.
- create: Creates an optional Prime instance from a BigInt or String.
- createMersennePrime: Creates an optional Mersenne Prime based on the ith prime exponent.
- mersenneNumber: Computes a Mersenne number for a given exponent or prime.
- hasSmallFactor: Checks if a number has any of the smaller prime factors. Assumes the number is odd.
- isProbableOddPrime: Tests if an odd BigInt is a probable prime using the Miller-Rabin test.
- isSmallPrime: Tests if a value is one of the first one hundred primes.
- isProbablePrime: Tests if a given BigInt is a probable prime using the Miller-Rabin test.
- isCarmichaelNumber: Determines if a BigInt is a Carmichael number.
- carmichaelTheoremApplies: A private method related to the application of Carmichael's theorem.
- fill: Creates a list containing multiple copies of a given value.
- getRandomValues: Generates random BigInt values based on the input BigInt.
Attributes
Members list
Type members
Inherited and Abstract types
The names of the product elements.
The names of the product elements.
Attributes
- Inherited from:
- Mirror
The name of the type.
The name of the type.
Attributes
- Inherited from:
- Mirror
Value members
Concrete methods
Method to construct a new Prime, provided that it is positive.
Method to construct a new Prime, provided that it is positive.
NOTE there is no check at all as to whether the result is actually a prime number.
Value parameters
- p
-
a positive BigInt.
Attributes
- Returns
-
a Prime whose value may or may not be a Prime number.
- Note
-
Throws PrimeException if n is not positive.
Method to determine if two BigInts are coprime, i.e. relatively prime.
Method to determine if two BigInts are coprime, i.e. relatively prime.
Value parameters
- p
-
another BigInt.
- x
-
a BigInt.
Attributes
- Returns
-
true if the gcd of x and p is 1.
Method to create a (probable) Prime from a String.
Method to create a (probable) Prime from a String.
Value parameters
- s
-
the String.
Attributes
- Returns
-
an optional Prime whose value is the String and whose value is probably a prime.
Create an (optional) instance of Prime such that n is a probable prime.
Create an (optional) instance of Prime such that n is a probable prime.
Value parameters
- p
-
a BigInt.
Attributes
- Returns
-
an Option[Prime]
Create an (optional) Mersenne Prime of form (2 to the power of the ith prime) - 1. Returns Some only if the candidate passes the Lucas-Lehmer primality test.
Create an (optional) Mersenne Prime of form (2 to the power of the ith prime) - 1. Returns Some only if the candidate passes the Lucas-Lehmer primality test.
Value parameters
- i
-
the index of the exponent of two.
Attributes
- Returns
-
an Option[Prime]
Format a BigInt with a delimiter.
Format a BigInt with a delimiter.
NOTE that I tried to use new java.text.DecimalFormat("#,###") but it didn't work correctly!
Value parameters
- x
-
a BigInt.
Attributes
- Returns
-
a String
Method to detect if x has one of the smaller factors. NOTE: we don't test for odd parity because we assume that x is odd.
Method to detect if x has one of the smaller factors. NOTE: we don't test for odd parity because we assume that x is odd.
Value parameters
- x
-
an odd BigInt
Attributes
- Returns
-
true if 3 or 5 or 7 divides x.
Test n to determine if it is a Carmichael Number.
Test n to determine if it is a Carmichael Number.
Value parameters
- n
-
a BigInt to be tested.
Attributes
- Returns
-
true if n is a Carmichael Number.
Checks whether the given number is even.
Checks whether the given number is even.
Value parameters
- x
-
the number to be checked
Attributes
- Returns
-
true if the number is even, false otherwise
Method to determine if n is a probable prime. We use the MillerRabin test on n. NOTE: we assume that n is odd.
Method to determine if n is a probable prime. We use the MillerRabin test on n. NOTE: we assume that n is odd.
More or less the equivalent of n.isProbablePrime(100). The performance appears to be similar.
NOTE: you may be tempted to replace carmichael.contains(p) by isCarmichaelNumber(p) but tread very carefully if you do that!
Value parameters
- p
-
an odd BigInt.
Attributes
- Returns
-
true if n is probably prime.
Method to determine if n is a probable prime. We use the MillerRabin test on n.
Method to determine if n is a probable prime. We use the MillerRabin test on n.
Value parameters
- p
-
a BigInt.
Attributes
- Returns
-
true if n is probably prime.
Method to determine if p is one of the first one hundred primes.
Method to determine if p is one of the first one hundred primes.
Value parameters
- p
-
a candidate BigInt
Attributes
- Returns
-
true if p is in hundredPrimes.
Method to test whether a Mersenne number M_p = 2^p - 1 is prime using the Lucas-Lehmer primality test.
Method to test whether a Mersenne number M_p = 2^p - 1 is prime using the Lucas-Lehmer primality test.
Value parameters
- p
-
the exponent; M_p is prime iff p is prime, so callers should ensure this.
Attributes
- Returns
-
true if M_p is a Mersenne prime.
Performs the Lucas-Lehmer primality test for Mersenne numbers.
Performs the Lucas-Lehmer primality test for Mersenne numbers.
Value parameters
- p
-
A Prime number object that contains the exponent for the Mersenne number.
Attributes
- Returns
-
Boolean value indicating whether the Mersenne number of the form 2^p - 1 is prime.
Method to yield a Mersenne number: (2 to the power of the ith prime) - 1.
Method to yield a Mersenne number: (2 to the power of the ith prime) - 1.
Value parameters
- i
-
the index of the exponent of two.
Attributes
- Returns
-
a BigInt.
Method to yield a Mersenne number: (2 to the power of n) - 1.
Method to yield a Mersenne number: (2 to the power of n) - 1.
Value parameters
- p
-
the prime number to generate the Mersenne prime. NOTE that no explicit check is made to ensure that n is prime.
Attributes
- Returns
-
a BigInt.
Get the multiplicativeInverse for a BigInt (a) modulus n.
Get the multiplicativeInverse for a BigInt (a) modulus n.
NOTE: if is assumed that n is not a prime number. Assuming that n is coprime to a, then we return a.modPow(totient(n)-1), otherwise a.modInverse(n).
Value parameters
- a
-
the number for which we need the multiplicative inverse.
- n
-
the modulus.
Attributes
- Returns
-
a number x such that ax is congruent to 1, mod n.
Method to determine how many prime numbers there are which are less than x.
Method to determine how many prime numbers there are which are less than x.
Value parameters
- x
-
a BigInt.
Attributes
- Returns
-
the number of primes that are less than x.
Method to determine how many prime numbers there are which are less than x.
Method to determine how many prime numbers there are which are less than x.
Value parameters
- x
-
a BigInt.
Attributes
- Returns
-
the number of primes that are less than x.
Computes the prime factorization of the given number x and returns a map of prime factors with their respective multiplicities (exponents). The computation can optionally be limited to a maximum number of primes through maybeMax.
Computes the prime factorization of the given number x and returns a map of prime factors with their respective multiplicities (exponents). The computation can optionally be limited to a maximum number of primes through maybeMax.
XXX Adapted from Scala 99: http://aperiodic.net/phil/scala/s-99/
Value parameters
- maybeMax
-
an optional parameter specifying the maximum number of primes to consider during factorization. If not provided, all primes are considered.
- x
-
the number to factorize.
Attributes
- Returns
-
a map where each key is a prime factor of
xand the corresponding value is its exponent in the prime factorization.
Method to yield the prime factors (with repeated elements). NOTE that if x is prime, then the list returned consists of x (not sure why but that's how it's implemented in Scala 99).
Method to yield the prime factors (with repeated elements). NOTE that if x is prime, then the list returned consists of x (not sure why but that's how it's implemented in Scala 99).
XXX Adapted from Scala 99: http://aperiodic.net/phil/scala/s-99/
Value parameters
- maybeMax
-
an optional maximum number of prime factors to consider. Defaults to None.
- x
-
a BigInt whose prime factors are to be determined.
Attributes
- Returns
-
a sequence of Prime objects representing the prime factors of the input BigInt.
Method to calculate the Carmichael (or "reduced") totient for x.
Method to calculate the Carmichael (or "reduced") totient for x.
Value parameters
- x
-
a BigInt for which we require Carmichael's totient function.
Attributes
- Returns
-
a BigInt, which represents the Carmichael totient function.
Method to yield the value of the Euler's Totient function (phi) for this Prime.
Method to yield the value of the Euler's Totient function (phi) for this Prime.
XXX Adapted from Scala 99: http://aperiodic.net/phil/scala/s-99/
Value parameters
- x
-
a BigInt for which we require Euler's totient function.
Attributes
- Returns
-
a BigInt, which represents the number of elements less than n which are relatively prime to x.
Euler's totient function for a prime power.
Euler's totient function for a prime power.
Value parameters
- factor
-
a PrimeFactor (prime base and exponent).
Attributes
- Returns
-
Euler's totient function for this Prime power.