PrimesFinder using #atRandom

Has anyone tried

  ElGamalKeyGenerator new generateKeysOfSize: 2048

?

The ElGamal tests pass because they use but a 15-bit
key!  Does anyone mind if I beef up this test and
possibly others?

I can post notice of my commit here when I'm done and
then someone else can review it if they want?  The
tests will not pass unless we fix the issue itself.

The issue itself appears to be caused by use of the
Float-based "Random" generator.  I haven't yet tried
replacing it with SecureRandom, but I will try that
soon.

_______________________________________________
Cryptography mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/cryptography

It seems that the problem lies at the bottom of
PrimesFinder>>#iterate, when making extensive user of LargeInteger
primitives. Perhaps there's a more efficient way to implement this
method. Here's a MessageTally on:[PrmesFinder primeOfSize: 250]

 - 30670 tallies, 30747 msec.

**Tree**
100.0% {30747ms} PrimesFinder class>>primeOfSize:
  99.6% {30624ms} PrimesFinder>>nextPrime
    99.5% {30593ms} PrimesFinder>>satisfied
      99.5% {30593ms} MillerRabin class>>isProbablyPrime:
        99.5% {30593ms} MillerRabin>>iterate
          98.0% {30132ms} LargePositiveInteger(Integer)>>raisedTo:modulo:
            65.6% {20170ms} LargePositiveInteger>>\\\
              |65.5% {20139ms} LargePositiveInteger(Integer)>>digitDiv:neg:
              |  61.5% {18909ms} primitives
              |  2.8% {861ms} LargePositiveInteger(Integer)>>digitLshift:
              |    2.5% {769ms} primitives
            31.7% {9747ms} LargePositiveInteger>>*
              31.7% {9747ms} LargePositiveInteger(Integer)>>*
                31.7% {9747ms} LargePositiveInteger(Integer)>>digitMultiply:neg:
                  31.5% {9685ms} primitives

**Leaves**
62.2% {19125ms} LargePositiveInteger(Integer)>>digitDiv:neg:
32.1% {9870ms} LargePositiveInteger(Integer)>>digitMultiply:neg:
2.6% {799ms} LargePositiveInteger(Integer)>>digitLshift:

**Memory**
        old +0 bytes
        young +124,532 bytes
        used +124,532 bytes
        free -124,532 bytes

**GCs**
        full 0 totalling 0ms (0.0% uptime)
        incr 389 totalling 152ms (0.0% uptime), avg 0.0ms
        tenures 0
        root table 0 overflows



On 2/13/06, Chris Muller <[hidden email]> wrote: _______________________________________________
Cryptography mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/cryptography

Regarding the tests, I'd rather keep them fast, so we can run lots of
them very often (after every change we make). If we have a test case
that never finishes, it'll keep us from running the rest of the test
suit. If we want to test for speed and make sure Squeak will generate
2048-bits keys in a reasonable amount of time, pehaps we should make a
test like this:

self assert: [(Time millisecondsToRun:[ElGamalKeyGenerator new
generateKeysOfSize: 128]) < 100]

or something similar, i.e making sure a small key is generated in a
very very short time. Does this make sense? What do you think?

Luciano

On 2/13/06, Chris Muller <[hidden email]> wrote: _______________________________________________
Cryptography mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/cryptography