Ich mag ein Programm schreiben, die multiplikative Ordnung in Lisp finden, aber ich weiß nicht, was falsch mit meinem Programm

Question

hier ist die Definition von multiplikative Ordnung https://en.wikipedia.org/wiki/Multiplicative_order

hier wird das Programm

(defun power (x y) 
     (if (= y 0) 1 
      (if (evenp y) (* (power x (/ y 2)) (power x (/ y 2))) 
       (* x (power x (/ (- y 1) 2)) (power x (/ (- y 1) 2)))))) 
(defun ord (n r) 
     (if (> (gcd n r) 1) 0 
      (let ((a 0))(loop (defvar a (+ a 1)) 
       (when (= (mod (- (power r a) 1) n) 0)(return a)))))) 

Answer 1

Hier ist eine mögliche Lösung ohne die Verwendung einer power-Funktion (beachten Sie, dass eine solche Funktion bereits in Common Lisp, expt definiert ist).

(defun ord (n r) 
    (if (> (gcd r n) 1) 
     0 
     (loop for k from 1 
     for v = r then (* v r) 
     when (= 1 (mod v n)) 
      do (return k)))) 

Um die multiplikative Ordnung von ein Modulo n berechnet man die Funktion mit (ord a n) nennen sollte. Zum Beispiel:

(ord 7 10) ; => 6 

seit 10 ≡ 1 (mod 7)

Die Funktion prüft zuerst, um zu sehen, ob die beiden Parameter coprimes sind, sonst kehrt sie 0. Dann ist das erweiterte loop Form verwendet wird eine Schleife über zwei Variablen, k (das Ergebnis), beginnend bei 1 und bei jeder Iteration um 1, und v, die aktuelle Leistung von r, ausgehend von r und zunehmende Multiplikation des vorhergehenden Wertes mit r bei jeder Iteration (so Bei jeder Iteration die Invar iant ist v = r^k). Wenn wir den Wert k so erreichen, dass v mod n = 1 ist, beenden wir die Iteration, die k zurückgibt.

Für eine detaillierte Beschreibung von loop sehen entweder die formal definition oder eine praktische Erklärung (in Kapitel 7 und 22) des wirklich nützlichen Buchs Practical Common Lisp (ein „Muss lesen“ Common Lisp lernen).