Primality test natural number -- one of the basic operations for creating cryptographic keys. Since it is impossible to synthesize a prime number, finding prime numbers is based on looking at numbers and checking them for primality.

Test

Some prime numbers for your tests 
11
101
1009
10007
100003
1000003
10000019
100000007
1000000007
10000000019

Trial division

A simple enumeration of possible divisors. The given number is checked by dividing by numbers from two to half of the given number. The given number is checked by dividing with a remainder by numbers from two to half of the given number. If the remainder of the division is zero, then the number being tested is composite.

Don't try to enter this form numbers larger than those given for testing, this may load your browser for a lo-o-o-ong time!
Verifying a number by dividing by all possible divisors is practically impossible for numbers whose bit depth is sufficient for cryptography.

Miller-Rabin primality test

The Miller-Rabin algorithm is a probabilistic primality test. If the answer is "The number is composite", then it is definitely composite. The other answer is "The number is most likely prime".

By repeatedly applying the test to the same number, the probability of error can be reduced to a level acceptable for cryptography. Twenty-fold verification is considered quite reliable.

Dumb Primality Test

The Miller-Rabin test requires significant computational resources. To speed up the process, it's advisable to perform a preliminary check by dividing the number being tested by small prime numbers: 3, 5, 7, … .

This form creates an array of prime numbers.

Probability of passing the test 0.6666666666666666

You'll definitely see a significant performance boost when using the first 500 primes.

For numbers of the order of 3-5 kilobits, a small speedup can be achieved by using an array of the first 3-5 thousand prime numbers.

Using an array of 20'000 elements for testing, will definitely reduce performance.

Seek

Prime number 3000 bits -- 1000..<and also insert 893 zeros>..0001021 click to insert into the following form.

Statistics Log
Legend
Δ -- Distance to a prime number
t -- Search time, seconds
BitLen -- Digit capacity
DumbLen -- The length of the sequence of initial primes used in the Dumb Primality Test
DumbTrue -- Number of preliminary positive results Dumb Primality Test
DumbFalse -- Number of negative results Dumb Primality Test
LikelyTrue -- The number of positive results is always 1, since we found a prime number
LikelyFalse -- The number of negative results of the main primality check is always one less than the number of positive preliminary checks DumbTrue
Pp -- Probability for a number to be prime in the neighborhood of that number

Specific Prime Seek

Safe and Sophie Germain primes

Safe and Sophie Germain primes -- 2 × PrimeSophieGermain + 1 = PrimeSafe

Prime = 3 (mod 4)

Some cryptographic systems require calculating the modular square root. For prime modules M = 3 (mod 4), calculate the square root using the formula X(M+1)/4.

Exapmle: Bitcoin Elliptic Curve y2=x3+7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663)

Subskribita.net