Sie sind nicht angemeldet.

  • Anmelden

an die programmierer unter euch

DgT_matze4x4__

Profi

  • »DgT_matze4x4__« ist der Autor dieses Themas

Beiträge: 707

  • Nachricht senden

1

10.07.2007, 16:03

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »DgT_matze4x4__« (10.07.2007, 16:45)

kOa_Borgg

Erleuchteter

Beiträge: 6 204

Beruf: GER

  • Nachricht senden

2

10.07.2007, 16:14

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

edit... nu aber ;). hmm gibt keine Lösung :/

Quellcode

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

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »kOa_Borgg« (10.07.2007, 16:21)

patrik

Erleuchteter

Beiträge: 3 809

Beruf: GER

  • Nachricht senden

3

10.07.2007, 16:19

Zitat

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

Quellcode

 
1

         x=pow(a,17)%pow(b,13)%pow(c,11);


Das wird nicht in Java gehen...

kOa_Borgg

Erleuchteter

Beiträge: 6 204

Beruf: GER

  • Nachricht senden

4

10.07.2007, 16:22

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »kOa_Borgg« (10.07.2007, 16:22)

DgT_matze4x4__

Profi

  • »DgT_matze4x4__« ist der Autor dieses Themas

Beiträge: 707

  • Nachricht senden

5

10.07.2007, 16:31

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

[AA]Hawk

Erleuchteter

Beiträge: 6 250

Beruf: GER

  • Nachricht senden

6

10.07.2007, 16:39

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »[AA]Hawk« (10.07.2007, 16:48)

kOa_Borgg

Erleuchteter

Beiträge: 6 204

Beruf: GER

  • Nachricht senden

7

10.07.2007, 17:05

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

kOa_Master

Erleuchteter

Beiträge: 12 493

Wohnort: Basel

Beruf: CH

  • Nachricht senden

8

10.07.2007, 17:25

2mal ResultB=b? O_o

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

9

10.07.2007, 17:55

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.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »pitt82« (10.07.2007, 17:57)

plexiq

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

10

10.07.2007, 18:01

*Edit: Lösung unten.

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »plexiq« (10.07.2007, 18:33)

[AA]Hawk

Erleuchteter

Beiträge: 6 250

Beruf: GER

  • Nachricht senden

11

10.07.2007, 18:02

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

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

12

10.07.2007, 18:08

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

Quellcode

 
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.

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »plexiq« (10.07.2007, 18:34)

Sheep

Erleuchteter

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

13

10.07.2007, 18:45

Maple meint:

plexiq

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

14

10.07.2007, 18:50

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?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »plexiq« (10.07.2007, 18:59)

Sheep

Erleuchteter

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

15

10.07.2007, 19:00

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__

Profi

  • »DgT_matze4x4__« ist der Autor dieses Themas

Beiträge: 707

  • Nachricht senden

16

10.07.2007, 19:13

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

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

17

10.07.2007, 19:32

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

Meister

Beiträge: 2 655

Wohnort: Schweinfurt

Beruf: GER

  • Nachricht senden

18

10.07.2007, 19:34

plexiq is teh ownage ^^

DgT_matze4x4__

Profi

  • »DgT_matze4x4__« ist der Autor dieses Themas

Beiträge: 707

  • Nachricht senden

19

10.07.2007, 19:39

Zitat

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

Erleuchteter

Beiträge: 6 204

Beruf: GER

  • Nachricht senden

20

10.07.2007, 20:16

Zitat

Original von kOa_Master
2mal ResultB=b? O_o

tippfehler :) aber kam ja eh auf keinen grünen zweig...

mymF.frantic

Fortgeschrittener

Beiträge: 561

  • Nachricht senden

21

10.07.2007, 20:47

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »mymF.frantic« (10.07.2007, 21:27)

plexiq

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

22

10.07.2007, 21:42

Haskell > Mathlab :P

Quellcode

 
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

Erleuchteter

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

23

10.07.2007, 21:54

Zitat

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

Fortgeschrittener

Beiträge: 453

  • Nachricht senden

24

10.07.2007, 23:51

also hut ab vor deiner lernerei matze.

Event

Erleuchteter

Beiträge: 4 035

  • Nachricht senden

25

11.07.2007, 13:08

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

kOa_DrohhyN_

Profi

Beiträge: 1 248

Wohnort: Deutschland

Beruf: GER

  • Nachricht senden

26

11.07.2007, 16:34

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*

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »kOa_DrohhyN_« (11.07.2007, 16:34)

plexiq

Profi

Beiträge: 1 512

Wohnort: Wien

  • Nachricht senden

27

11.07.2007, 17:04

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

DgT_matze4x4__

Profi

  • »DgT_matze4x4__« ist der Autor dieses Themas

Beiträge: 707

  • Nachricht senden

28

11.07.2007, 19:08

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

Erleuchteter

Beiträge: 6 250

Beruf: GER

  • Nachricht senden

29

11.07.2007, 20:51

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »[AA]Hawk« (11.07.2007, 20:51)