Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.653.mcz

==================== Summary ====================

Name: Kernel-nice.653
Author: nice
Time: 15 November 2011, 11:23:38.908 pm
UUID: d149a4f7-f537-4f76-9b79-367acd0aa832
Ancestors: Kernel-laza.649

Minor refactoring of isProbablyPrime
- Add more comments (tell it's a Miller Rabin test, tells about probabilities)
- avoid repeated shift when #lowBit can help doing it once
- refactor Knuth "P3" test to a simpler expression
- and restore the fact that there is a step "P4" before "P5"

=============== Diff against Kernel-laza.649 ===============

Item was changed:
  ----- Method: Integer>>isProbablyPrime (in category 'testing') -----
  isProbablyPrime
  	"See isProbablyPrimeWithK:andQ: for the algoritm description."
  	
  	| k q |
  	self <= 1 ifTrue: [ ^false ].
  	self even ifTrue: [ ^self = 2 ].
+ 	"Factor self into (2 raisedTo: k) * q + 1, where q odd"
+ 	q := self bitShift: -1.
+ 	k := q lowBit.
+ 	q := q bitShift: 1 - k.
+ 	"Repeat the probabilistic until false (the probability of false negative is null) or until probability is very low."
- 	k := 1.
- 	q := self - 1 bitShift: -1.
- 	[ q odd ] whileFalse: [
- 		q := q bitShift: -1.
- 		k := k + 1 ].
  	25 timesRepeat: [ (self isProbablyPrimeWithK: k andQ: q) ifFalse: [ ^false ] ].
+ 	"The probability of false positive after 25 iterations is less than (1/4 raisedTo: 25) < 1.0e-15"
  	^true!

Item was changed:
  ----- Method: Integer>>isProbablyPrimeWithK:andQ: (in category 'private') -----
  isProbablyPrimeWithK: k andQ: q 
  	"Algorithm P, probabilistic primality test, from
  	Knuth, Donald E. 'The Art of Computer Programming', Vol 2,
+ 	Third Edition, section 4.5.4, page 395, P1-P5 refer to Knuth description..
+ 	Note that this is a Miller Rabin test which may answer false positives (known as pseudoprimes) for at most 1/4 of the possible bases x."
- 	Third Edition, section 4.5.4, page 395, P1-P5 refer to Knuth description."
  
+ 	| x j y minusOne |
  	"P1"
- 
- 	| x j y |
  	x := (self - 2) atRandom + 1.
  	"P2"
  	j := 0.
  	y := x raisedTo: q modulo: self.
+ 	minusOne := self - 1.
- 	"P3"
  	
+ 	["P3"
+ 	y = 1 ifTrue: [^j = 0].
+ 	y = minusOne ifTrue: [^true].
+ 	"P4"
+ 	(j := j + 1) < k]
+ 		whileTrue:
+ 			[y := y squared \\ self].
- 	[((j = 0 and: [y = 1]) or: [y = (self - 1)]) ifTrue: [^true].
- 	(j > 0 and: [y = 1]) ifTrue: [^false].
  	"P5"
+ 	^false!
- 	j := j + 1.
- 	j < k
- 		ifTrue: [y := y squared \\ self]
- 		ifFalse:[^ false]] repeat!