Re:
>I stumbled across the arithmetic stuff in the DigitalSignatureAlgorithm
>class and had a little trouble understanding isProbablyPrime's answer to
>small primes. (I wouldn't call this a bug exactly, since small primes
>probably won't be used there <g>. Alas, the fix was useful elsewhere.)
>
>The respective excerpt reads (vanilla 2.7 image):
>
>	factor _ SmallPrimes detect: [:f | (p \\ f) = 0] ifNone: [nil].
>	factor ifNotNil: [^ false].
>
>Buf if p *is* a small prime, this will answer false.
>
>Suggestion:
>
>	factor _ SmallPrimes detect: [:f | (p \\ f) = 0] ifNone: [nil].
>	factor ifNotNil: [^ p = factor].
>
>Small changeset attached.

Good idea. Thanks! And you're right, in the context for which it was written,
this method was testing 160 to 512 bit numbers for probable primness, so
there was virtually no chance of encountering a number < 2000. But it's
better to be correct in all cases.

Note that for a smallish integer N, testing all odd numbers up
to N sqrt to see if they divide N doesn't take long and gives an
exact answer about N's primality. You really only need a
probabilistic primality test when you start getting numbers
with over 40 or 50 bits.

You may also be interested in the method "primesUpTo: N", which
uses the sieve algorithm to winnow out all the non-primes. Handy
for quickly computing the first 10,000 or so primes.


Re:
>P.S. We could move DSA's large int arithmetic stuff to Integer and
>LargePositiveInteger, no?

Andrew Greenberg has done just that, while Stephan Rudlof has
been working on a complete set of large integer primitives. One
way or another, we'll get much faster large integer arithmetic!

	-- John