[racket] slow g^x=h mod p meet in the middle code

2014-02-27 15:23 GMT+01:00 Cristian Baboi <cristian.baboi at gmail.com>:
> Hello,
>
> I recently used racket for a math assignment in a crypto class because of
> big numbers support. Others used python, java, haskell and bragged with
> short execution times. Is there anything I can do to speed up the following
> code or is my computer too old ?

First make sure you use the same algorithm. Post it!

Second:  (modulo (* l gm1) p) looks inefficient.
              If l and gm1 are large, then it is more efficient
              to reduce modulo p first, then multiply, then reduce again.

Since all your calculations are modulo p, you can use with-modulus and mod*.

Third: When benchmarking turn off display and use racket (not DrRacket).

Fourth: Use Racket hash tables rather than rnrs ones. (I haven't looked, so
I am unsure how they are implemented - maybe they are slower - maybe they
are the ok)/

Without changing the algorithm, I get this:

#lang racket
(require math)
(require rnrs/hashtables-6)
(define p 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
(define g 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
(define h 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)
(define B (expt 2 20))

(with-modulus p
  (define gB  (modexpt g B))
  (define gm1 (modular-inverse g p))
  (define (mx x0 x1) (+ (* B x0) x1))

  (define (hash n ht l x1)
    (cond
      [(> n 0)  (hashtable-set! ht l x1)
                (when (< x1 10) (displayln (list x1 l)))
                (hash (- n 1) ht  (mod* l gm1) (+ x1 1))]
      [else     (hashtable-set! ht l x1)
                ht]))

  (define (htbl) (hash (- B 1) (make-eqv-hashtable B) h 0))
  (define (gol)  (make-eqv-hashtable B))

  (define (caut n ht l x0)
    (cond
      [(> n 0) (define x1 (hashtable-ref ht l -1))
               (when (< x0 10) (displayln (list x0 l)))
               (if (eqv? x1 -1)
                   (caut (- n 1) ht  (mod* l gB) (+ x0 1))
                   (cons x0 x1))]
      [else (define x1 (hashtable-ref ht l -1))
            (if (eqv? x1 -1)
                (cons -1 -1)
                (cons x0 x1))]))

  (define run (caut (- B 1) (htbl) 1 0))
  (define x (mx (car run) (cdr run)))
  (displayln x))



>
> #lang racket
> (require math)
> (require rnrs/hashtables-6)
> (define p
> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
> (define g
> 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
> (define h
> 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)
> (define B (expt 2 20))
>
>
> (define gB (modular-expt g B p))
> (define gm1 (modular-inverse g p))
>
> (define (mx x0 x1) (+ (* B x0) x1))
> (define (hash n ht l x1)(cond ((> n 0)
>                             (begin (hashtable-set! ht l x1)
>                                    (if (< x1 10) (displayln (list x1 l)) 0)
>                                    (hash (- n 1) ht  (modulo (* l gm1) p) (+
> x1 1)) ))
>                          (else (begin
>                                  (hashtable-set! ht l x1)
>                                   ht
>                                )))
> )
> (define (htbl) (hash (- B 1) (make-eqv-hashtable B) h 0))
> (define (gol) (make-eqv-hashtable B) )
>
> (define (caut n ht l x0)(cond ((> n 0)
>                             (let ((x1 (hashtable-ref ht l -1)))
>                               (begin (if (< x0 10) (displayln (list x0 l))
> 0)
>                               (cond ((eqv? x1 -1) (caut (- n 1) ht  (modulo
> (* l gB) p) (+ x0 1)))
>                                      (else (cons x0 x1) )
>                                     ))))
>                          (else (let ((x1 (hashtable-ref ht l -1)))
>                                   (cond ((eqv? x1 -1) (cons -1 -1))
>                                         (else (cons x0 x1)))
>                                )))
> )
>
> (define run (caut (- B 1) (htbl) 1 0))
> (define x (mx (car run) (cdr run)))
> (displayln x)
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>



-- 
--
Jens Axel Søgaard