On Sat, 23 Jan 2010, commits at source.squeak.org wrote:

> David T. Lewis uploaded a new version of Kernel to project The Trunk:
> http://source.squeak.org/trunk/Kernel-dtl.381.mcz
>
> ==================== Summary ====================
>
> Name: Kernel-dtl.381
> Author: dtl
> Time: 23 January 2010, 2:56:10.622 pm
> UUID: 70c5d3fd-a468-4289-b9b5-101cdaea72b8
> Ancestors: Kernel-nice.380
>
> Use probabilistic algorithm (Knuth) for testing primality of large integers, and add method comments for explanation.

The algorithm is a Miller-Rabin primality test with 25 as the accuracy 
parameter. This means that the chance for a false positive is less than 4 
raisedTo: -25. DSA uses the same algorithm, but requires the parameter to 
be at least 50 IIRC, you can find the other implementation at: 
DigitalSignatureAlgorithm >> #isProbablyPrime:.

I was digging into the code and tried possible improvements, but got stuck 
at a point. I found that there are two methods for the same problem:
#raisedTo:modulo: and #raisedToInteger:modulo:. They do the same, but the 
latter is a lot slower, because the first one uses #\\\ instead of #\\ 
which uses #digitDiv:neg: (a division primitive).
I found that #digitDiv:neg: works with any Integer, while primitive 
31 (used by #\\) only works if the argument and the result are both less 
than 2 raisedTo: 30, otherwise it will fall back to Smalltalk code which 
happens most of the time in these primality tests.

For a final solution we should decide what to do.
- what should we do with #raisedTo:modulo: and #raisedToInteger:modulo: ?
- should (can) we replace the implementation of LargePositiveInteger >> 
#\\ (and #//) with #digitDiv:neg: + #normalize or something similar?


Levente

>
> Rationale for use of probabilistic algorithm provided by Enrico Spinielli:
>  http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-December/142372.html
>
> =============== Diff against Kernel-nice.380 ===============
>
> Item was changed:
>  ----- Method: Integer>>isPrime (in category 'testing') -----
>  isPrime
> + 	"Answer true if the receiver is a prime number. See isProbablyPrime for a probabilistic
> + 	implementation that is much faster for large integers, and that is correct to an extremely
> + 	high statistical level of confidence (effectively deterministic)."
>
>  	self <= 1 ifTrue: [ ^false ].
>  	self even ifTrue: [ ^self = 2].
>  	3 to: self sqrtFloor by: 2 do: [ :each |
>  		self \\ each = 0 ifTrue: [ ^false ] ].
>  	^true!
>
> Item was added:
> + ----- Method: LargePositiveInteger>>isPrime (in category 'testing') -----
> + isPrime
> + 	"Answer true if the receiver is a prime number. Use a probabilistic implementation	 that
> + 	is much faster for large integers, and that is correct to an extremely high statistical
> + 	level of confidence (effectively deterministic)."
> +
> + 	^ self isProbablyPrime!
>
>
>