Gibt es einen Algorithmus zur Berechnung der multiplikativen Reihenfolge von x modulo y (für y <1000), die keinen BigInteger-Typ erfordert?

Question

Der Algorithmus, den ich gerade benutze, läuft sehr schnell in extrem hohen Zahlen. Ein Schritt in dem Algorithmus, den ich bin, hebt x auf das Ergebnis der totient Funktion an, die auf y angewandt wird. Das Ergebnis ist, dass Sie sehr große Zahlen erreichen können.

Eg. Bei der Berechnung der multiplicative order von 10 Modulo 53:

10^totient(53) == 10^52 == 1 * 10^52 

den folgenden Algorithmus Tarife ein bisschen besser entweder in Bezug auf große Zahlen zu vermeiden, aber es immer noch nicht, wo 10^morder ist größer als die Kapazität des Datentyps :

mOrder = 1 
    while 10^mOrder % 53 != 1 
     if mOrder >= i 
      mOrder = 0; 
      break 
     else 
      mOrder = mOrder + 1 

Answer 1

modulare Potenzierung verwendet wird, ist es möglich, (10^morder% 53) oder im allgemeinen jeden (a^b mod c) Werte zu berechnen, ohne viel größer als C zu erhalten. Siehe Wikipedia für Details, gibt es diesen Beispielcode, auch:

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) { 

    Bignum result = 1; 

    while (exponent > 0) { 
     if ((exponent & 1) == 1) { 
      // multiply in this bit's contribution while using modulus to keep result small 
      result = (result * base) % modulus; 
     } 
     // move to the next bit of the exponent, square (and mod) the base accordingly 
     exponent >>= 1; 
     base = (base * base) % modulus; 
    } 

    return result; 
} 

Answer 2

Warum potenzieren? Können Sie nicht einfach modulo n in einer Schleife multiplizieren?

 
(defun multiplicative-order (a n) 
    (if (> (gcd a n) 1) 
     0 
     (do ((order 1 (+ order 1)) 
      (mod-exp a (mod (* mod-exp a) n))) 
      ((= mod-exp 1) order)))) 

Oder in ptheudo (sic) Code:

def multiplicative_order (a, n) : 
    if gcd (a, n) > 1 : 
     return 0 
     else: 
     order = 1 
     mod_exp = a 
     while mod_exp != 1 : 
      order += 1 
      mod_exp = (mod_exp * a) mod n 
     return order