(Copying to the Crypto list, should we move discussion over there altogether?)
Random Fortuna is a random-stream-of-bytes generator, no Floats are
involved to overflow. However, I do see, now, why I tried to override
nextInt: in Fortuna: performance.
The inherited implementation from SecureRandom:
"Answer a random integer in the interval [1, anInteger]."
| r high |
anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive' ].
high := anInteger-1.
[ (r := self nextBits: anInteger highBit)
and: high ] whileFalse.
So it may have do a little churning before it arrives at something
in-range. Surely there is a less-wasteful way to do it. Fortuna
tried, but failed.
How can a random-stream-of-bytes generator be used for a faster #nextInt:?
BTW, it looks like the #nextInt: implementation in SecureRandom is an
exact duplicate of its superclass impl.. probably can be removed.
On Tue, Jul 6, 2010 at 11:05 AM, Gary Chambers
> Having dealt with rather large encryption keys (2048 bit) here's the fix
> we've had for Random>>nextInt:
> nextInt: anInteger
> "Answer a random integer in the interval [1, anInteger].
> Handle large numbers too (for cryptography)."
> anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive'
> anInteger asFloat isInfinite
> ifTrue: [^(self next asFraction * anInteger) truncated + 1].
> ^ (self next * anInteger) truncated + 1
> Regards, Gary
> ----- Original Message ----- From: "Chris Muller" <asqueaker(a)gmail.com>
> To: "The general-purpose Squeak developers list"
> Cc: "Squeak Cryptography" <cryptography(a)lists.squeakfoundation.org>
> Sent: Tuesday, July 06, 2010 4:52 PM
> Subject: Re: [squeak-dev] Cryptography: Fortuna>>nextInt:
> Hi David, yes, absolutely, Fortuna>>#nextInt: should be deleted,
> because it is a flawed implementation, as the following script
> "explore it"
> f:=Fortuna picker.
> ((1 to: 1000) collect: [ : n | f nextInt: 6 ]) asBag sortedCounts
> Note the consistent, heavy weighting for "1"..
> The method should be deleted so it can inherit the generic one in the
> Thanks and Regards,
> On Mon, Jul 5, 2010 at 2:58 PM, C. David Shaffer <cdshaffer(a)acm.org> wrote:
>> I missed a method in my merge of Chris' branch:
>> Fortuna>>nextInt: was removed by cmm.7 with the comment:
>> "Removed faulty optimization of Fortuna>>#nextInt:. Now inherits slower
>> but correct one from superclass."
>> Chris: It looks like the original version has persistent (with
>> underscores fixed) in the latest version. Can you confirm that I should
>> remove the version below?
>> Feedback from others?
>> Fortuna>>nextInt: anInteger
>> "Answer a random integer in the interval [1, anInteger]."
>> | r high bits highestMultiple |
>> anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive'
>> high := anInteger-1.
>> bits := high highBit.
>> "Calculate highestMultiple of anInteger, so that we can simply divide r by
>> anInteger and use the remainder for the random value."
>> highestMultiple := (1 bitShift: bits) truncateTo: anInteger.
>> [ (r := self nextBits: bits)
>> between: 0
>> and: highestMultiple ] whileFalse.
>> ^ r\\anInteger+1