Reference / Paper · 1995
A Very Fast Electronic Number Sieve (PhD thesis, University of Manitoba)
Thesis describing the MSSU electronic sieve, with a history of sieving devices in section 1.6.
Reference / Paper · 1995
Thesis describing the MSSU electronic sieve, with a history of sieving devices in section 1.6.
A Very Fast Electronic Number Sieve by Richard F. Lukes A thesis presented to the University of Manitoba in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science Winnipeg, Manitoba, Canada, 1995 @Richard F. Lukes 1995 n*B N,{onarolibrav Bibliothèque nationale du Canada Acquisitions and BiblìograPhic Services Branch Direction des acquisitions et des services bibliograPhiques 395 Wellington Street 395, rue Wellington Ottawa (Ontario) Ottawa, Ontario K1A ON4 K1A ON4 Your l¡le Votre rélérence Ou( l¡le Nolrc rélércnce The author has granted an irrevocable non-exclus¡ve licence allowing the National LibrarY of Canada to reproduce, loan, distribute or sell copies of his/her thesis bY anY means and in any form or format, making this thesis available to interested persons. L'auteur a accordé une licence irrévocable et non exclusive permettant à la Bibliothèque nationale du Canada de reproduire, prêter, distribuer ou vendre des coPies de sa thèse de quelque manière et sous quelque forme que ce soit Pour mettre des exemPlaires de cette thèse à la disPosition des person nes intéressées. The author retains ownershiP of the copyright in his/her thesis. Neither the thesis nor substantial extracts from it maY be Printed or otherwise reProduced without his/her permission. L'auteur conserve la ProPriété du droit d'auteur qui Protège sa thèse. Ni la thèse ni des extraits substantiels de celle'ci ne doivent être imPrimés ou autrement reproduits sans son autorisation. ISBN 0-612-13321-4 Canadä Nome Disrl¡fc/ion Ahsfrocfs lnf¡¡motrbno/ is neorly describes lhe content of your dissertlion. CorqeuT¿R Scr srr, cg fcTqreH UM.f ST'UECÍ CODE SI'åJECTTERM Sulrisct CoiÊgories mE HUmA¡tffi¡ES A88Þ Sg€¡e& S€¡EnreEg COTilHKfiffiIS ITID THE ANIS 07n 0377 oe00 0378 0357 0723 0391 0399 Music.......................... 0708 Soæh Communicotion 04t 3 0459 TfræCr ...................... 0Áó5 Psrrclroloqlr .....0525 Ri¡dirn 1.................................. 0535 Ref iq¡oùs ............. ..................... 0527 Sciõces -............ ......................O71 4 Secondorv ................................ 0533 Sociol Scíences ......................... 0534 Socidoov of ............................. 0340 soociolll............. ...................... 0529 Tèocher Troininq ....................... 0530 Tech¡roloov......1........................ 071 0 PHttosoPHY, REuctoìt ÂltD THEOTOGY Tesls onff¡'loosurements ............ 0288 Vocotionol .......... ...................... 07 A7 IAIIGUÂG' IMNAÏURE Al{D ultGUlsltCs Lonouooe [inquisfics oó79 0289 0290 Mdilem .............. o291 t'erËrol ............. A¡rcient............... Lilerofure Geneml .............................. 0¿0'ì Cfossicol ............. ..-.............O294 Coqporotive ..................-..-. 0295 Mediorol ............................ 0297 Modem .............. ........ -....... 0298 Ahicon ............................... 03t ó Americon ..-......................... 059'| ,Asion ................................. 0305 Conodion f Enolishl .............. 0352 Conodion {Fre-nchi .............. 0355 Enolish ............................... 0593 Germonic ..........-................ 03.| I l¡olìn Americon .................... 031 2 Middle Eosfem .................... 03 I 5 Romonce ............................ 03.| 3 Slovic ond Eosr Eurooeon .....031 4 sfiIAtSC$|CS Americon Studies ...................... 0323 Anthroooloov Arèhoeõlocv ....................... 032¿ Cuf turol ...::........ ................. 0326 Physicol ......-...... .................0327 Busineis Adminisholion Generol ... -.......................... 03 I 0 Accounlino ......................... 0272 Bonkinq ..L.-....... .................o77o Monodóment ................:..... 0454 Morkeiino ........................... 0338 Conodion Stùdies ..................... 0385 cconomtcs Generol ..............,........ -...... 050 I Aqriculturol ......................... 0503 Cðmmerce-Business ............. 0505 Finonce ..............................0508 History................................ 0509 Lobor'................................. 05ì0 Theory ................................ 05 ì I Fo|k|ore....................................0358 Geoorophy......... ...... ....... ...... 03óó $.ero;ntcilo9y .. . ........................ 035 1 nrslc)ry Género1 .............................. 0578 rHE SCIET{GES AIID ËI{GIT{EERING BtotoGtürsqtilcs - C'enerol -............................ 0 47 3 Geodesy .................................. 0370 Geolooy ............. ...................... 037 2 Aqronomy .......................... 0285 Añimol Cûlture ond Nutrition ............. ............. 047 5 Animol Potholoqv ................ 047ó Minerol&v............................... 0¿l I PoleobotoÁv ............................. 0345 Aqrículture . Food Science oñiJ Technoloqy ...................... 0359 Foresrry onãWìldlib ........... 0¿78 Pfont Culture ....................... 0479 Plont PoÈology ................... 0480 Plont Ph¡rio|ogy .................. 081 7 Ronqe Monoqemer'l -- ---.--. --.0777 Woõd Technõloov ...............O7 Áó Bioloov dinerol .............................. 030ó Anotomy ... -...... -................. 0287 Biostotisiics ......................... 0308 Bolony ......... -...................... 0309 Cell .-................. ................ 0379 Eco|oqy .............................. 0329 Enrmã|oqy................ ....... 0353 Genetics l-............ ............. 03ó9 Limnoloqy ........... ..... -.......... 0793 Microbióloqv ...................... 0¿ t 0 Moleculor :......................... 0307 Neuroscience ...................... 03 I 7 Geonoqroohy.................... 04ì ó Phnidùv :...:..................... 0433 Ro'diotioñ'............................ 082 1 VeÞrinory Science -.............. 0778 Z,*l.ogy. ......................0472 ^. óropnystcs '(Énerol .............................. 078ó Medicol .............. ....-..-.....-..0760 TARIH SCIIIICTS ueoonvsrcs ................-..-.......-.. l-tvdioli¡qy uJl J ......0388 Pofeoecoloóy ....... ....... --. -.......-.. 0426 Poleontoloôi ............................. 0¿ ì I Poleozooldíív............................ 0985 Polvnoloqvl'......... .....................0427 Phúsicol C'eooroohv .................. 03ó8 . Physicol Oceõncþóphy ............ 04 1 5 HüTTH AilD EHVIROilNT}ITAI. sctilGs Environmentol Sciences ............. 07ó8 Heolth Sciences Speech Potho|oqv .............. 0¿ó0 loxrcoloqy .. .... ............0383 Home Econo'äics ...................... 038ó PHYS|(Â[ SCEilCtS Ancienl..-............................0579 Medievol ............................ 058 I Modem .........-....................0582 Block ..................................0328 Africon ........... -................... 033 I Asio, Austrolio ond Geonio 0332 Conodion .........-................. 0334 Europeon ............................ 0335 Lotin'Americon .................... 033ó Middle Eosern .................... 0333 United Stotes ....................... 0332 History of Science ..................... 0585 tdw.. :....................................... 0398 Politicol Science Disserlolion Abslrocls lnlernolional esf orgonisé en colégor¡es de sujels. Veuillez s,v.p, choìsir le suiet qui décrit le mieux volre lhèse et inscrivez le code numêrique opproprié dons l'espoce réservé ci-dessous. |-|-l-n {JM.I SUJET CODE DE SUJII Cotégories por suiets H¡'!AñA¡{¡IÊS ET SGIEN€ES SOGIAIEs 1ecrure.....................................0535 Molhémorioues.................... 0280 Musioue .1.. os22 ...0422 O¡¡eniorion êr conr!ho1ion....... .05ì9 Philosoohie de l'éducotion ......... 0998 Phvsio,ie 0523 Conodi€iñe........................033¿ 8rors.Unis ............... .......... 0337 Eurooèenne 0335 Movån-orienrole 0333 Loti'no ornéricoiñe.... ........... 033ó Asie, Aurrolie et Océonie....0332 Hisroire des sciences... 0585 P¡óq¿mme! d érudes êr enseionemenr .. .. Psvcho!ãoie . 0727 os25 5crences .................. ....... . .. (J/ l4 Sciences so<ioìes....................... 0534 Sociolooie de l'èducorion........... 03¿0 Technofôsie............... ......... .. 07ì0 I.ÂNGUT, TIflÉRAfURT Plonilicorion urboine ei régionole ........... .. . ....A999 çenero rles ..... ........ . uô l5 Tf Adrni¡irroiionÕuhlioùe 0617 _ trenerolrlê! .................... .. .uôly Ancieññes.... .... .................0289 1inouis|ioue...................... ..0290 Mo?erne!.................. . 029t Droil et relôrio;! internorionoles .............. ..0ól ó Sociolôo;e Génirolites............... a626 Litlérolure Aidê er bien.òrre sociol........ 0ó30 Gênêrolirés..................... ...0401 4nciennes........................... 029¿ ComDorée ..........................0295 Medíévo|e.... ......................02e2 Moderne.............................0298 Alricoine ............ .. .. . .......031ó A¡éricoine ......................... 0591 Anolôise....................... .. . 0593 Asi¿lioue.-............. 0305 conoúenne lAnoloisel ........ 03s2 conodrenne lfronco,sel . ....0JJ5 Ge¡monioue élobli";menis oénitenrioire3 ...........03r 0 .........0454 03ì ì ...........0770 ..........0272 ..........0338 torìno om'áricoine................ 03l 2 0313 Slove êl €t.europænne .....0314 SE¡EN€85 ET INGÉNIER¡F .. Çèolçie. o473 Hvd;ol6oiå. ... Mi',¿¡olåoie 0285 ..........0578 0372 S(IINCTS PHYSIOUTS o38s Sciences Pu¡es or'ì ì Chìmie Genê¡ol'rés....... .................0¿85 Biochimie ............... .. ¿87 . Chi¡nie ooricole..... ....... . 07a9 Chimie oñol¡io¡e 0Á86 Polèozooloäie...........................0985 Polynolosie-........... .. .... ......... 0427 Chimie min¿'rolå........... .. O¿8e (hrm e nucl-ÀoÍe ... O/34 Chim;e o¡oonioue ............... 0490 Chimieohãrmoceurioue. 0491 oÄ9a PofvmCres ............. .... .0¿95 Rodrolron.. .. O/54 Molhémo1ioues..................... .. 0¿05 s(lt (ts Dt ta saNli It Dt rrNvtR0 Ntft$Nr Économie dome!rioue............. .. 038ó 5c ences de I envroñnement 0/óa Sciences de lo sontê Générolirés .........................05óó A¿minislrorion des hìóitôux O7ó9 Alimenrôlionelnukilitn . ..0570 audiolø;e.... . o3oo chimiôrÊ'érÒôie o99) Dênriterie..:...... .. ........ .....05ó7 Déveloooementhrmoin 073A Enseioååmenr................ .. . 0350 l.-,;"|""i. oga? 1or5rrs.................................(J5/5 Médecine du hovoilel thérôó;e Mede¿ile er ¡hnu¡oie 035¿ 05ó¿ Obsréhioùe er ovñËcôlôôiê 0380 oohrolmhlôore:i........ .:...... 038ì Ohhoohonie-.. .... .. . Porhofooie .... Oaóo O57l Phormocre .................... .....u5/2 Pho¡mocolooie . .... .. . .... . .0a19 Phv<iorhé¡oàie RôiliôlMiÞ 0382 o57À Sonré mËnrol-" . .... .... .........0347 5orn5 nlrrmreß ...............U5óv loxicologie . .... ..................0383 . . Phvsiouå... : .. . ' c¿nè,olirés .........................oóos AcoulioLre.............. O98ó orroohvlioue.-..... 0ó0ó Elecrroniqire èr élecrricir€ ...... Oó07 rru des el Dlosmo......... . .. ..o/5y Méréo¡olobie . ....... . ...qéaq upnqu€,.,, -........................u/J2 Porlicules {Phy!ique nucleonel.... ........0798 orôñioùe solide Phvsioue 07 Ág Phisiciue de l étår oól I Phísiciue moleculoire ........ .. oó09 Pl,i¡iciuenuclæire.... 0ólo Roijioi;on....... . .......025ó Sloliliques ......................... .. . 04ó3 5ciences Appliqués Et 1nformorioJe........................ lnqè¡ie¡ie inierethñ;ôùe3 er des relorions Slruclure et develoooemenr rocioles 0ó31 so<iol.............11........ ozoo Théorie er mérhodes ...........03¿¿ TrovoileÌ relorions industrie|jes......................0ó29 Tronloorls ... . ..... 0709 Tro'oìlsociol.................... 0¿52 Bioméd]co|e........... .. ..... .. 05al Choleur ei ther modvnomioue.......... . .. .03¿8 Ocèonosiophie physique . ... ....0415 P.lèôhôrõ¡idL,ê O3¿5 Poleðko|ooii........................ ..0¿2ó P.lÉÒ¡r.ld:è or'l8 O6t7 DémooroÞhie.......... .... ......0938 Erudeidd l' indi"id, er - de lo fomi |e........... .. .. ...0ó28 ErL:des des relotions Moyen.or;e.role......... .. 03r5 Romõne . ........081¿ Loisìrs...................... UNGUT5Í0Ut to¡gles. ,. 4ncienne...................-........ 0579 Mediévo|e...... .... ...............0581 Moderñe.......... .. ..........0582 H¡roire des ¡oir'.... .... . .0328 . .098¡ (Jenerolrles.. l)t.l/ Asrico|e ................. .. .......0539 Aulomobile . . 05r'O Condirìonne"i.* {Embo |oqel .....................05¿9 Gèñie oèroiooriol ...... . 0s38 Génie civil .:................... ...05¿3 Génie élecìronioue et elê(k;a!e . . .. .054a Génie inJurriel..... 05¡ó Gènie mèconioue................05a8 çenenucleorre........... u5ll Meconroùe ¡ôvôlê .. l)5Á/ Mèro lurbie . .. o7Á3 Science ðes rnorériou^ .... ....079a Technioue du oèlrole a765 (ì551 le.hnr.re Ìê.hni;1,ê( (ô.ir^i,êr pt . mrnrÞrê muni¿iooles.. .... .... . oss¿ T€chnoloiie hvd¡oLJlioue.. . osa5 Mèconiouê ôåôliiuéê o:]r'¿, Céorechnoìosii . .......... O¿28 fTê¿h""!"l,i.l a7e5 Recheiche ooé¡ãtiónnelle. . .. .. .079ó Tenieserris!us (Tech¡olosie) ....079¿ PSY(H0t0GtI (Jenerolrles |J621 Pe¡sonnoliré............ .................0ó25 Psvchobiolooie.... o3¿9 Psicholøie-cl;nioue aó?? Psicholdie d! c¿moo¡remenr o3B¿ Pricholoãie du dev¿lÒóóéñênr 0ó20 P!;choloãieexoérime;iirle.. 0ó23 Psicholoðie in¿ur,ielle .. o62a PsicholoËie ohvsiolooioue........ 0989 Psicholoãie lo.iole .: .:. . o¿51 Psichom5r,ie .... .. ............ oó32 @ A VERY FAST ELECTRONIC NIIIßER SIEVE BY RICH.ARD F. LÛreS A Thesis submitted to the Faculty of Graduate Studies of the Universify of Manitoba in partial fuifillment of the requirements of the degree of DOCTOR OF PEILOSOPEY @ L995 Permission has been granted to the LIBRARY OF THE UNMRSITY OF MANITOBA to lend or sell copies of this thesis, to the NAIONAL LIBI{ARY OF CANADA to microfilm this thesis and to lend or sell copies of the film, and LIBRARY MICROFILMS to publish an abstract of this thesis. The author reserr¡es other publication rights, and neither the thesis nor extensive extracts from it may be printed or othe¡-wise reproduced without the author's written per=rission. I hereby declare that I am the sore author of this thesis. I authorize the University of Manitoba to lend this thesis to other institutions or individuals for the purpose of scholarly research. I further authorize the University of Manitoba to reproduce this thesis by photocopying or by other means, in total or in part, at the request of other institutions or inclivirluals for the purpose of scholarly research. Abstract Number sieves are special-purpose devices used. for solving tional number theory. In this thesis we give a brief history certain problems in computa- of number sieves. We describe a single-chip sieve device, called the Scalable Sieve Unit (SSu), which has been to 'serl implement a parallel sieving device, called the Manitoba Scalable Sieve Unit (MSSU). The MSSU achieves sieving rates at least an order of magnitude greater than those of previous sieves through the use of parallelism and a tighily-coupled cleclicated control processor' We discuss ihe design of the hardware ancl software components which make up the MSSU sieving system. A number of applications of sieving are described, including many tained using MSSU' Some results on problems of quadratic tending results of Lehmer, Lehmer and Shanks. The iist of recent results ob- character are presente¿, ex- known pseudosr¡uare val'es is extended, and some eviclence is presented which suggests that the growth of this sequence is sufficiently rapid to ensute that primality testing can be performecl in ¿eterministic polynomial time. New results are presented with regard to quadratic polynomials with high asymptotic densities of prime values. We also extend the numerical investigation of Shanks on Littlewood's bounds on the Dirichlet L-function L(r,Ð. Some results on other problems are presented, including a search for a successor to Euler,s famous prime-producing polynomial, further computations of the Erdös-Selfriclge function, a new pseudocube value, and computation of pseudopowers for bases 2, 3, 5 and 7. A new method of employing parallel sieves is clescribed which we call sieving' We use this method on the MSSU to find three new three cubes problem, finding representations of the integers muiti-variable solutions to the sums of 110, 435 and 47g as the sum of three integer cubes. An investigation into waring's problem for cubes presents new evidence to suggest that all numbers are representable as sums of four positive or negative c¡bes, anrl that all numbers greater than approximately 1013 can be representecl cubes. lv as the sum of four positive Acknowledgements There are a numbe¡ of individuals who I would like to acknowleclge for their in the preparation of this thesis. assistance Foremost, I would like to thank my supervisor, Dr. Hugh C. \Milliams, for giving me the opportunity to be involved in interesting and rewarding research. r consicler myself very fortunate to have been one of his students. His financial support of my studies and in the building of oASiS II and the MSSU are greatly appreciated. Financial support was also provided by NSÐRC and the University of Manitoba Graduate Fellowship. I would also like to thank my committee members Dr. Duncan Buell, Dr. John Bate and Dr. Bob Mcleod for their careful reading of my thesis. I am very grateful to Dr. Cameron Patterson, the designer of the SSU single-chip sieve devices' Dr. Patterson's ingenuity and dilìgence in the design and clevelopment of the SSU made the MSSU project possible. The speed and reliability of these devices are truly remarkable. In the many thousancls of hours of sieving all of the SSU ¿evices have performed flawlessly. I would like to thank my fellow sturlent Mike Jacobson for his invaluable computations which are used throughout the thesis. I wish him the very best as he continues his stuclies in Germany. As well, I thank Dr. Renate Scheidler for her collaboration on computations of the Erdös-Selfridge function which provided me with an opportunity to meet both of these distinguished mathematicians. For answering scores of cluestions, f am grateful to the technical expertise ancl sense of humour of Gilbert Detillieux, Tom Dubinski, and Professor Daniel Salomon. Computer time on an Alpha workstation used for some computations in Chapter 7 was kindly provided by Guy Durocher and the Physics Department of the University of Manitoba. I would also [ke to thank Vaclav Zvonik for assistance in the mechanical construction of the MSSU chassis. I would also like to acknowledge the support and encouragement of my tennis friencls: Ken Hotz, Andy Kuc, Doug Stone, and Tony Weekes. I wonder if they have realizecl yet that I don't actually play tennis myself? There are many, many other people who helped me' or helped to change me, during my six years of PhD studier, uoã I lm glarl I met each and every one. Finally, and most importantly, I woukl like to acknowledge my parents who provi¿ecl me with the encouragement and motivation to undertake my PhD in the first place. I dedicate this thesis to them. I shall always be grateful that they sacrificerl everything by leaving Czechoslovakia in 1968 to ensure that I was raisecl in a free anrl clemocratic country. Contents fntroduction 1 1.1 The sieve problem I.2 Principles of Sieve Automation 1.3 Some Terms and Measures 1 ,f +À 1.3.1 Basic Components of a Sieve Device 4 I.3.2 Measuring Sieve Performance i) 1.3.3 Density of Sieve Problems 5 I.3.4 The Filter Mechanism I.4 Optimizations I.4.L Single Residue Optimization L4.2 Multiple Residue Optimization 1.5 Factoring using Sieves 1.6 History of Sieving 1.6.1 Early Sieve Devices 7.6.2 Lehmer's Sieves 1.6.3 Electronic Sieves 1.6.4 ASummary... The Manitoba Scalable Sieve Unit Architecture 2.I Motivation 2.2 The Scalable Sieve Unit 2.3 MSSU Overview 2.4 Comparison of MSSU with Recent Systems 6 7 7 8 a 10 13 I4 16 23 25 25 26 30 31 MSSU lfardware 34 3.1 Control Processor 3.2 Sieve Array 3.3 Sieve Chassis 34 38 42 MSSU Software: The Control processor Software 4.1 The Function of SSUMon 4.2 The Choice of Programming Language 4.3 SSUMon Overview 4.3.7 CPUS2BUG Resources Checkpoints 4.6 SSUMon Variables 46 48 50 51 51 53 56 57 4.6.7 The Enable Vector 4.6.2 The Output Mode 58 59 4.7 SSUMon Command Set 4.7.7 Host Communication Protocol 4.7.2 The Reset Command 4.7.3 Sieve Loading and Unloading 4.7.4 The Run and Halt States 4.8 44 49 4.4 Implementation of Residue Optimization 4.4.I Partitioning 4.4.2 The Counter 4.4.3 Ring Loading 4.5 44 Solution Processing 59 60 62 62 63 63 4.8.1 QSPI Routines 4.8.2 The WhichO Routine 4.8.3 Solution Pipelining 4.8.4 A Responsive Halt Mechanism 4.9 Filter Routines 4.9.1 The Virtual Filter - VIRT 64 oð 66 67 68 70 vll 5 MSSU Software: The Host Software 5.1 Host Software Overview 5.2 Format of Problem Files 5.2.1 PROBTEM Section 5.2.2 CONGRUENCES Secrion 5.2.3 Specifying Parallel Execution of Sieve Jobs 5.2.4 PARAMETERS Secrion 5.2.5 LOG Section 5.3 The Programs 5.3.1 The Configuration File 5.3.2 The Sieve Command 5.3.3 talker 5.3.4 stat 5.3.5 pulI . 5.3.6 Off-Line Solution Filters 5.3.7 Problem Generators 5.4 Implementation of the Sieve Manaqement Software 5.4.1 Multiple Precision Arithmetic 5.4.2 Shared Files 5.4.3 Use of Signals 5.4.4 Problem File Parser 5.4.5 The Daemon Process 5.4.6 The Sender 5.4.7 Solution Processing 5.4.8 Porting to Other Hosts 72 72 74 /Ð /Ð 76 79 82 84 84 85 86 86 87 88 89 89 90 90 91 93 94 95 96 97 Problems fnvolving Quadratic Characters 98 6.1 Pseudosquares a0 6.1.1 Pseudosquares and primality testing 101 6.I.2 Pseudosquare resrilts 707 vul 6.1.3 Negative Pseudosquares 115 6-2 Quadratic Polynomials Having a High Density of primes 6.2.1 The conjecture of Hardy and Littlewood 6.2.2 Some results III IL7 119 6.3 Polynomials of the Form ø2 + .4. 725 6.4 Lehmer-Lehmer-Shanks Problem V . . . 130 o.,) Examination of Littlewood's Bounds on Z(1,X) . . L32 6.5.1 The Analytic Class Number Formula 6.5.2 The Search for Unusually Large Regulators 6.5.3 Littlewood's Bounds on -t(1, Ð . . 132 133 135 Some Results on Other Problems 151 7.L On a Successor to Euler's polynomial X2 + X + +t 151 7.1.1 Computing ,4'(z) 155 7.2 The Erdös-Selfridge Function 158 7.2.1 The Sieving Algorithm 7.2.2 Implementation 7.2.3 Computational Results 159 160 I62 7.3 Pseudocubes 7.4 Pseudopowers 7.4.I A Heuristic Estimate for p2(r) 7.4.2 Pseudopowers of Other Bases 7.4.3 The c¿ Values 7.5 Two-Dimensional Sieving problems 7.5.I Sums of Three Cubes 7.6 Sums of Four Cubes and Waring,s problem Conclusion 165 169 770 771 173 177 177 184 193 8.1 ASummary... 8.2 Improving the MSSU 193 194 lx A Successor to the MSSU 8.3.1 More Hardware Rings 8.3.2 Greater Parallelism 8.3.3 Newer VLSI Technologies 8.4 New Applications A Summary of SSUMon Commands SSUMon Filter Algorithms 8.1 The Perfect Square Filter - pSQR 8.2 The Perfect Cube Filter - PCUB 8.2.I Description of the Initial Algorithm 8.2.2 A Sequence of Tbansformations 8.3 The Probable-Prime Fiiter - pBpM 196 196 198 i98 200 202 21,2 212 276 2I6 220 229 S,ist of Tahles 2.1 SSU Commands 28 2.2 SSU Signal Lines 30 2.3 Comparison of Recent Electronic Sieves 33 4.I SSUMon Modules 49 4.2 Sieve State Information (SSI) 58 4.3 Sieve Global Variables 58 4.4 SSUMon Commands 60 4.5 SSUMon Message Types 61 4.6 SSUMon Filters 69 5.1 Sieving Parameters 79 5.2 Log Message Types 82 5.3 Sieve Command Options í).+ SMS Signals 6.1 Pseudosquares 6.2 Negative Pseudosquares 116 6.3 C(D)-hichamps (D < 0) 727 6.4 C(D)-hichamps (D > 0) 727 6.5 Selected C(D)-hichamps 722 6.6 Computations to r = I07 for Select C(D)-hichamps 722 6.7 Values of llo and their sources 723 6.8 Values of. M, and their sources 124 ð,5 92 772 xt C(-A)-hichamps (,4 > 0) 6.9 126 6.10 Computations to ø = 106 for C(-A)-hichamps 6.11 C(-A)-lochamps (A > 0) 126 727 6.12 Computations to ¿ = 106 for C(-,4,)-lochamps 128 6.13 Lehmer-Lehmer-Shanks probiem IV L29 6.14 Lehmer-Lehmer-Shanks problem V 131 6.15 D : 5 (mod 8) Llf-lochamps - ULf-hichamps : 6.L7 D 3 (mod B) - ULf-hichamps 6.18 D:6 (mod B) - ULLhichamps 6.19 D : 7 (mod B) - ULl-hichamps 6.76 D: 1 (mod B) 6.20 5¡f" - Least Solutions 138 138 139 139 140 14r 6.27 íNp - Least Prime Solutions 142 6.22 -T Ro - Least Solutions (problem II) 743 6.23 -T Ro - Least Prime Solutions (problem II) 144 6.24 1-Bo - Least Solutions (problem I) r45 6.25 lfue - Least Prime Solutions (problem I) r+o 6.26 6Re - Least Solutions 147 6.27 6Re - Least 2x Prime Solutions 148 6.28 ïRp and 7Ro - Least Solutions 149 6.29 ïRe and 7Ro - Least prime Solutions 150 7.r Tabulation of A'(n) 7.2 Tabulation of the Erdös-Selfriclge Function 7.3 Pseudocubes 7.4 Pseudopowers to base 2 t.Ð Pseudopowers to base B 7.6 Pseudopowers to base 5 t.t Pseudopowers to base Z 7.8 Numbers d requiring r¿ cubes for 0 ( d < 3.43 x 108 189 7.9 Non-4-cubes in selected ranges of size 108 192 757 166 168 L72 174 175 )(l1 L76 S,ist of Figtr.res 2.1 SSU Block Diagram 2.2 SSU Scan Paths 2.3 MSSU Block Diagram 3.1 MC68332 Block Diagram 36 3.2 Simplified Schematic of the Sieve Array Board 39 3.3 Sieve Array Board Layour 47 3.4 Two MSSU sieves (one extencled from rack with cover rernoved). 43 4.r Calculation of the COUNT Value 52 4.2 Layout of RINGDAT 4.3 Operations on the Ring Data 54 4.4 Simultaneous Read and Write of SSU Registers 64 5.1 The Sieve Management Software t¿l 5.2 Partitioning Example 77 5.3 Multi-Variable Sieving Example 78 5.4 Sample Log Output 83 6.1 Pseudosquare growth vs. p 113 6.2 Pseudosquare growth vs. n 174 27 28 31 Ð+ XIII Chapter X. lntnoductíon L.1- The sieve problem Consider the simple problem of determining LT,where z7 is theleast positive non-s(ruaïe integer such that L7: 1(mocl 8), L7 : 1(mod3), Lz : 1or4(mod5), Lz : I,2 or a (mod 7). The solution of this problem is Lz - 1009. This is a solution, for the primes less than or equal to 7, to an important problem in number theory known as problem' Later, in chapter 6, we shal criscuss this probrem in detail. This problem is also an instance of a much larger problem Sieving Problem (GSP), in which we are given: the gtseudosq,ares known as the Generalized CHAPTER 1. INTRODUCTION 1. bounds A,B with B > A; 2. ,t moduli Trl1,rÍù2,,rr13r...,mt (m¿ ) 1,i- I,2,g,...,k) which we usually assume are relatively prime in pairs; 3. å sets of acceptable residuesF*¿ : {r¿j l0 < r¡¡ < rni} (i = L,Z,J,...,k). We are then to determine all c € Z such that A{r<B and ø (mod rn¿) e R4 (i = 7,2,9, . . .,1í). Some problems may place further rest¡ictions on o in adclition to satisfying this set of ]inear congruences; in our example we want ø to not be a perfect sq¿are. Other possibilities include restricting c to prime values, values for which 12 - N is a perfect square' or just about any other mathematical condition. The process of searching for values of ø satisfying such additional restrictions is called filtering an¿ is consiclered a problem apart from the GSp itself. We call this a sieve problem because each successive modul u.s as acting like an ordinary kitchen sieve with an increasingly finer mesh, thereby further restricting the possible solutions to the problem. Notice that the Eratosthenes for finding primes is an instance of the GSp. (i= 1,2,3,...,k). well known sieve of In this case, if we have B : p? + r where p¿ is the kth prime, we see that the problem between á and B is that of solving the GSp for m; rmi can be regarclecl of finding all the primes - p; and R; : {1,2,J,...,p;_ I} Patterson [Pat9lb] has shown that, when translated into a decision problem, the GSp is NP-complete and is therefore likely to be a very clifficult problem there is no efficient method known for solving the GSp. The in general. Certainly, best methocls that are CHAPTER 1. INTRODUCTION currently available involve the construction of mechanisms which automate the process of searching for solutions. In order to see how such a device might be constructecl, we will now discuss some of the principles of sieve automation. For further this we refer the reader to [patglb] and to stephens and williams information on [swgO]. L.2 Frinciples of Sieve Automation Consider the problem mentioned at the beginning of this section and observe the tableau below. x012345671009 modS x ./ x x x x x x modS x ,/ x x ,/ x x ,/ modS x I x x ./ x ,/ x modT x ./ ./ x I x x x ./ I ./ ,/ For each of the moduli 8, 3, 5, 7 we have put a check mark (/) residues and a cross (x) under the others. When we find a value of X for which there is a column consisting only of check marks, this value of X represents to the problem. In this example, the solution candidat e X is a perfect square, and it is not until X : uncler the acceptaSle a solution candidate = 1 is rejectecl beca'se it 1009 that we find a valicl solution. The difficulty with this approach is that we may have to go a very long way before we finrl a solution, particularly if we have many moduü. We can solve this problem by noting that each row of the tableau exhibits a cyclic pattern corresponding to the list of acceptaSle and non-acceptable residue classes for its associated modulus, information that can be compressed by the expedient of recorrling the results for each modulus only once. Any column of the original table can be generated by shifting each of the rows to the left in order to advance the appropriate set of residues to the frrst column, the leftmost resid'e wrapping around to the rightmost encl. In general, then, column ú can be obtaine¿ bv performing ú of these shift operations. CHAPTER 1, INTB"ODUCTION To see how a machine that performs this sieving operation can be fabricate¿, we note that each modulus rn; can be represented by a loop or ring which is clivided into r¿t positions. Those positions that represent acceptable residues are tagged. in some mannel to differentiate them from non-acceptable residues, and the one position from each ring at a fixed location calied a wind,ow or advanced in unison and a solution is detected when the window machine examines tap. The rings are is filled exclusively with tags identifying the residues as being acceptable for all the rings ofinterest. records the number of shifts performed by the machine. Thus, the A trial cottnter machine can be set up to start searching from some point trl by setting the ith ring such that /rr (mocl rn;) is in the window when the mechanism is turned on; after s shifts the value being teste¿ 1ù + s. A device of this type is called a number sieue or,, frequently, is i..st a sieue. 1-.3 Some Terms and Measures Before we can continue in our discussion of sieve clevices, it is important to ¿efine some terms and measures which will aid our discussion. 1.3.1 Basic Components of a Sieve Device Inherent in the design of all sieve devices are three basic components: the uector generator (CVG)' a solution detector, and a trial counter. character.,istic The CVG correspon¿s to the rings discussed above. The purpose of the CVG is to generate the patterns residues corresponding to our sieve problem. Solution taps route residue information from the CVG to a solution detection mechanism. In most digital logic implementations, solution detector is a wide AND-gate having one input per ring. To prevent value from being out of synchronization with the residue information, rings is kept in lock-step with incrementing of the trial counrer. of the the countel. the shifting of the CHAPTER 1. INTRODUCTION 1.3.2 Measuring Sieve performance To avoid confusion, we shall define two measures for describing the speed of a sieve device: Definition 1.3.1 We define úåe canvass rate of a sieue problem to be the numlter of ualues of æ included wíthin a specifi,ed sieuing range, A L x < B, diuided by the number of seconds required to sieue that range. Because sieving problems can be subject to various optimizations ancl transformations which we will discuss later, we also define a measure of the raw sieving rate of the underlying sieve hardware in order to make valid comparisons between vario¡s clevices. Definition 1'3'2 We define úåe maximum hardware sieving rate to t¡e tl¿e muxirnurn number of ualues tested per second by the solution detection mechanism. This ualue is giaen in terms o/trials per second. I-.3.3 Density of Sieve Problems Clearly, the ratio of acceptable to non-acceptable residues will have an effect on the solution rate of a given sieve problem. Often, it is useful to clefine some measure of the density of a sieve problem, and for this it is useful to compare the density of a given problem to that of a quadratic sieve. Although we shall not discuss quaclratic sieves lntil chapter 6, it suffices to say that the mrmber of acceptable residues per moclulus quadratic sieve problem is 1 for modul's 8, and (n; of a - t¡¡z for the odcl primes p¿ { p*, where p¡ is the largest modulus specifiecl by our sieve problem. From this it is verv easv to see that the density of solutions for quadratic sieves is thP'-t 8!J 2 Lehmer [Leh53, p' 8] and Cantor et al. [CEFT62, p. 151] have usecl the quariratic sieve as a benchmark when discussing the solution density of sieving problems, identifying CHAPTER 1. INTRODT]CTION problems as being "less than quadratic" or "more than quadratic,,. For our purposes we shall consider the quadratic sieve to be a moderøúe density sieve problem. We shall call the extreme of one residue per modulus, equivalent to a Chinese Remainder Theorem (CRT) type of problem, a sparse sieve problem. At the othe¡ extreme, when all but one residue per modulus is acceptable, as is the case with the sieve of Eratosthenes, a problem shall be considered a dense sieving problem. In between these extremes we define ,,moderate to low density" sieves and "moderate to high density', sieves. 1.3.4 The Filter Mechanism When filtering is required, a very high solution rate may overwhelm the resources available for filtering and cause a sieve problem tobe filter bound,. When a problem is filter bo.nd, the sieve will operate at a much lower speed than the maximum hardware sieving rate, as the process of filtering, or merely outputting solutions, becomes a bottleneck. Commonly, there are two different types of filtering mechanisms employecl systems' Wilh on-line filtering, frltering is performed almost immediately eration of a solution candidate by using a computer connectecl directly by sieve after the gen- to the sieve. This is in contrast to off-line filtering, where the solution candiclates are collecte¿ and at some later time transferred to a computer system for processing. in a batch, Clearly, before the advent of digital computers, all solution filtering was performed off-line, using manual methods such as hand-computation. Often' even when on-line solution filtering is provided, some off-line post-processing the data may be required' For example, it may be necessary to perform primality of solutions' a process generally too time consuming to be performed on-line. fast probable-prime test can be performed on-Iine, with the much slower being performed off-üne. of testing Instead, a primality test CHAPTER 1. INTRODT]CTION L.4 ûptimizations The performance of this basic modei can be improved further by testing for solutions in parallel. We can improve the sieving rate by a factor of ú by using ú sieves, starting each at a different point in the range to be sieved, or by constructing a single sieve with a Ú position solution window. Using an idea which originated from the work of Cantor et al. [CEFT62], it is possible to test ú solution taps at once. This winclow woul<l test I consecutive positions from each ring instead of just one and then the sieve wo¿¡I advance the rings by f positions. However, in order to support ú solution taps, a ring must accommodate more than I positions, hence many such rlesigns support very small moduli with rings corresponding to prime powers (see [patg1b, pp. 112-114]). 1.4.L Single Residue Optimization We can often increase the sieving rate even more by making use of the iclea of single residue optimization. Possibly, the best way to illustrate this iclea is to look once again at the example at the beginning of this section. Notice that if we combine the mo<luli which have only a single acceptable residue, we need to find a value for X such that X : I (mod 2a). Since X - 1 + 24Y, instead of sieving on X, we coukl sieve on y. In this case all residues modulo 8 and 3 are acceptable for Y and we simply rearrange our remaining residues modulo 5 and 7 so that Y : 0or2(mod5), Y : 0,1 or 5 (mod 7). This simple idea, known to Lehmer (see [Leh53]), effects a 24 fo\d, speeclup for the problems because any solution Y can easily be converted to one for X by complting X : I + 24Y and the sieving range has been reduced by a factor of L124. An algorithm to perform the required residue reordering for single residue optimization will 6e presented in Section 4.4.3. CHAPTER 1. INTRODUCTION I.4.2 Multiple Residue Optimization The idea of single residue optimization can be applied to multiple residues to obtain an additional increase in the sieving rate. This idea was used by Lehmer [Leh28, p. 8g1] to divide a factoring problem into two separate sieve problems based on the congruerce ø : 2,3 (mod 5). BV separating results into two cases and using single residue optimization on both subproblems, a speedup factor of 512 was achieved over that of a single run. In 1975, Stark [Sta75, p. 301] used this method to divide a quadratic type problem into 30 subproblems with respect to the implicit modulus mr : 8 . 3. 5 . T . LI = 9240. Using single residue optimization modulo 9240, each subproblem achieves a speedup of 9240130 over a non-optimized problem, not including any additional costs incurrecl in running multiple subproblems over that of a single problem. 1-.5 F'actoring using Sieves One of the earliest applications of sieve devices was in the factoring of integers. In fact, it was the interest in factoring which spurred much of the early development of sieve devices. Although modern factoring algorithms programmed on present-day computers have made factoring by sieving obsolete, up until about 1970, sieving wâ.s the fastest general method available for factoring large integers [SW90, p. 43]. In orcler that the reader is not left with the impression that sieves are only of historical interest, we shall be presenting examples of contemporary sieve applications in Chapters 6 and 7 of this thesis. The factoring algorithm we shall describe is based on an idea which began with Fermat in 1643 [Dic66] who suggested that if one can frnd a representation for a number y'{ as a difference of squares, *2 - g',then one can easily rletermine two factors of trf. Assuming N : U.I/, where U ) V, ar'd, U, V are both odd, then we can define 11 *:õ(U+V), u:;(U-V), þ4 CHAPTER 1. INTRODT]CTION and see that U=(x*A), V=(r-y), and 1[:(ø+y)(n-y):*'-y2. Stated as a sieving problem, we must find a value ø such that x2 - N is a perfect sqrlare. It is a fairly straightforward matter to specify the necessary congruence relations. For example, in 1938 Lehmer [Leh39, p. 137] used a mechanical sieve to factor the integer /y'1, where ,i' _: (zt'o + r) (zt + t) = 18518800563e24r07527. þ2*¡ffi fn fact, an examination of Lehmer's unpublished sieve log shows that he employed a goocl deal of mathematical ingenuity to restrict