## Tonelli-Shanks Algorithm

### November 23, 2012

Here is our version of the function:

`(define (tonelli a p)`

(define (expp b e) (expm b e p))

(define (modp n) (modulo n p))

(let* ((p-1 (- p 1)) (p-1/2 (/ p-1 2)))

(if (even? p) (error 'tonelli "must be odd"))

(if (not (prime? p)) (error 'tonelli "must be prime"))

(if (< p 3) (error 'tonelli "must be greater than two"))

(if (< 1 (gcd a p)) (error 'tonelli "must be coprime"))

(if (= (expp a p-1/2) -1)

(error 'tonelli "must be quadratic residue"))

(let loop ((s p-1) (e 0))

(if (even? s) (loop (/ s 2) (+ e 1))

(let loop ((n 2))

(if (not (= (expp n p-1/2) p-1)) (loop (+ n 1))

(let loop1 ((x (expp a (/ (+ s 1) 2)))

(b (expp a s)) (g (expp n s)) (r e))

(let loop2 ((m 0) (mm 1))

(if (not (= (expp b mm) 1)) (loop2 (+ m 1) (* mm 2))

(if (zero? m) (list x (- p x)) ; found result

(loop1 (modp (* x (expp g (expt 2 (- r m 1)))))

(modp (* b (expp g (expt 2 (- r m)))))

(expp g (expt 2 (- r m))) m)))))))))))

We defined functions `expp`

and `modp`

, and save the values of *p*−1 and (*p*−1)/2, to save redundancies later in the function. After the error returns, the first `loop`

computes *s* and *e* and the second loop computes *n*. Then `loop1`

is the main processing loop, with variables *x*, *b*, *g* and *r*, `loop2`

calculates *m*, and then the program exits when *m* = 0 or loops with new values of *x*, *b*, *g* and *r*. It’s all much simpler than the description on the previous page. Here’s an example:

`> (tonelli 2 113)`

(62 51)

You can check that by squaring: 62 · 62 = 3844 = 34 · 113 + 2, and 51 · 51 = 23 · 113 + 2.

We use `expm`

from the Standard Prelude and `prime?`

from a previous exercise. You can run the program at http://programmingpraxis.codepad.org/CAPseLXK.

Pages: 1 2

[…] Pages: 1 2 […]

A python version.

when i try to execute, i get the error as No module named ma.primee

This is great, was looking for an implementation of this instead of just the theory on Wikipedia, thank you!

awesome thanks alot…!! (y)