This section describes two methods for checking the primality of an
integer `n`, one with order of growth Θ(√`n`), and a
“probabilistic” algorithm with order of growth Θ(`log`

`n`). The exercises at the end of this section suggest programming
projects based on these algorithms.

### Searching for divisors

Since ancient times, mathematicians have been fascinated by problems
concerning prime numbers, and many people have worked on the problem
of determining ways to test if numbers are prime. One way
to test if a number is prime is to find the number’s divisors. The
following program finds the smallest integral divisor (greater than 1)
of a given number `n`. It does this in a straightforward way, by
testing `n` for divisibility by successive integers starting with 2.

```
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
```

We can test whether a number is prime as follows: `n` is prime if
and only if `n` is its own smallest divisor.

```
(define (prime? n)
(= n (smallest-divisor n)))
```

The end test for `find-divisor`

is based on the fact that if `n`
is not prime it must have a divisor less than or equal to
√`n`.[44] This
means that the algorithm need only test divisors between 1 and
√`n`. Consequently, the number of steps required to identify
`n` as prime will have order of growth Θ(√`n`).

### The Fermat test

The Θ(`log`

`n`) primality test is based on a result from number theory known as Fermat’s Little Theorem.[45]

#### Fermat’s Little Theorem:

If `n` is a prime number and `a` is any positive integer less than `n`, then `a` raised to the
`n`th power is congruent to `a` modulo `n`.

(Two numbers are said to be congruent modulo `n` if
they both have the same remainder when divided by `n`. The
remainder of a number `a` when divided by `n` is also referred to as
the remainder of `a` modulo `n`, or simply as `a` modulo `n`.)

If `n` is not prime, then, in general, most of the numbers `a`< `n` will not satisfy the above relation. This leads to the following algorithm for
testing primality: Given a number `n`, pick a random number `a` < `n` and
compute the remainder of `a`^{n} modulo `n`. If the result is not equal to `a`, then `n` is certainly not prime. If it is `a`, then chances are good
that `n` is prime. Now pick another random number `a` and test it with the
same method. If it also satisfies the equation, then we can be even more
confident that `n` is prime. By trying more and more values of `a`, we can
increase our confidence in the result. This algorithm is known as the
Fermat test.

To implement the Fermat test, we need a procedure that computes the exponential of a number modulo another number:

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```

This is very similar to the `fast-expt`

procedure of
section 1.2.4. It uses successive squaring, so
that the number of steps grows logarithmically with the
exponent.[46]

The Fermat test is performed by choosing at random a number `a`
between 1 and `n` - 1 inclusive and checking whether the remainder
modulo `n` of the `n`th power of `a` is equal to `a`. The random number `a` is chosen using the procedure `random`

, which we assume is
included as a primitive in Scheme. `Random`

returns a
nonnegative integer less than its integer input. Hence, to obtain a random
number between 1 and `n` - 1, we call `random`

with an input of `n` - 1 and add 1 to the result:

```
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
```

The following procedure runs the test a given number of times, as specified by a parameter. Its value is true if the test succeeds every time, and false otherwise.

```
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
```

### Probabilistic methods

The Fermat test differs in character from most familiar algorithms, in
which one computes an answer that is guaranteed to be correct. Here,
the answer obtained is only probably correct. More precisely, if `n`
ever fails the Fermat test, we can be certain that `n` is not prime.
But the fact that `n` passes the test, while an extremely strong
indication, is still not a guarantee that `n` is prime. What we would
like to say is that for any number `n`, if we perform the test enough
times and find that `n` always passes the test, then the probability
of error in our primality test can be made as small as we like.

Unfortunately, this assertion is not quite correct. There do exist
numbers that fool the Fermat test: numbers `n` that are not prime and
yet have the property that `a`^{n} is congruent to `a` modulo `n` for all integers `a` < `n`. Such numbers are extremely rare, so the Fermat
test is quite reliable in practice.[47] There are variations of the Fermat test that cannot be fooled. In
these tests, as with the Fermat method, one tests the primality of an
integer `n` by choosing a random integer `a`<`n` and checking some
condition that depends upon `n` and `a`. (See
exercise 1.28 for an example of such a test.) On the
other hand, in contrast to the Fermat test, one can prove that, for
any `n`, the condition does not hold for most of the integers `a` < `n` unless `n` is prime. Thus, if `n` passes the test for some random
choice of `a`, the chances are better than even that `n` is prime. If `n` passes the test for two random choices of `a`, the chances are better
than 3 out of 4 that `n` is prime. By running the test with more and
more randomly chosen values of `a` we can make the probability of
error as small as we like.

The existence of tests for which one can prove that the chance of error becomes arbitrarily small has sparked interest in algorithms of this type, which have come to be known as probabilistic algorithms. There is a great deal of research activity in this area, and probabilistic algorithms have been fruitfully applied to many fields.[48]

`e`is greater than 1 are based on the fact that, for any integers

`x`,

`y`, and

`m`, we can find the remainder of

`x`times

`y`modulo

`m`by computing separately the remainders of

`x`modulo

`m`and

`y`modulo

`m`, multiplying these, and then taking the remainder of the result modulo

`m`. For instance, in the case where

`e`is even, we compute the remainder of

`b`

^{e/2}modulo

`m`, square this, and take the remainder modulo

`m`. This technique is useful because it means we can perform our computation without ever having to deal with numbers much larger than

`m`. (Compare exercise 1.25.) [back]

Exercises

## Exercise 1.21

Use the `smallest-divisor`

procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

## Exercise 1.22

Most Lisp implementations include a primitive called `runtime`

that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The
following `timed-prime-test`

procedure, when called with an
integer `n`, prints `n` and checks to see if `n` is prime. If `n` is
prime, the procedure prints three asterisks followed by the amount of time
used in performing the test.

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```

Using this procedure, write a procedure `search-for-primes` that
checks the primality of consecutive odd integers in a specified range.
Use your procedure to find the three smallest primes larger than 1000;
larger than 10,000; larger than 100,000; larger than 1,000,000. Note
the time needed to test each prime. Since the testing algorithm has
order of growth of Θ(√`n`), you should expect that testing
for primes around 10,000 should take about √10 times as long
as testing for primes around 1000. Do your timing data bear this out?
How well do the data for 100,000 and 1,000,000 support the √`n`
prediction? Is your result compatible with the notion that programs
on your machine run in time proportional to the number of steps
required for the computation?

## Exercise 1.23

The `smallest-divisor`

procedure shown at the start of this section does lots of needless testing: After it checks to see if the
number is divisible by 2 there is no point in checking to see if
it is divisible by any larger even numbers. This suggests that the
values used for `test-divisor`

should not be 2, 3, 4, 5, 6,
…, but rather 2, 3, 5, 7, 9, …. To implement this
change, define a procedure `next`

that returns 3 if its input is
equal to 2 and otherwise returns its input plus 2. Modify the `smallest-divisor`

procedure to use `(next test-divisor)`

instead
of `(+ test-divisor 1)`

. With `timed-prime-test`

incorporating this modified version of `smallest-divisor`

, run the test for each of the 12 primes found in
exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast.
Is this expectation confirmed? If not, what is the observed ratio of
the speeds of the two algorithms, and how do you explain the fact that
it is different from 2?

## Exercise 1.24

Modify the `timed-prime-test`

procedure of
exercise 1.22 to use `fast-prime?`

(the
Fermat method), and test each of the 12 primes you found in that
exercise. Since the Fermat test has Θ(`log`

`n`) growth, how
would you expect the time to test primes near 1,000,000 to compare
with the time needed to test primes near 1000? Do your data bear this
out? Can you explain any discrepancy you find?

## Exercise 1.25

Alyssa P. Hacker complains that we went to a lot of extra work in
writing `expmod`

. After all, she says, since we already know how to compute exponentials, we could have simply written

```
(define (expmod base exp m)
(remainder (fast-expt base exp) m))
```

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

## Exercise 1.26

Louis Reasoner is having great difficulty doing
exercise 1.24. His `fast-prime?`

test
seems to run more slowly than his `prime?`

test. Louis calls his
friend Eva Lu Ator over to help. When they examine Louis’s code, they
find that he has rewritten the `expmod`

procedure to use an
explicit multiplication, rather than calling `square`

:

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```

“I don’t see what difference that could make,” says Louis. “I
do.” says Eva. “By writing the procedure like that, you have
transformed the Θ(`log`

`n`) process into a Θ(`n`) process.” Explain.

## Exercise 1.27

Demonstrate that the Carmichael numbers listed in footnote 47 really do fool
the Fermat test. That is, write a procedure that takes an integer `n`
and tests whether `a`^{n} is congruent to `a` modulo `n` for every
`a` < `n`, and try your procedure on the given Carmichael numbers.

## Exercise 1.28

One variant of the Fermat test that cannot be fooled is called the
Miller-Rabin test (Miller 1976; Rabin 1980). This starts from
an alternate form of Fermat’s Little Theorem, which states that if `n`
is a prime number and `a` is any positive integer less than `n`, then
`a` raised to the (`n` - 1)st power is congruent to 1 modulo `n`. To test
the primality of a number `n` by the Miller-Rabin test, we pick a
random number `a` < `n` and raise `a` to the (`n` - 1)st power modulo `n`
using the `expmod`

procedure. However, whenever we perform the
squaring step in `expmod`

, we check to see if we have discovered a
“nontrivial square root of 1 modulo `n`,” that is, a number not
equal to 1 or `n` - 1 whose square is equal to 1 modulo `n`. It is
possible to prove that if such a nontrivial square root of 1 exists,
then `n` is not prime. It is also possible to prove that if `n` is an
odd number that is not prime, then, for at least half the numbers
`a` < `n`, computing `a`^{n-1} in this way will reveal a nontrivial
square root of 1 modulo `n`. (This is why the Miller-Rabin test
cannot be fooled.) Modify the `expmod`

procedure to signal if it discovers a nontrivial square root of 1, and use this to implement
the Miller-Rabin test with a procedure analogous to `fermat-test`

. Check your procedure by testing various known primes and non-primes.
Hint: One convenient way to make `expmod`

signal is to have it return 0.

## Comments

## kIKiMDlJWjTtTZJYDs

I’m out of league here. Too much brain power on dsialpy!

## hermes replica bags

look at hermes replica for less VykpABZc http://replicahermesbags.medykblog.pl/

## hermes outlet

you love this? hermes outlet online at my estore wuzfDRnP http://hermesoutlet.urbanblog.dk/

## burberry touch

view burberry sunglasses ZAgGZkgH [URL=http://www.burberryoutlet-online2013.org/ - burberry shop online[/URL - and get big save CoAvGolH http://www.burberryoutlet-online2013.org/

## Knock off Oakleys

This is similar to the benefits being gained by running barefoot in semi-soft sand. And all on this makes one’s body healthier and stronger. People will base their decision to buy the shoe on consumer reviews and claims by the company. Pensate totalmente libero di andare al mio sito e l’indicazione-up per una Nessun costo di 35 Parte E-mail newsletter contenente un grande aiuto su tutte le caratteristiche del gioco!hogan outlet 脠 un singolo asse golf swing il modo migliore per colpire una palla? Alimentato dal successo del Moe Norman, che ha reso popolare il singolo asse approccio ed 猫 stata ampiamente riconosciuta per il potere, la coerenza e correttezza a impressione, infuria la discussione su. Ha pubblicato una idea identificata come “normali Golf” un sacco di decenni fa. Hogan era un tempo citato come dichiarando: “Moe 猫 l’unica persona che avrei attraversare la strada a guardare le palle colpite.” Hogan non era da solo.But soon after skiing or snowshoeing off the beginner route, the trail is long and difficult. Follow this path and the snow is usually consistent for skiing or snowshoeing. You may find snow waist deep in the higher elevations. What Shanty lacks in difficulty is more than made up for in its wonderful views and those soft-as-velvet sunsets over incomparable West Michigan hills. One of Michigan’s best cross country ski trails, Shanty Creek Resort Trails is located near Mancelona, MI. Trails’ printable online topo maps offer shaded and un-shaded reliefs, and aerial photos too! Use topographic map functionality to find elevation, print high resolution maps, save a PNG, or just learn the topography around Shanty Creek Resort Trails. Knock off Oakleys http://ircona.com/shop/fake-oakleys.html

## 1.2.6 Example: Testing for Primality | SICP in Clojure

This piece of writing offers clear idea in favor of the new visitors of blogging,

that in fact how to do running a blog.

my weblog … mooduu

## 1.2.6 Example: Testing for Primality | SICP in Clojure

But God’s Word could and our Creator loves online nursing school him. There were also some online nursing school non-nude photos that feature the woman with the same fake tattoos Lively wore for her role in” The Town” and a photo that shows the actress’s face.

Motivation and Emotion, 26, 57-81. Thus, a victim counselor under the rule

would be protected by the right of conscious

law, medical professionals in New York City. She is the principle of equal treatment under the

law.

Feel free to surf to my homepage - nursing schools in new york (Giuseppe)

## Authentic Mychal Kendricks Jersey

Yet again, sneakers that will in shape upon this specific categoryhave lessgroundfeel, a lesser amount of freedom and in addition moreweightdue for you to better bottoms along with moredurableuppers. Job to find out additional with regards to solar panel technology data, be sure to check out your author’ ersus site exceptional no cost article in solar power [url=http://www.chargersofficialteamshop.com/michael-harris-signed-jersey/ ]Michael Harris Jersey[/url] systems [url=http://www.chargersofficialteamshop.com/kendall-reyes-signed-jersey/ ]Kendall Reyes Womens Jersey[/url] pertaining to household employ, along with the easiest way a knowledgeable screen workers. These are generally people linked to installing of your acquired products. Make inquiries your building contractors prioritize and look after these people. Even though mastering, you’ll be able to train the idea on the yoga exercise mat along with develop essentially the most cozy along with powerful strategy.A terrific covering restoration builder might be identified by his or [url=http://www.chargersofficialteamshop.com/manti-teo-signed-jersey/ ]Manti Te’o Womens Jersey[/url] her reputations, certainly not by simply the amount that they harass anyone at your house along with organization.

## Post new comment