Prime_Numbers_A_Computational_Perspective-Crandall-Pomerance-2e.pdf

Prime Numbers

Richard Crandall Carl Pomerance

Prime Numbers

A Computational Perspective

Second Edition

Richard Crandall

Center for Advanced Computation

3754 SE Knight Street

Portland, OR 97202

USA

crandall@reed.edu

Carl Pomerance

Department of Mathematics

Dartmouth College

Hanover, NH 03755-3551

USA

carl.pomerance@dartmouth.edu

Cover illustration: The cover shows a magnified view—through a watchmaker’s loupe—of a very

small portion of an actual poster giving the 7.2 million decimal digits of the prime 2 24036583 -1 .Ifthe

entire one-meter tall poster were thus magnified, it would be the size of a baseball diamond.

Mathematics Subject Classification (2000): 11-00, 11A41

Library of Congress Control Number: 2005923504

ISBN-10: 0-387-25282-7

Printed on acid-free paper.

ISBN-13: 978-0387-25282-7

permission of the publisher (Springer Science+Business Media, Inc., 233 Spring Street, New York, NY

10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connec-

tion with any form of information storage and retrieval, electronic adaptation, computer software, or by

similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they

are not identified as such, is not to be taken as an expression of opinion as to whether or not they are

subject to proprietary rights.

Printed in the United States of America.

(MVY)

987654321

springeronline.com

We dedicate this work to our parents Janice, Harold, Hilda, Leon, who—in

unique and wonderful ways—taught their children how to think.