Quadratische Reste

Um die quadratischen Reste einer natürlichen Zahl zu bestimmen, berechnet man die Liste der Quadrate von 0 bis zur Zahl vermindert um 1 modulo der Zahl und entfernt die Duplikate.

Für die Zahl 128 ergibt sich die Liste (0 1 4 9 16 17 25 33 36 41 49 57 64 65 68 73 81 89 97 100 105 113 121).

(defproc quadratic-residues (n)
  (unique
    (sort
      (map-with
        (lambda (m) (rem (* m m) n))
        (range 0 n))
      <)
    =))

(defproc unique (l p)
  (cond
    ((null? l) nil)
    ((single? l) l)
    ((p (first l) (second l)) (unique (rest l) p))
    (t (cons (first l) (unique (rest l) p)))))


quadratic-residues.sheet.xml