Crypto.Number.Prime

Generate a prime number of the required bitsize (i.e. in the range [2^(b-1)+2^(b-2), 2^b)).

May throw a CryptoError_PrimeSizeInvalid if the requested size is less than 5 bits, as the smallest prime meeting these conditions is 29. This function requires that the two highest bits are set, so that when multiplied with another prime to create a key, it is guaranteed to be of the proper size.

Generate a prime number of the form 2p+1 where p is also prime. it is also knowed as a Sophie Germaine prime or safe prime.

The number of safe prime is significantly smaller to the number of prime, as such it shouldn't be used if this number is supposed to be kept safe.

May throw a CryptoError_PrimeSizeInvalid if the requested size is less than 6 bits, as the smallest safe prime with the two highest bits set is 59.

Returns if the number is probably prime.

The small primes are tested for divisibility first, and then the Miller-Rabin algorithm with an accuracy of 30 rounds.

A Fermat test of fifty consecutive bases used to run between the two. It ruled out nothing Miller-Rabin does not: a strong probable prime to a base is a Fermat probable prime to that base, and the converse is what Carmichael numbers are. What it cost was fifty modular exponentiations on every number that turned out to be prime -- 2167 of the 3480 microseconds spent on a 512-bit prime, and about two thirds of the time to generate one.

Find a prime from a starting point with no specific property.

Find a prime from a starting point where the property hold.

Miller Rabin algorithm return if the number is probably prime or composite. the tries parameter is the number of recursion, that determines the accuracy of the test.

The witnesses are drawn from a generator derived from n itself and from a secret drawn once per process: testing the same number twice gives the same answer, testing two numbers draws independent witnesses for each, and an attacker choosing the number cannot tell which witnesses it will face.

Test naively is integer is prime. while naive, we skip even number and stop iteration at i > sqrt(n)

Probabilitic Test using Fermat primility test. Beware of Carmichael numbers that are Fermat liars, i.e. this test is useless for them. always combines with some other test.

Test is two integer are coprime to each other