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

From: Cristian Baboi (cristian.baboi at gmail.com)
Date: Thu Feb 27 09:23:04 EST 2014


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 ?

The code solves g^x=h mod p with a meet in the middle approach.

#lang racket
(require math)
(require rnrs/hashtables-6)
(define p  
(define g  
(define h  
(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)
(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))  
                               (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)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: logaritm.rkt
Type: application/octet-stream
Size: 1925 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20140227/460deb7a/attachment.obj>

Posted on the users mailing list.