You are not logged in.

  • Login

an die programmierer unter euch

Dear visitor, welcome to MastersForum. If this is your first visit here, please read the Help. It explains in detail how this page works. To use all features of this page, you should consider registering. Please use the registration form, to register here or read more information about the registration process. If you are already registered, please login here.

DgT_matze4x4__

Professional

  • "DgT_matze4x4__" started this thread

Posts: 707

  • Send private message

1

Tuesday, July 10th 2007, 4:03pm

an die programmierer unter euch

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)

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

  • Send private message

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

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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)

patrik

Sage

Posts: 3,809

Occupation: GER

  • Send private message

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...

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

  • Send private message

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)

DgT_matze4x4__

Professional

  • "DgT_matze4x4__" started this thread

Posts: 707

  • Send private message

5

Tuesday, July 10th 2007, 4:31pm

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

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

  • Send private message

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)

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

  • Send private message

7

Tuesday, July 10th 2007, 5:05pm

hmm das könnte ein Grund sein ;) Werd das mal mit double durch hangeln...

kOa_Master

Sage

Posts: 12,493

Location: Basel

Occupation: CH

  • Send private message

8

Tuesday, July 10th 2007, 5:25pm

2mal ResultB=b? O_o

pitt82

Master

Posts: 2,114

  • Send private message

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)

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

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)

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

  • Send private message

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 ^^

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

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

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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)

Sheep

Sage

Posts: 4,172

Occupation: GER

  • Send private message

13

Tuesday, July 10th 2007, 6:45pm

Maple meint:

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

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)

Sheep

Sage

Posts: 4,172

Occupation: GER

  • Send private message

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. :P

DgT_matze4x4__

Professional

  • "DgT_matze4x4__" started this thread

Posts: 707

  • Send private message

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

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

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 ;)

ZwerG_Michi_de

Master

Posts: 2,655

Location: Schweinfurt

Occupation: GER

  • Send private message

18

Tuesday, July 10th 2007, 7:34pm

plexiq is teh ownage ^^

DgT_matze4x4__

Professional

  • "DgT_matze4x4__" started this thread

Posts: 707

  • Send private message

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) :D
hab mal rumgehört hier im internat und keiner hat was raus ?(

kOa_Borgg

Sage

Posts: 6,204

Occupation: GER

  • Send private message

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...

mymF.frantic

Intermediate

Posts: 561

  • Send private message

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)

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

22

Tuesday, July 10th 2007, 9:42pm

Haskell > Mathlab :P

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)]

Sheep

Sage

Posts: 4,172

Occupation: GER

  • Send private message

23

Tuesday, July 10th 2007, 9:54pm

Quoted

Original von plexiq
Haskell > Mathlab :P


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

HKD_H_A_T_E

Intermediate

Posts: 453

  • Send private message

24

Tuesday, July 10th 2007, 11:51pm

also hut ab vor deiner lernerei matze.

Event

Sage

Posts: 4,035

  • Send private message

25

Wednesday, July 11th 2007, 1:08pm

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

kOa_DrohhyN_

Professional

Posts: 1,248

Location: Deutschland

Occupation: GER

  • Send private message

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" :D:D:D
Der Geist der Zeit *gg*

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

plexiq

Professional

Posts: 1,512

Location: Wien

  • Send private message

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?

DgT_matze4x4__

Professional

  • "DgT_matze4x4__" started this thread

Posts: 707

  • Send private message

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
?(

[AA]Hawk

Sage

Posts: 6,250

Occupation: GER

  • Send private message

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)