an die programmierer unter euch

Professional

Tuesday, July 10th 2007, 4:03pm

hallo

ich habe hier eine aufgabe von unserem lehrer bekommen die wie folgt aussieht:

11= a^17 mod b^13 mod c^11

der zahlenbereich von a,b und c liegt jeweils von 1-100

es gibt für die aufgabe nur eine lösung die ich jedoch nicht rausbekomme...

die aufgabe ist vll durch brute force zu lösen und ich würde mich freuen wenn mir das jemand erklären könnte

thx schonmal mfg matze

This post has been edited 1 times, last edit by "DgT_matze4x4__" (Jul 10th 2007, 4:45pm)

Go to the top of the page

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

2

Tuesday, July 10th 2007, 4:14pm

folgender Code ist glaub ich in c (und imho auch java) compilierbar.

edit... nu aber

. hmm gibt keine Lösung :/

Source code

int x;
int resultA=0,resultB=0,resultC=0;
for (int a=1;a<101;a++)
	for (int b=1;b<101;b++)
		for (int c=1;c<101;c++)
		{
			x=int(pow(float(a),17))%int(pow(float(b),13))%int(pow(float(c),11));
			if (x==11)
			{
				resultA=a;
				resultB=b;
				resultB=b;
				a=b=c=101; //->break für alle schleifen
			}
		}

This post has been edited 3 times, last edit by "kOa_Borgg" (Jul 10th 2007, 4:21pm)

Go to the top of the page

patrik

Sage

Posts: 3,809

Occupation: GER

3

Tuesday, July 10th 2007, 4:19pm

Quoted
Original von kOa_Borgg
folgender Code ist glaub ich in c (und imho auch java) compilierbar.
Source code
1
         x=pow(a,17)%pow(b,13)%pow(c,11);

Das wird nicht in Java gehen...

Go to the top of the page

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

4

Tuesday, July 10th 2007, 4:22pm

jo maybe. c gings auch nicht auf anhieb. Scheiß pow Funktionen mit ihrem zwangsweisen floatinput...

aber irgendwie find der keine Lösung :/ sicher dass es eine gibt? ^^

This post has been edited 1 times, last edit by "kOa_Borgg" (Jul 10th 2007, 4:22pm)

Go to the top of the page

DgT_matze4x4__

Professional

Posts: 707

5

Tuesday, July 10th 2007, 4:31pm

ja es gibt eine und auch nur eine lösung sagte er

Go to the top of the page

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

6

Tuesday, July 10th 2007, 4:39pm

werd auch mal schauen, aber schonmal vorweg: brute force, nicht boot force

EDIT: und Zahlentyp int und überhaupt Precision reicht hinten und vorne ned für das was da an Potenzen so rauskommt

This post has been edited 1 times, last edit by "[AA]Hawk" (Jul 10th 2007, 4:48pm)

Go to the top of the page

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

7

Tuesday, July 10th 2007, 5:05pm

hmm das könnte ein Grund sein

Werd das mal mit double durch hangeln...

Go to the top of the page

kOa_Master

Sage

Posts: 12,493

Location: Basel

Occupation: CH

8

Tuesday, July 10th 2007, 5:25pm

2mal ResultB=b? O_o

Go to the top of the page

pitt82

Master

Posts: 2,114

9

Tuesday, July 10th 2007, 5:55pm

Also Modulo lässt sich logischerweise nur mit int Variablen durchführen.

Aber selbst unsigned long int geht nur bis 4 294 967 295. 100^11 is aber schon 10^22. So gesehn kommt man wohl um selbstgeschriebene Funktionen nich rum.

This post has been edited 1 times, last edit by "pitt82" (Jul 10th 2007, 5:57pm)

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

10

Tuesday, July 10th 2007, 6:01pm

*Edit: Lösung unten.

This post has been edited 3 times, last edit by "plexiq" (Jul 10th 2007, 6:33pm)

Go to the top of the page

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

11

Tuesday, July 10th 2007, 6:02pm

für die nicht-brute-force-Lösung hab ich an den kleinen Satz von Fermat gedacht bzw. die Eulersche Verallgemeinerung, hab aber grad weder Zeit noch Lust anzuschauen ob's damit geht ^^

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

12

Tuesday, July 10th 2007, 6:08pm

Mhm, Aufgabe wohl bewusst so gewählt, dass ihr euch mit BigNumber & Co herumschlagen dürft? *g*

Source code

import java.math.BigInteger;

public class ModBF {
	public static void main(String[] args) {
		BigInteger r = new BigInteger("11");

		for (int a = 1; a <= 100; a++) {
			BigInteger ba = new BigInteger(a + "").pow(17);

			for (int b = 1; b <= 100; b++) {

				BigInteger bb = new BigInteger(b + "").pow(13);
				bb = ba.mod(bb);

				for (int c = 1; c <= 100; c++) {

					BigInteger bc = new BigInteger(c + "").pow(11);
					bc = bb.mod(bc);

					if (bc.compareTo(r) == 0) {
						System.out.println(a + "," + b + "," + c);
						return;
					}

				}
			}
		}

	}
}

Results: a=50, b=77, c=2

Der Ubuntu "Taschenrechner" is der selben Meinung.

This post has been edited 4 times, last edit by "plexiq" (Jul 10th 2007, 6:34pm)

Go to the top of the page

Sheep

Sage

Posts: 4,172

Occupation: GER

13

Tuesday, July 10th 2007, 6:45pm

Maple meint:

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

14

Tuesday, July 10th 2007, 6:50pm

Wenn ich das letzte return rausnehme krieg ich 3 Lösungen:
50,77,2
52,5,2
99,21,2

Da is die von Sheep ebenfalls dabei, aber auch die beiden anderen "stimmen" lt. TR. Wär interessant zu wissen was Maple zu den beiden anderen "Lösungen" sagt?

This post has been edited 1 times, last edit by "plexiq" (Jul 10th 2007, 6:59pm)

Go to the top of the page

Sheep

Sage

Posts: 4,172

Occupation: GER

15

Tuesday, July 10th 2007, 7:00pm

Wenn ich bei Maple das a beschränke (nur noch bis 98, 51, 49), komme ich auf die gleichen drei Lösungen. Entweder haben die Entwickler bei den numerischen Operationen kollektiv geschlampt oder es ist tatsächlich richtig. Der erste Fall ist auch nicht tragisch, der Lehrer wird ja dann vermutlich das gleiche haben.

Go to the top of the page

DgT_matze4x4__

Professional

Posts: 707

16

Tuesday, July 10th 2007, 7:13pm

saubere arbeit

man muss dazu sagen das wir absolute anfänger sind und er sich gedacht hat das wir das nie rausbekommen(wo er ja auch recht hat)
jetzt komme ich morgen hin und wenn er nach der lösung fragt dann kann ich ihm die geben

werd mich selbstverständlich nicht mit fremden federn schmücken und ihm sagen wer das gelöst hat

thx nochmal

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

17

Tuesday, July 10th 2007, 7:32pm

Jetzt kannst ihm ja sogar 3 Lösungen anbieten *g* Ich nehm mal an er weiss gar nicht, dass mehrere Lösungen existieren. (Evtl auch Maple-Anwender?)

Kannst ja dann das Feedback hier posten

Go to the top of the page

ZwerG_Michi_de

Master

Posts: 2,655

Location: Schweinfurt

Occupation: GER

18

Tuesday, July 10th 2007, 7:34pm

plexiq is teh ownage ^^

Go to the top of the page

DgT_matze4x4__

Professional

Posts: 707

19

Tuesday, July 10th 2007, 7:39pm

Quoted

Original von plexiq
Kannst ja dann das Feedback hier posten

freu mich jetzt schon auf seinen blick (weil grad ich ihm das bringe)

hab mal rumgehört hier im internat und keiner hat was raus

Go to the top of the page

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

20

Tuesday, July 10th 2007, 8:16pm

Quoted

Original von kOa_Master
2mal ResultB=b? O_o

tippfehler

aber kam ja eh auf keinen grünen zweig...

Go to the top of the page

mymF.frantic

Intermediate

Posts: 561

21

Tuesday, July 10th 2007, 8:47pm

wie wäre es mit matlab? ^^

dann sparst dir irgendwelche komplizierten implementierungen weil du alles was du brauchst schon hast.

/edit: hm sehe gerade dass man da das problem hat dass er bei zu großen zahlen was abschneidet, wohl nicht brauchbar... ka ob man das einstellen kann..

This post has been edited 1 times, last edit by "mymF.frantic" (Jul 10th 2007, 9:27pm)

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

22

Tuesday, July 10th 2007, 9:42pm

Haskell > Mathlab

	Source code
1 2	Hugs.Base> [(a,b,c)\|a<-[1..100],b<-[1..100],c<-[1..100], (mod (mod (a^17) (b^13)) (c^11)) == 11] [(50,77,2),(52,5,2),(99,21,2)]

Go to the top of the page

Sheep

Sage

Posts: 4,172

Occupation: GER

23

Tuesday, July 10th 2007, 9:54pm

Quoted

Original von plexiq
Haskell > Mathlab

Wenn man solche neumodischen Qualitätsmerkmale wie Wartbarkeit und Verständlichkeit ignoriert, ja.

Go to the top of the page

HKD_H_A_T_E

Intermediate

Posts: 453

24

Tuesday, July 10th 2007, 11:51pm

also hut ab vor deiner lernerei matze.

Go to the top of the page

Event

Sage

Posts: 4,035

25

Wednesday, July 11th 2007, 1:08pm

Also wenn man Matheprobleme hat ist das Masters mal echt ne gute Hilfe @@

Go to the top of the page

kOa_DrohhyN_

Professional

Posts: 1,248

Location: Deutschland

Occupation: GER

26

Wednesday, July 11th 2007, 4:34pm

Hm, witzig daran ist insbesondere die Entwicklung daß sich kaum einer an eine mathematische Lösung (Satz von Fermat wurde genannt) gewagt hat - heutzutage löst man sowas mit "Brute Force"

Der Geist der Zeit *gg*

This post has been edited 1 times, last edit by "kOa_DrohhyN_" (Jul 11th 2007, 4:34pm)

Go to the top of the page

plexiq

Professional

Posts: 1,512

Location: Wien

27

Wednesday, July 11th 2007, 5:04pm

Seh nicht wie der kleine Fermatsche Satz hier anzuwenden wäre. Wir mod'en ja nicht mit Primzahlen?

Go to the top of the page

DgT_matze4x4__

Professional

Posts: 707

28

Wednesday, July 11th 2007, 7:08pm

riesen lob nochmal an alle, der lehrer hat sich gefreut zumal ich der einzigste war der überhaupt was mitgebracht hat^^
hab dann auch gleich aufgelöst und ihr sollt euch alle ne 1 eintragen

die auflösungen von euch hat er sich mitgenommen (er hatte via perl noch was anderes raus )
das ergebnis gibts dann später

insgesamt ging es ihm um passwörter da man ja durch die mod funktion nicht zurückrechnen kann und man dadurch schwer auf das passwort kommen soll

Go to the top of the page

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

29

Wednesday, July 11th 2007, 8:51pm

@plexiq: ich meinte ja auch die Verallgemeinerung durch Euler - aber irgendwie bin ich noch nicht überzeugt dass die's bringt, die Eulersche phi-Funktion hat's in sich ^^

This post has been edited 1 times, last edit by "[AA]Hawk" (Jul 11th 2007, 8:51pm)

Go to the top of the page

MastersForum