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 ?
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 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)
logaritm.rkt
Description: Binary data
____________________ Racket Users list: http://lists.racket-lang.org/users
