Modulo berechnen

[Jayman]

hi,
ich habe eine schwierige Aufgabe zu bewältigen mit einer modulo Rechnung.
es geht um Augabe
x_(n+1) = 16807*x_n mod 2^31 - 1
Dabei soll x_1 maximal werden und die Frage ist wie x_0 dann aussieht.
Wie kann ich das programmieren, damit ich auf die Lösung komme.
die maximale Zahl ist ja 2^31 - 2 (2147483646), also bräuc´hte ich so etwas:
2147483646 = 16807*x mod 2147483647
ist das zu programmieren? finde nur über google englischsprachige Seiten und da ist mein Schulenglisch etwas zu schwach...

 

[AmunRa]

Wenn du vor hast eine hierfür eine Explizitelösung für diese Folge zufinden muss ich dich glaub ich entäuschen, das einzige was ich mir vorstellen kann ist eine Rekursive- lösung

du stehst eben vor dem Problem , dass:

4 mod 3 = 1 ist
und

3 mod 2 = 1 ebenfalls

Eine Lösung für dein Problem ist z.B

2147483646/16807= 12777,088800699695965443587012786

 

[Ark]

die maximale Zahl ist ja 2^31 - 2 (2147483646)

Ich weiß zwar nicht, von welchem System du ausgehst, aber bei mir liegt das Maximum bei 2147483647; es muss auf jeden Fall eine ungerade Zahl sein.

Ark

 

[Jayman]

Dein Maximum ist ja die Modulozahl selbst...

 

[Ark]

Ach, so rum meinst du das. Ja, dann hast du Recht.

Ark

 

[0x7F800000]

ich habe eine schwierige Aufgabe zu bewältigen mit einer modulo Rechnung

Nö, euklidischer Algo läuft in O(lg(n)) worst case, daher ist das problem eigentlich komplexitätstheoretisch nicht als schwierig zu bewerten 😉

Wenn diese Aufgabe allerdings nicht in einer Zahlentheorie/Kryptographie Vorlesung gestellt wurde, dann ist sie schlicht und einfach nicht machbar. Das läuft alles unter dem Motto Restklassenringe/Euklidischer algorithmus/Bezout Koeffizienten. Einfach so von alleine kommt man da niemals drauf, wenn man das nicht in einer vorlesung mal gehört hat... :bahnhof:

Mit standard-Java API geht's so:

java.math.BigInteger y=
			(new java.math.BigInteger("16807"))
			.modInverse(new java.math.BigInteger(String.valueOf(Integer.MAX_VALUE)))
			.multiply(new java.math.BigInteger(String.valueOf(Integer.MAX_VALUE-1)))
			.mod(new java.math.BigInteger(String.valueOf(Integer.MAX_VALUE)));
		System.out.println(y);
		System.out.println(y.multiply(new java.math.BigInteger("16807")).mod(new java.math.BigInteger(String.valueOf(Integer.MAX_VALUE))));

Wenn man spaß an der Sache hat, und in etwa weiß was man da tut, kann man das auch selbst schnell basteln:

//etwas kryptisch hingeschrieben. Im code eh unverständlich. Google "BezoutkoeffizienT"
	public static long modInverse(long a, long p){
		long a1=1, a2=0, q;
		while(p!=0){
			q=a/p;
			a2=a1-q*(a1=a2);
			p=a-q*(a=p);
		}
		return a1;
	}

// modulo rechnen ist fast dasselbe wie %, aber mit kanonischer representantenwahl:
public static long mod(long n, long m){
		return ((n%=m)<0)?n+m:n;
	}

und anwenden:

long x=mod(modInverse(16807,Integer.MAX_VALUE)*2147483646,Integer.MAX_VALUE);
		System.out.println(x);
		System.out.println(x*16807%Integer.MAX_VALUE);

Ausgabe in beiden Fällen:

739806647
2147483646

...soo
Hoffentlich hab ich mich jetzt nirgends verrechnet, das wär ja mordspeinlich 😉

 

[Jayman]

danke für so eine ausführleich antwort.
aber leider ist doch... 16807 * 739806647 mod 2147483647 = 0 und nicht 2147483646 🙁

 

[AmunRa]

aber leider ist doch... 16807 * 739806647 mod 2147483647 = 0 und nicht 2147483646 🙁

Das würd ich an deiner Stelle nocheinmal mit dem Taschenrechner nachrechnen

Das geht sogar mit dem Windows rechner

da kommt für die Rechnung 2147483646 raus

LG

 

[Jayman]

bei meinem Casio Rechner, kam da der Rest von 0 raus...
Danke vielmals! passt 😀

 

[0x7F800000]

Wenn diese Aufgabe allerdings nicht in einer Zahlentheorie/Kryptographie Vorlesung gestellt wurde, dann ist sie schlicht und einfach nicht machbar.

Meine Implizit gestellte Frage lautet: wie kommst du denn jetzt eigentlich darauf, so etwas berchnen zu wollen? ???:L

 

[Jayman]

der Prof meinte das sei eine schwierige aber machbare Aufgabe.
ich dachte, dass dieses doch per programmieren zu lösen sei, wie du auch bewiesen hast. denn rechnerisch bin ich nicht daruaf gekommen.
eine Frage zu deinem Code, was wird in modInverse für a,sowie p übergeben? 16807 als a, und 2147483646 als p?

 

[0x7F800000]

der Prof meinte das sei eine schwierige aber machbare Aufgabe.

per bruteforce vielleicht :noe:

eine Frage zu deinem Code, was wird in modInverse für a,sowie p übergeben? 16807 als a, und 2147483646 als p?

modInverse(a,p) berechnet das Inverse von a in Z/pZ

modInverse(16807,Integer.MAX_VALUE)

...in diesem fall eben das Inverse von 16807 im Z/Int.MAX Z