;; As of 17Nov2006:
;;
;; Currently, this code only works when the modulus N is 561.
;; This is because , writing
;;    N = D*[2^K],   where D is odd,
;; I have hard-coded the values of D (=35) and K (=4).

(setq N (* 3 11 17)) ;;Modulus
(setq H (/ N 2))     ;;Half the modulus, rounded.

(defun modNpos (z)  ;; Non-negative residue.
  (mod z N) )

(defun modN (z)	    ;; Symmetric residue.		
  (setq result (mod z N))
  (if (<= result H)
      result
    ;;else
    (- result N)) )

;; (modN 281) (modN 560)

;; We compute the multipliers to realize the ring-iso
;; from		Z3 × Z11 × Z17
;; to		Z561 .
;;
(setq  
  A	 1
  B	-3
  C	-1
  AA (modN (* A 11 17))
  BB (modN (* 3  B 17))
  CC (modN (* 3 11  C))
  )
AA
187
BB
-153
CC
-33


(defun iso (x y z) ;; This realizes the isomorphism.
  (modN (+ (* AA x) (* BB y) (* CC z))) )

(iso 1  1  1)
1
(iso 1  1 -1)
67

;; Lets compute the 8 square-roots of 1.
(progn
  (setq PMO  '( +1 -1)) ;;PlusMinusOne
  (princ "\n  THE EIGHT SQROOTS of 1:\n")
  (princ "Z3 × Z11 × Z17  iso        Z561\n")
  (princ "  ( x  y  z)    ->    Sqrt of 1\n")
  (dolist (x PMO) (dolist (y PMO) (dolist (z PMO)
   (setq RootOfOne (iso x y z))
   (princ (format
     "  (%2s %2s %2s)    ->  %9d\n" x y z RootOfOne))
   ) ) ) )

  THE EIGHT SQROOTS of 1:
Z3 × Z11 × Z17  iso        Z561
  ( x  y  z)    ->    Sqrt of 1
  ( 1  1  1)    ->          1
  ( 1  1 -1)    ->         67
  ( 1 -1  1)    ->       -254
  ( 1 -1 -1)    ->       -188
  (-1  1  1)    ->        188
  (-1  1 -1)    ->        254
  (-1 -1  1)    ->        -67
  (-1 -1 -1)    ->         -1

The two sqroots of 67 are (1 1 ±4).  I.e,
(iso 1 1 4)
-98
(iso 1 1 -4)
166

;; Other than 1 and 67, the other six sqroots of 1
;; do NOT have sqroots!

;; ================================================================

(defun printpowout (pow out)
  (princ (format "%3s   %6s\n" pow out)) )

(defun tf (x)
  (setq
    pow 35
    two   (modNpos (* x x))
    four  (modNpos (* two two))
    five  (modNpos (* four x))		;5th power.
    ten   (modNpos (* five five))	;Tenth power.
    fifte (modNpos (* ten  five))	;Fifteenth power.
    twent (modNpos (* ten ten))		;20 power.
    out   (modN (* fifte twent))	;35 power.
    )
  (printpowout "  E" (format "%2d^E mod N" x))
  (printpowout  pow out)
  (dotimes (j 4 out)
    (outsquared)
    ) "Done")

(defun outsquared ()
  (setq pow	(+ pow pow)
	out	(modN (* out out))
	)
  (printpowout  pow out) )

(tf 2)
  E    2^E mod N
 35      263
 70      166
140       67
280        1
560        1
"Done"

(tf 3)
  E    3^E mod N
 35       78
 70      -87
140      276
280     -120
560     -186
"Done"

(tf 37)
  E   37^E mod N
 35      265
 70      100
140      -98
280       67
560        1
"Done"

(tf 67)
  E   67^E mod N
 35       67
 70        1
140        1
280        1
560        1
"Done"

(tf -1)
  E   -1^E mod N
 35       -1
 70        1
140        1
280        1
560        1
"Done"