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!