(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:
nextInt: anInteger "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) between: 0 and: high ] whileFalse. ^ r+1
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.
- Chris
On Tue, Jul 6, 2010 at 11:05 AM, Gary Chambers gazzaguru2@btinternet.com wrote:
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@gmail.com To: "The general-purpose Squeak developers list" squeak-dev@lists.squeakfoundation.org Cc: "Squeak Cryptography" cryptography@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 demonstrates:
"explore it" |f| 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 superclass.
Thanks and Regards, Chris
On Mon, Jul 5, 2010 at 2:58 PM, C. David Shaffer cdshaffer@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?
Thanks!
David
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
cryptography@lists.squeakfoundation.org