Appendix 5. Prime table
(Primes near to 2^n, 10^n, factorial, primorial and compositorial)
(January 18, 2009)
[Japanese]
Abstract
In case we generate a n-digit prime number, the most primitive method is,
First, generate a random odd number and check the primarity,
If failed, add 2 and check the primarity,
repeat this procedure until the prime is found.
Almost all number choosed at random is usually composite,
so not starting from definite primarity check,
first we should check it is divisible by small primes (3, 5, 7), then filter by Fermat test.
In many cases, chosen number is sieved out, then we should try more definite primarity test.
We try to search,
by this primitive method.
The number of primes are,
- Smaller and larger 10 primes for small n
- Smallest and largest primes for large n
(Because the computation time for searching 10 primes is ten times of that of one prime,
and the time for primarity check becomes longer.)
- Small differences (i.e. N ± 1, 3, 5, 7, 9).
Primarity is checked by Solovey-Strassen test for base = 2, 3, 5, 7, 11, 13, 17, 19.
(So accurately say, they are probable prime.
But in very lowest possibility, then are all primes.)
We should finally check strict primarity by APRT-CLE or ECPP.
Prime table
[1] n-bit prime
First and last 10 n-bit primes
(bit length n=2, ... , 2600 : Jan. 18, 2009) First and last n-bit primes
(bit length n=2, ... , 4320 : Dec. 21, 2008) Primes of form 2n±1, 3, 5, 7 and 9
(n=1, ... , 4320 : Dec. 01, 2008)
|
-
n-bit prime number N lies between 2n-1 ≤ N ≤ 2n-1.
We search for the primes within these ranges from higher (2n-1)
and lower (2n-1) numbers.
This table means the primes near 2n.
These primes are available for generating the key pair of RSA.
-
The end of search range is up to n=4321 (computation limit of modpow in UBASIC (1300 digits)).
- Legend
|
[2] Primes near 10n
First and last 10 primes near to 10n
(n=1, ... , 500 : Dec. 01, 2008) First and last primes near to 10n
(n=1, ... , 1300 : Dec. 11, 2008) Primes near to 10n in small difference
(form 10n±3, 9, 10n+1, 7)
(n=1, ... , 1300 : Dec. 01, 2008)
|
-
We search for the primes near to 10n.
This table is also the smallest and largest primes in each digits.
And these results are related to prime gap near 10n.
-
The end of search range is up to n=1300 (computation limit of modpow in UBASIC).
- Legend
|
|
[3] Primes near to factorial, primorial and compositorial
|
-
(n-1)!+1 is divisible by n iff n is prime (Wilson's Theorem).
And N=n!±k (k=2, ... , n) has trivial factors.
In the other cases, primarity and trivial factors are unknown.
I searched for the primes near to n! (factorial of n)
up tp n=561 (computation limit of modpow in UBASIC).
-
#Pn denotes the pruduct of primes up to n-th prime.
#Pn = P1 * P2 * ... * Pn
This product is often called as "primorial" from the analogy of "factorial".
This number is used for the proof of the infinity of the number of primes,
because #Pn+1 is not divisible by Pk (k=1, ... ,n).
I searched for the primes near to #Pn
up to n=437 (Pn=3049) (computation limit of modpow in UBASIC).
-
From the analogy of factorial and primorial, we name the product of composite numbers
as "Compositorial".
(Caution ! : This term is not commonly used. We use it only in this page.)
For example, in case of n=10, factorial, primorial, compositorial are as follows;
F : 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
P : 2 * 3 * 5 * 7
C : 4 * 6 * 8 * 9 * 10
Compositorial #Compn is represented as
#Compn = n! / #Pk
where k is the largest number such that Pk ≤ n.
We search for the primes near to #Compn
up to n=538 (Cn=658) (computation limit of modpow in UBASIC).
|
Legend
[1] n-bit primes
For n less than 7, all primes are in a list (because the number of primes is smaller than 10).
For example,
5 | 1, 3, 7, 13, 15
denotes
24+1 (=17)
24+3 (=19)
24+7 (=23)
24+13 (=29)
24+15 (=31)
are the 5 bit primes.
For n larger than 7, first and last 10 primes are in a list.
For example,
8 | 3, 9, 11, 21, 23, 29, 35, 39, 45, 51 | -59,-57,-45,-33,-29,-27,-23,-17,-15,-5
denotes
27+3 (=131)
27+9 (=137)
...
27+45 (=173)
27+51 (=179)
...
...
28-59 (=197)
28-57 (=199)
...
28-15 (=241)
28-5 (=251)
are the first and last 10 8-bit primes.
[2] Primes near to 10n
last 10 primes nearest to 10^n (form 10^n-a) [n] first 10 primes nearest to 10^n (form 10^n+a)
---------------------------------------------[-]-----------------------------------------------
-8, -7, -5, -3 [1] 1, 3, 7, 9, 13, 19, 21, 27, 31, 33
denotes
101-8 (=2)
101-7 (=3)
101-5 (=5)
101-3 (=7)
are the primes smaller than 101, and
101+1 (=11)
101+3 (=13)
...
101+31 (=41)
101+33 (=43)
are the primes larger than 101
Furthur computation
- Extend the search range for first and last primes
- Strict primarity check with APRT-CLE or ECPP
E-mail : kc2h-msm@asahi-net.or.jpHisanori Mishima