Class to represent a (possible) prime number. The isProbablePrime method can be invoked to test if this is probably prime (to a very high certainty). The validate method can be invoked to test if it is definitely prime (but it's expensive!)
NOTE: just because we have an instance of Prime does not mean that it is a prime number.
NOTE: Prime is no longer an AnyVal because we want to have lazy val validated.
Value parameters
- n
-
the value of the (possible) prime number (should be greater than zero, although this is not checked)
Attributes
- Companion
- object
- Graph
-
- Supertypes
-
trait Serializabletrait Producttrait Equalsclass Objecttrait Matchableclass AnyShow all
Members list
Value members
Concrete methods
Method to apply the Lucas test of primality.
Method to apply the Lucas test of primality.
Value parameters
- a
-
an arbitrary BigInt such that 0 < a < c.
- c
-
a composite number (typically one less than this prime).
- qs
-
the prime factors of c.
Attributes
- Returns
-
fermat(a) && doLucas(c, qs)(a)
This yields the value of a.pow(n-1) mod n.
This yields the value of a.pow(n-1) mod n.
Value parameters
- a
-
a BigInt which is not divisible by n.
Attributes
- Returns
-
a BigInt which, if this is prime, should be 1 for all 0 < a < n.
Method to determine if this Prime is coPrime to n. Recall that this class doesn't only have true prime members.
Method to determine if this Prime is coPrime to n. Recall that this class doesn't only have true prime members.
XXX Adapted from Scala 99: http://aperiodic.net/phil/scala/s-99/
Value parameters
- x
-
a BigInt.
Attributes
- Returns
-
true or false.
Method to yield base raised to the power exponent modulo n (i.e., this prime number).
Method to yield base raised to the power exponent modulo n (i.e., this prime number).
Value parameters
- base
-
a BigInt representing the base number.
- exponent
-
a BigInt representing the power to which a will be raised.
Attributes
- Returns
-
the value of base.pow(exponent) mod n.
Determine the multiplicative inverse of a, modulo n.
Determine the multiplicative inverse of a, modulo n.
NOTE: when this is a prime number, the multiplicativeInverse is modPow(a, n - 2); for non-prime moduli, we use the modInverse method on BigInt.
Value parameters
- a
-
the value whose multiplicative inverse we require.
Attributes
- Returns
-
a number z such that z a is congruent to 1 modulo n.
Get the remainder from the division x/n.
Get the remainder from the division x/n.
Value parameters
- x
-
a BigInt.
Attributes
- Returns
-
x % n
Method to test whether a BigInt is a primitive root of this Prime.
Method to test whether a BigInt is a primitive root of this Prime.
Value parameters
- a
-
a BigInt: the candidate primitive root.
Attributes
- Returns
-
true if a is a primitive root of this.
Optionally get the value of this prime as an Int.
Optionally get the value of this prime as an Int.
Attributes
- Returns
-
Some(n) if it fits as an Int, otherwise None.
Method to evaluate Euler's Totient function for this Prime raised to power r.
Method to evaluate Euler's Totient function for this Prime raised to power r.
Value parameters
- r
-
the exponent (power) by which the prime is raised.
Attributes
- Returns
-
a BigInt, which represents the number of elements less than n which are relatively prime to n.
Inherited methods
An iterator over the names of all the elements of this product.
An iterator over the names of all the elements of this product.
Attributes
- Inherited from:
- Product
An iterator over all the elements of this product.
An iterator over all the elements of this product.
Attributes
- Returns
-
in the default implementation, an
Iterator[Any] - Inherited from:
- Product
Concrete fields
Method to apply the Lucas test of primality.
Method to apply the Lucas test of primality.
TODO determine why this is so slow compared with Miller-Rabin.
Attributes
- Returns
-
true if for any random value a such that 0 < a < n - 1, Lucas(n-1, factors)(a) is true where factors are the prime factors of n - 1.
Get the length of this prime in bits.
Get the length of this prime in bits.
Attributes
- Returns
-
the length in bits.
Method to determine if this is indeed a probably prime.
Method to determine if this is indeed a probably prime.
NOTE: ideally, we should be able to substitute Lucas here.
Attributes
- Returns
-
the result of Prime.isProbablePrime(n).
Get the next probable prime number after this one.
Get the next probable prime number after this one.
Equivalent to Prime(n.bigInteger.nextProbablePrime())
Attributes
- Returns
-
a probable prime which is greater than this.
NOTE: this has been known to fail for 23
NOTE: this has been known to fail for 23
NOTE: This will yield only one of the primitive roots, the one where k = 1.
https://homepages.math.uic.edu/~leon/mcs425-s08/handouts/PrimitiveElements.pdf
Attributes
Method to get the reciprocal period for decimal expansion for this Prime. NOTE as of now, this is a simple lookup. If None is returned, then either this is not actually prime or it is not in the first hundred primes or in the list of reciprocal primes.
Method to get the reciprocal period for decimal expansion for this Prime. NOTE as of now, this is a simple lookup. If None is returned, then either this is not actually prime or it is not in the first hundred primes or in the list of reciprocal primes.
Attributes
Get the value of this prime.
Get the value of this prime.
Attributes
- Returns
-
n.
Method to render this Prime number as a String with a delimiter every third place.
Method to render this Prime number as a String with a delimiter every third place.
CONSIDER get the delimiter from the Java i18n features.
Attributes
- Returns
-
a String representing a Prime number.
True if this is a valid prime number, As this is a lazy val, it will only be evaluated at most once and, often, not at all.
True if this is a valid prime number, As this is a lazy val, it will only be evaluated at most once and, often, not at all.