Schnell und schnurrig - das Lieblingsprogramm: (geeignete Testzahlen sind bekannte Inverse, Ergebnis dann 1)

#(c) Dr. Ulrike Ritter

 

#Das Programm berechnet ziffernweise den Modulo-Rest von Potenzen mit bis zu 30stelligen Exponenten

 

import math

 

import sys

 

from sys import argv

 

import csv

 

from csv import reader

 

import re

 

import itertools

 

import pickle

 

import typing

 

from datetime import datetime

 

import cmath

 

import time

 

ba = int(input("ba: "))

 

n = int(input("modulus: "))

 

#exponent = int(input("exponent: "))

 

#hier als Beispiel vorinstantiiert mit:

 

exponent = 32574143196786285757152

 

x = 0

 

expon = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

 

expodig = exponent

 

for t in range(0, 24):

 

if (exponent % 10**t == exponent):

 

exdigit = t

 

break

 

print("exdigit", exdigit)

 

for x in range(0, 24):

 

y = 24 - x

 

if (expodig > 10**y):

 

digit = y+1

 

expon_y = int((expodig)/(10**(y)))

 

expon[y] = expon_y

 

expodig = expodig - expon_y*(10**y)

 

if expodig < 10:

 

expon[0] = int(expodig)

 

break

 

if (expon[exdigit-2] == 10):

 

expon[exdigit-1] = 1

 

expon[exdigit-2] = 0

 

print("exponentin expon", expon)

 

modul = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

 

aw10 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

 

ug = 0

 

aw = ba

 

for x in range (0, exdigit):

 

if (x==0):

 

aw = ba%n

 

ex = expon[x]

 

print("x, aw, ex", x, aw, ex)

 

modul[x] = (aw**ex)%n

 

modulprod = modul[0]

 

print("aw, expon[x], x, modul", aw, expon[x], x, modul)

 

if (24 > x > 0):

 

aw = ba%n

 

if x == 1:

 

aw = (aw**2)%n

 

aw = (aw**2)%n

 

aw = (aw**2)%n

 

aw = aw*ba %n

 

aw = aw*ba %n

 

print("aw", aw)

 

aw10[x]= aw

 

if (expon[x]>0):

 

modul[x] = (aw**expon[x])%n

 

if (expon[x]==0 and exponent%10 == 0):

 

modul[x] = 1

 

if (expon[x]==0 and exponent%10 > 0):

 

modul[x] = 1

 

print("aw, expon[x], x, modul", aw, expon[x], x, modul)

 

if (x > 1):

 

aw = (((aw10[x-1]*aw10[x-1]*aw10[x-1] )%n)*((aw10[x-1]*aw10[x-1]*aw10[x-1])

 

%n)*((aw10[x-1]*aw10[x-1]*aw10[x-1])%n)*(aw10[x-1])%n)

 

aw10[x] = aw

 

print("aw", aw)

 

if (expon[x]>0):

 

modul[x] = (aw**expon[x])%n

 

if (expon[x]==0 and exponent%10 == 0):

 

modul[x] = 1

 

if (expon[x]==0 and exponent%10 > 0):

 

modul[x] = 1

 

print("aw10[], expon[x], x, modul", aw10, expon[x], x, modul)

 

modulpro = 1

 

modul[0] = modulprod

 

print("modul, modulpro, exdigit", modul, modulpro, exdigit)

 

def multiplyList(modul, n, exdigit, modulpro):

 

m = 0

 

for m in range(0, exdigit):

 

if (m < exdigit):

 

if (modul[m]==1):

 

m= m+1

 

modulpro = (modulpro * modul[m])%n

 

print(modulpro)

 

if m == exdigit-1 :

 

return modulpro

 

print(modulpro)

 

break

 

return modulpro

 

modulprod= multiplyList(modul, n, exdigit,modulpro)

 

print(modulprod)