Vega, Primes, Cryptography and the Fields Medal Vega. praštevila, kriptogratija in Fieldsova medalja Dr. Toma/ Pisanski. Dr. Marko Boben. Dr. Alen Orbanič, Boris Horvat University of Ljubljana Faculty of Mathematics and Physics Jadranska /9. Ljubljana Slovenia Abstract Prime numbers have been studied since the ancient times. This seemingly theoretical part of mathematics forms the basis for cryptographic algorithms which secure the communications in the modem world. The list of famous mathematicians who were involved in the study of primes is very long. It ranges from Euclid. Eratosthenes. Fermat, Gauss, Legend re. Hudamard to ErdSs. Jurij Vega can proudly take place on this list. By publishing the table of primes up to 400,03! in 1797 he enabled further research in this area done by Gauss and Legemlre who formulated the Prime number theorem. Povzetek Praštevila so predmet raziskav že vse od antike. To na videz teoretično področje v okviru matematike je osnova za kriptografske algoritme, ki služijo varovanju komunikacij v sodobnem svetu. Seznam matematikov, ki so raziskovali praštevila, je zelo dolg, obsega imena od Evklida in Eratostena, prek Fermata, Gaussa, Legendra in Hadamanla. do Enlosu. Na ta seznam se lahko s ponosom uvrsti tudi Jurij Vega. Njegova objava praštevil do 400.031 iz leta 1797 je omogočila nadaljnje raziskovanje podmčja tudi Gaussu in Legendru, kije oblikoval Izrek o praštevil i h. 308 PRIME Nl.'MHHKS 309 Introduction Vega accomplished many very important achievements in mathematics. He published several editions of logarithmic, trigonometric, and ballistic tables, lectures (on geometry, land surveying, infinitesimal calculus), handbooks (Logarith-misch-trigonometrisches Handbuch, etc.). However, it is not well known that he was also interested in problems in number theory. He published a table of prime numbers and tables of decompositions of numbers not divisible by 2. 3, or 5. Prime numbers A prime number, or simply a "prime." is a positive integer p > 1 that has no positive integer divisors other than 1 and p itself. For example. 13 is a prime and 1") = 3 • 5 is not. The history of primes is very long. The ancient Greeks knew of primes and Euclid proved in his Elements (Book IX) that there were infinitely many of them. In about 200 BC Eratosthenes devised an algorithm for calculating primes called the Sieve of Eratosthenes. After a large gap during the Dark Ages, the next important results about prime numbers were made by Fermat. Among them, the result which is known under the name Little Fermat Theorem is best known. It states that if p is a prime number and a is a natural number then a? = a (mod p). The first known table of primes is a table of the least prime factors of the positive integers up to 800. This table was created by Cataldi in 1603. The least prime factor of ii is the least integer greater than 1 that divides n. Cataldi's table was soon followed by others: see Table 1. In 1776 Anton Felkel. a schoolmaster from Vienna, gave a table of all prime factors of numbers not divisible by 2. 3. or 5 up to 408.000. But only a few copies of the printed edition were sold: most of them were scrapped and used for cartridges in the Turkish war [3]. He claimed that he computed primes up to 2.000.000. but due to lack of interest the result remained in manuscript form. Vega published a table of primes up to 400.031 in 1797 [4]. In the second volume of his Logarithmic-Trigonometric Tables ([4], Figure 3). the table of primes ranges from 102.001 to 400.031. The actual number of all primes in this interval is 24.096. which matches the number of primes in the list given by Vega. But it turns out that some primes are missing from the list and that the list contains some composite numbers. For example, the number 152.053 = 293 ■ 521 is listed in the table (page 99 of [4]): see Figure I. An example of a missing prime is 185,429. It should be listed between 185,401 and 185.441 but it is not; see Figure 2. The list of primes of this extent can be now adays obtained in a lew seconds using the computer program Mathematica. This was how the authors were able to detect errors in Vega's tables. 3 N EGA. PRIMES. CRYPTOGRAPHY ANI) THE FIELDS MEDAL Limit Who When IVpe of table 800 Cataldi 1603 least prime factor 100.000 Brancker 1668 least prime factor 100,000 Kruger 1746 primes 102,000 Lambert 1770 least prime factor 408,000 Felkel 1776 least prime factor 400,031 Vega 1797 primes 1,020,000 Chernac 1811 least prime factor 3.036,000 Burkhardt 1816/17 primes 6,000,000 Crelle 1856 primes 9,000,000 Dase 1861 primes 100,330,200 iKuiik 1863? least prime factor 10,007.000 D. N. Lehmer 1909 least prime factor 10,006.721 D. N. Lehmer 1914 primes Tabela / table I. Tabele prašlevil pred elektronsko računalniško dobo (iz [2]) / Tables of prime numbers before the electronic computer age (from [2]) Slika / figure 1. Številka 152.653 ni praštcvilo, saj je produkt številk 293 in 521 (str. 95). / The number 152,653 is not a prime since it is a product of 293 and 521 (page 95). PRIMI- NUMBERS 311 ; • ' 1 cJ-JQ > i 19 yy • o 49 51 »V 1B46 69 71 1846 $7 iU6 93 -*C ^4? . 7 Qy 184^ t L 271 — X l4Sy i * i >3 1853 1-853 itd tg54 l 854 >9 6> - ^ ?J Oi i»rv >:? j I g^C C? | i o i^j 6g67 i J 9 i S6c z z Igt^? 185429 Slika / Figure 2. Na seznamu manjka praštevilo 185.429 (str. 99). / The prime number 185.429 is missing from the list (page 99). Vega's tables were known as very reliable. Vega himself offered a prize of one duall to anyone that could find an imperfection in his Thesaurus logarithmorum |5|. which would lead to an error in computation. Gauss, who reviewed Thesaurus [ 11, reported that he did not find any errors after checking some values of logarithms in the lirst part but that there are several in the second part. Gauss also remarked that Vega was probably not aware of what kinds of imperfections could actually occur, but also said that he was not informed of any case that the reward had actually been paid out. At that time, there were many authors of various tables that used the same stimulation. According to Gauss [1], only Kohler had requested rewards for four errors. Using the tables of primes by Lambert and Vega, the great mathematicians like Gauss and Legendre were able to guess the prime number theorem. Gauss carefully checked the tables of Lambert and caught several errors. This shows that probably no tables of that time were error-free. The prime number theorem gives an asymptotic formula for the prime counting function rr(/>). which counts the number of primes less than n. In 1791. Gauss suggested the formula 312 N EGA. PRIMES. CRYPTOGRAPHY ANI) THE FIELDS MEDAL ~(n) ~ n/lnn, which was later refined to tt(/)) ~ Li(n), where Li(n) is the logarithmic integral. The prime number theorem was proved independently by Hadamard (1896) and de la Valee Poussin (1896). On December 24. 1849. Gauss mentioned in a four-page letter 110|.| 11] to his student Johann Franz Encke, a lieutenant in the artillery, that he used Vega's tables to confirm his estimate (see Figure 4). Finding an elementary proof of the Prime number theorem remained a challenge for the next fifty years, until it was produced by Erdos and Selberg in 1949. Paul Erdos (1913-1996) was one of the most prolific and eccentric mathematicians of the past century [6|. He spent the last two decades of his life traveling from university to a university to work with mathematicians on problems in many different areas. He wrote or co-authored 1,475 academic papers. His extensive work with many people gave him the idea to start research on collaboration among mathematicians. An Erdos number is defined in the following way |9|: Erdos has Erdos number 0. Erdos's co-authors have Erdos number 1. people other than Erdos who have written a joint paper with someone with Erdos number 1 have Erdos number 2. and so on. If there is no chain of co-authorships connecting someone with Erdos. then that person's Erdos number is said to be infinite. Erdos numbers of mathematicians currently range up to 15. but the average is less than 5. and almost everyone with a finite Erdos number has a number less than 8. The authors of this paper have Erdos numbers 2. 3. 3. respectively. Back to the prime number theorem. There is an interesting story about the proof of Erdos and Selberg. Erdos sent a postcard to some friend informing him about the proof. When Selberg met this friend, he told him that Erdos and some "what's-his-name" had an elementary proof of the prime number theorem. Selberg felt offended and published the result alone. Among other work, this proof brought him the Fields Medal, which is considered the premier award in mathematics, often called the "Nobel Prize in Mathematics" (although its monetary value of about S9.500 cannot compare to the Nobel Prize). Prime numbers today have an important application in cryptography. They are the basis of the RSA encryption system [7J. The system uses the fact that determining whether some large number is a prime is a computationally hard problem. Until recently, all algorithms for determining whether some number is prime were of exponential time complexity. In [8| a polynomial algorithm was found. (Un)fortunately the algorithm has still large time complexity (0(n12)). Because Vega was also a soldier, we may consider the role of primes in wars. The first known use of primes in battles was the use of Felkel's tables for cartridges, as mentioned before. In the last century and nowadays, cryptography plays an essential role in communications in the army. PRIMI- NUMBERS 6 I G c or g V cga's, TUrrcr* milicntifulien Wrtric-Tlumfli*-flrfian- . Mujms uinH 1>rtffcfi'rt7* dcv Matlioiiiu:iK de«. Icnii.v. l. kftnipl. ArtHlc.-te.Tivn« . . o • ■.apnnHirciutoi; il«t Ubntpl i »rnUiirirauniiolicn t •mbUtbliaft dei WiftcnlchhitKU Kli tihnmpci;, log arirhmifch - t r i go n o m c trii ch c T A F E L N »ipiiji i r. d f :u i u ni GfV.rtKr'h # r M « t >i ? tr .i t i k T 2 t e 1 n v: n d F o r m c 1 n. n r> s n a. fTif, T,»sVf .'.Vsu, vfi.v.t) v. v. a j«**". 1» V » v..-, U.tK-V l-fusifi. V> ■ - -»ije«©.-«.- I * i p r i J. i« .•v....Sv.-V^jt-.-■JIV. » - o Slika / Figure 3. (Nemška) naslovnica drugega dela Vegovih logaritemsko-trigonometričnih tabel / The (German) title page of the second volume of Vega's Logarithmic-trigonometric tables 7 N EGA. PRIMES. CRYPTOGRAPHY ANI) THE FIELDS MEDAL Pe^jS i L Ju ? ^r««^ 7 > m, t d -š/forti J. u rim t ' Tt *n i/1* Sr. r* 4th , lm ^IfvCr J/j Z ^f), "V tu Ckili d uJvCh , /Vej il//afe •Ctt^Jt* c WM,£W V r , cwTct dti,, ^. t, ^ v^rxi.! iCniM-t /itn J>r\-p+/f\>rKiA. J* 'l , Jo yyCmc^ ^-rfnjt. n /KiJtt >lu.rxA /a J f JiL ' J to* v »trvft* d t* *jevJ e. r*u- »(■} 1 ui&Ml , tltinfC mene y vc J^re.u.J* -m Itn 2/o incfizC^u^ »im s o-n.tr, fd* /d v /M /te* h&- ">■*-' h l**l) let* 'tišini, 'yiO^J-^txJjW v* Le t tU icA cUc CfcliUt. a-HuT^-hle* ; dr uJi litA jC?^ tliy.k (c4(tk- JU* chui(uM ^o^u^-jcstil ^-v. . t/vihr h*. tutllu t» - J' /U«/ f'?!*.« Irltrn v^Wt, JaliX^Jtb*- JiAttlu. ^Utf tU-^v eA«* > 1 Slika / Figure 4. Gaussovo pismo svojemu študentu Johannu Fran/u Enckeju, I. stran / Gauss' letter to his student Johann Fran/ Encke. page I PRIMI- NUMBERS 8 iLftr SOO ooO {oon ooO I J C O 000 laoo aoo 1 foo oo" •}ooo ooo Cut 4/ ffi 78 so i IHHZ 14-sm 161,01 C 4i SoC,^ +}o,A l^out.3 +1/1,8 tlCijyo.C -j-itf.C H i S J by -+- 4 jl\>7VJ +17/,/ 'WVf.O -Y'lbtf-fl 1I7103, r -yn e ( 1 loV Cy, cC'e W CclX -t- 6 s, 1 4- Ify I -----^ IFiitiJk-^ j"^ aiV . irrUu^ -^J/ri-O- "v^-. rej/lc^VC ^"Avtt A = ' t.cf^Me 1.07681 1,0 7fi-u 1,0 IS if TI 7j U07*< cLrt ^renjz. A lUe^CUc 1 i-Au w« ve-rf e J*« (, ffirvflt^ Jet* t^M aU UTJ c lA fen*. YtfnuditWy . kax-n Ttut,f tUy') t'.,« ti{ J* fa'J^- ft* ** u-ovtc*.} cUt <6, 'U4*Ml /J- ult, I ^jLvi t«, r —i- Oik ^rii •?<£«/<«, Xa^ Jcci Sfyfer^'-t • ri / T1 " r / 3* ft^c I &C r ----- ' ii aU ItrJ Tl - I J. d IK 7f = -V /, i m L ; cu>. Zm^J^*- Sj 00U 0..C000O IuJii* j r ^f flvjju*13 Ivt vitMtubf- t(fcx ^r" ,tUjy ti I'l't* JujJjJ.- 4-t tyofh ^uj-^rk^U ^yjjuA k/, CkLnU ^H. —. k>lr J t 'W n^ry.* IjCeiy^L^fj v^yyt/^ ^ felUm {+U Keenly 7 c£t Jle Tu^bi- .b^jwyuOtw, cUji if 0U1. fwv»\yJJ.u ii, I A i&Uu. iKlU nt*/1** der-i cui-LoJ-tfi, cke, vii aw -n.V< /v huih/n ^e^aji- , ^,'e i^nj« \ooooo Slika / Figure 6. Gaussovo pismo svojemu študentu Johannu Franzu Enckeju. 3. stran / Gauss' letter to his student Johann Franz Encke. page 3 I'KIMI- NUMBERS ffclx, a^f y^,/ (/Ycv,J OJavseJi. i^J 10 CAii yi Hjc« j J f Zt t t n ? ? n If S /1 £ »t. 1 0 i .iT J 791 -1 h 1 Ty^*- /jeHfud kif Y<-Al 'klIcJUh*^ u , dtc Y-ufaZ) li^f tu* j /I tU* "/> ( rcC X* /aj lOffoooi. IOl00pi/ hi 4. 100 Hemfv* Am/e» )t 4 tt-l^^lii. j II (i-^i f aUcy-t^^-. 7 fl. — J.| -4 4.tj.f.lt+ 0ieUt)U csf- eU^M- c(A r Ciyyr