Mathe Zahlen zerlegen

[Worka]

Hallo
Kennt einer von Euch eine Möglichkeit folgendes Problem effizient (also mit möglichst geringem Aufwand) zu lösen?

1. Gegeben seien 2 Zahlen X und Y.
2. Nun erzeuge ich 2 Zufallszahlen A und B und erzeuge daraus die Zahl: Z = A*X + B*Y
Den Schritt Nr.2 wiederhole ich mehrmals (n mal) und erzeuge verschiedene Zahlen Z1 bis Zn.


z.B.
X = 123
Y = 98

Nun erzeuge ich die Zahlen: Z = Zufallzahl() * X + Zufallszahl() * Y
Z1 = 45 * 123 + 87 * 98 = 14061
Z2 = 21 * 123 + 64 * 98 = 8855
Z3 = 76 * 123 + 83 * 98 = 17482



Mein Anliegen:
Wenn ich nur die Zahlen Z1 bis Zn kenne, wie kann ich daraus X und Y ermitteln?
Es muss nichtmal das "orginal" X und Y sein, da es ja möglich ist, dass auch andere Zahlen als X und Y sich eignen um die Zahlen Z1 bis Zn zu bilden.


z.B.
X = 4
Y = 5

Nun erzeuge ich die Zahlen: Z = Zufallzahl() * X + Zufallszahl() * Y
Z1 = 5 * 4 + 2 * 5 = 30
Z2 = 15 * 4 + 6 * 5 = 90
Z3 = 20 * 4 + 14 * 5 = 150

Hier könnte man auch X=20 und Y=10 ermiteln da sich die 20 und 10 auch eignen um die 30, 90 und die 150 aus A * X + B * Y zu bilden.
1 * 20 + 1 * 10 = 30
4 * 20 + 1 * 10 = 90
7 * 20 + 1 * 10 = 150

Oder man könnte X = 30 und Y = 0 ermitteln, da alle Zahlen durch 30 teilbar sind.

Wenn alle Zahlen einen grössten gemeinsamen Teiler haben, ist die Lösung natürlich leicht.
Was aber wenn es keinen ggT > 1 gibt, der alle Zahlen restlos teilt?

Gibt es da einen Weg der deutlich schneller ist, als alle Möglichkeiten zu probieren?

 

[D_Blade]

Ich würde für jedes gegebene Zn in Primfaktoren zerlegen.

Also 30 = 2 * 3 * 5

90 = 2 * 3² * 5

150 = 2 * 3 * 5²

Und aus der Menge der Primfaktoren dann den Durchschnitt bilden. Wäre in diesem Fall also {2,3,5}.

Theoretisch hättest du auf diese Weise immer mind. 2 Werte.

(Ich nehme mal an die Zufallszahlen gehen von 1 bis unendlich im Zahlengebiet der natürlichen Zahlen).
Aufwand wäre allerdings so groß wie die Anzahl der Z. Eine schnellere Methode fällt mir auf die schnelle nicht ein.

 

[MrToiz]

Ich würde für jedes gegebene Zn in Primfaktoren zerlegen.

Das wird nicht funktionieren, weil Z ja immer eine Summe ist.
Beispiel:

X = 4
Y = 3
Z = 2*X + 3*Y
   = 2*4 + 3*3
   = 17 => Primfaktoren: 1, 17

Es bleibt also nichts anderes übrig, als für jedes Z alle möglichen X und Y zu bestimmen und dann nach Übereinstimmungen zu suchen.

Um das möglichst effizient zu gestalten, würde ich mit dem kleinsten Z anfangen (weil es da vermutlich die wenigsten Möglichkeiten für X und Y gibt), und bei den größeren Z immer nur die X und Y prüfen, die bei den zuvor geprüften Z gepasst haben. Verständlich, was ich meine?

 

[D_Blade]

Ja stimmt, diese Möglichkeit ist mir nach meinem Post auch eingefallen, aber da hatte ich meinen Pc schon abgeschalten bevor ich was korrigieren konnte.

Ausnahme wäre wohl natürlich, wenn man als Z selbst eine Primzahl bekäme.

Auch ist mir eingefallen, dass man einfach sagen könne: X und Y seien beide gleich 1.

 

[Worka]

Hallo
Erstmal danke für die Antworten.
Das mit der Primzahlzerlegung hatte ich auch erst überlegt, aber es hilft mir nicht weiter und wäre ja auch nicht unbedingt effizient lösbar.

Das wird nicht funktionieren, weil Z ja immer eine Summe ist.
...
Um das möglichst effizient zu gestalten, würde ich mit dem kleinsten Z anfangen (weil es da vermutlich die wenigsten Möglichkeiten für X und Y gibt), und bei den größeren Z immer nur die X und Y prüfen, die bei den zuvor geprüften Z gepasst haben. Verständlich, was ich meine?

Die Idee ist gut, danke dafür!


Wäre das Problem deutlich leichter zu lösen, wenn B*Y immer kleiner als X ist, also wenn gilt:
B*Y < X ?

Mit deutlich leichter meine ich, ob es eine Möglichkeit gibt X und Y zu finden, die deutlich schneller ist als durch ausprobieren.
Natürlich wird der Bereich von B*Y dadurch stark eingeschränkt, so dass ich auch mit dem Probieren aller Möglichkeiten schneller fertig wäre, solange gilt: B*Y < X

Aber wenn X eine SEHR grosse Zahl ist, so dass B*Y auch einen grossen Zahlenraum einnehmen kann, dauert das Probieren aller Möglichkeiten wieder sehr lange.