On prime numbers in March 2008

Characteristics of prime numbers

Prime numbers are mysterious.Many people have been enchanted with the fascinating characters of prime numbers and they have left numerous outcomes in the world of mathematics.

Details of such contributions are, for example, presented in these two books [1, 2].

A prime number (p) is a number that can only be divided by 1 and itself (p)”, which are trivial divisors.

A number that does not have a "true divisor" is a divisor other than trivial divisors, and that has no factor form other than p = 1 x p.

In other words, it is a number that cannot be represented by a product of numbers smaller than its own (p), while it is the number that forms the basis of all other numbers by combining with other prime numbers.

In this sense, it is the number that represents “No.1 & the Only One”, which is the slogan of Kyoto Computer Gakuin and The Kyoto College of Graduate Studies for Informatics .

The fact that it is divisible only by itself means "The Only One".

Also, it is the number that is “No.1” in the sense that it represent the first of the group of numbers that is the product of {prime number p and prime number greater than p}.

For example, the prime number p = 41 is divisible only by 41, and it is the first number in the group of numbers {41, 41 × 41, 41 × 43, 41 × 47, 41 × 53,…}.

This signifies that one begins by understanding oneself and the group it belongs to.And the concept plays a role in determining whether a number larger than itself is a prime number.

For prime numbers

The "elastomeric sieve" method is one of the ways to discover all the prime numbers that are smaller than a number (N).The procedure can be written as follows.

1. Using Bit array pr[1:N] to represent prime candidates up to a number N.All initial values are on (1).

2. Starting from the number p = 2, the pr values of all multiples of p are turned off (0) and removed from the prime candidate.

3. Repeat step 2 until the number p is (p × p)> N.

4. A number whose pr value is on (1) is a prime number up to a number N.

For example, there are 25 prime numbers up to N = 100.

{2, 3, 5, 7, 11 , 13, 17 , 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

A prime pair whose value differs by 2 are called twin prime numbers.

By the number N = 100, there are 6 sets of twin prime numbers.

[11, 13] [17, 19] [29, 31] [41, 43] [59, 61] [71, 73]

The pair [41 and 43] in particular is memorized with a pun “yoi yomi” (good reading).

Here are slightly larger twin prime numbers [1,000,037, 1,000,039].

Also, 51,090 digit twin prime numbers: [33,218,925 × 2^169,690±1] were found by computer calculation in 2002.[3, p.33]

Are there formulas for prime numbers?

Now, for what are the "elastomeric sieve" method and other methods based on it in use?

It is because a formula or equation to solve the following two points has not yet been found.

Question 1. How many prime numbers are there up to the number N?π (N)

Problem 2. What is the K-th prime number from the number 2?prime [K]

Many people have tried to solve this problem and by doing so contributed to many mathematical concepts [1, 2].There are sequences, infinite series, relations with e and π, logarithms, and Riemann zeta functions [1, p107].

The zeta function is defined as ζ (s) = Σ _{n = 1} ^∞ (1 / n ^s ) = 1 + 1/2 ^s +1/3 ^s + 1/4 ^s +…
Stated as: ζ (2) = π ² / 6 [1, p.93].

Lehman's conjecture[2, p. 15]: "Is there a general rule or formula for the number of prime numbers less than N?" led to Lehman's prediction: "all the real parts of nontrivial zeros in a zeta function are 1/2" [2, p. 17].

It continues to be unresolved today.

The following prime theorems and their consequences seem to be accepted as close to the solution [2, p 70 -71].

Prime number theorem: π (N) ~ N / log N (The symbol "~" represents approximation)

Consequences from the prime number theorem:
　　　　　The probability that N is prime is ~ 1 / log N
　　　　　Kth prime number ~ K log K

The role of computers

Computers have greatly contributed to the calculation of prime numbers and the verification of the properties of prime numbers.

For example, the following trends and results have been derived.

(1)The number of prime numbers before and after the number 10⁷, for the range of100, is not the same.[1, p.16]
9,999,901 907 929 931 937 943 971 973 991 (9 in before)
10,000,019 079 (2 in after)

(2) Number of prime numbers up to N π (N) And the average interval of prime numbers (N / π (N) ).
[1, p.77 & p.137] [2, p.60 & 64]
The average interval increases by about 7 for every 10³ N.

Conversely, let’s find K-th prime [K].This is in the range of 1 word 32 bits, which we found a little while ago, and now we can find it much faster.

What happens in the range of 64 bits per word?Please try it.

(3) It was discovered in Germany on February 18, 2005 that (2^25,964,951 -1) is a prime number of 7,816,230 digits. [1, p.315]

(2 ^M -1) which is also a prime number is called a Mersenne prime number.

Recently, (2^32,582,657 -1) was reported on September 4, 2006 as a prime candidate with 9,808,358 digits. http://ja.wikipedia.org/wiki/メルセンヌ数。

(4) Mersenne number (2 ⁶⁷ -1) is proved to be the product of two prime numbers, 193,707,721 × 761,838,257,287.(1903) [1, p.336]

This result evolves into an RSA encryption system based on the product of 2 prime numbers (P, Q). (Ron Rivest, Adi Shamir, Leonard Adleman, 1997).

This is based on the fact that it is easy to find the product M of P and Q, but conversely, it is difficult to factor a large number M into two prime numbers.Modal calculation (modulo) is used there.

RSA is well known as one of the public key cryptosystems (1976, Whitfield Diff & Martin E. Hellman).[1, p341]

Evolution to quantum computing

The core of RSA is that factoring large numbers N takes computation time.

However, "Shor's factorization algorithm" which may be solved in a short time has been proposed in the quantum calculation using the quantum computer.It takes advantage of the periodicity of legal calculations and the superposition of quantum calculations.

Even if Shor's algorithm is simulated using a current computer, its characteristics can be fully demonstrated.
The world of prime numbers will endlessly expand.

[1] Marcus du Sautoy, The Music of the Primes, 2003,

By Marcus du Sautey (translated by Hoshi Tominaga),
Music of prime numbers, Shinchosha, August 30, 2005, 2,400 yen.

[2] John Derbyshire, Prime Obsession, 2003,

By John Derbyshire (translated by Shunsuke Matsuura),
Prime obsession, Nikkei BP, August 30, 2004, 2,600 yen.

[3] Keith Devlin, The Millennium Problems, 2002,

By Keith Debrin (translated by Junichi Yamaguchi),
Exciting mathematics, Iwanami Shoten, August 25, 2004, 2,940 yen.

Katsumasa Watanabe