[Algorithmus-Problem] Primzahlarray, welche zahlen sind mgl

moose · 05.10.2007, 18:53

Hi,
ich habe einen array, in dem Primzahlen gespeichert sind:
$primes = array(2,2,2,3,11,37);

Nun will ich in einen zweiten array speichern, welche zahlen möglich sind (man muss nicht alle primzahlen benutzen), also:

$numbers[] = 2;
$numbers[] = 4;
$numbers[] = 12;...

ich bin mir relativ sicher dass man das Problem rekursiv angehen muss, allerdings is mir nur eingefallen wieviele zahlen es gibt ... (n²+n)/2, also im beispiel sollte $numbers 21 elemente haben.

Momentan muss man bei mir die funktion dem array anpassen, und das gefällt mir gar nicht:

PHP-Code:

  <? 

$a_numbers = arraymit3elementen(array(2,3,4));

function get_all_numbers($faktors){

    $produkt = 1;

    foreach($faktors as $faktor){

      $produkt *= $faktor;

      $a_numbers[]=$faktor;

    }

    $a_numbers[] = $produkt;

    

    foreach($a_faktors AS $key=>$faktor1){

      unset($a_faktors[$key]);

      foreach($a_faktors AS $faktor2){

        $a_numbers[]=$faktor1*$faktor2;

      }

    }

    return $a_numbers;

}

Vielleicht hilft jemanden dieses Schema, das ich mir überlegt hab (mir hats nicht geholfen):
Array Faktors : abcde
Array Numbers:

abcde
abcd
abc
ab
a
------
bcde
bcd
bc
b
-----
cde
cd
c
-----
de
d
----
e

Es gibt count($a_faktors)-1 dieser Blöcke und jeder block hat ein element weniger (also 5, 4, 3, 2, 1)

agrajag · 05.10.2007, 19:46

Sorry, aber kannst du nochmal erklären was du machen willst?
Du sprichst andauernd von Zahlen die möglich sind? Wie "möglich"?

Vielleicht fängst du einfach mal ganz von vorne an: Was willst du erreichen?

Der_Gerhard · 05.10.2007, 20:04

Zitat:

Zitat von moose

ich bin mir relativ sicher dass man das Problem rekursiv angehen muss, allerdings is mir nur eingefallen wieviele zahlen es gibt ... (n²+n)/2, also im beispiel sollte $numbers 21 elemente haben.

Ich persönlich finde, dass $Numbers 42 sein sollte. $Anzahl wäre mit 17 super besetzt und $IrgendwasAnderes müsste dann den Wert $Number*$Daumen/$DenGanzenRest haben. Mein Nachbar schwört aber auf 23 für $Numbers.

Sollte Dir das total wirr vorkommen, dann gratuliere ich Dir. Mir kommt Deine Beschreibung genauso vor.

Willst Du vielleicht die Anzahl möglicher Zahlen, in denen die gegebenen Primzahlen nur je maximal einmal enthalten sind und die sonst keine weiteren Primfaktoren enthalten berechnen?
Was auch immer man dann mit dem Wert anfangen kann.... ????

agrajag · 05.10.2007, 20:13

Zitat:

Zitat von Der_Gerhard

Ich persönlich finde, dass $Numbers 42 sein sollte. $Anzahl wäre mit 17 super besetzt und $IrgendwasAnderes müsste dann den Wert $Number*$Daumen/$DenGanzenRest haben. Mein Nachbar schwört aber auf 23 für $Numbers.

YMMD. Da wir jetzt die Antwort kennen: Wie lautet die Frage?

Und ich dachte schon ich hätte einen Knoten im Kopf...

Zergling-new · 05.10.2007, 20:13

Und das noch:
http://www.lugbz.org/documents/smart...s_de.html#goal

moose · 05.10.2007, 20:16

okay:
Ich habe eine Verschlüsselung. Diese multipliziert am ende einen schlüssel mit einer zahl. Nun bekomme ich nur die verschlüsselte zahl und muss den schlüssel rausbekommen. Natürlich muss der Schlüssel dann ein Primfaktor beziehungsweise das Produkt mehrerer Primfaktoren sein. Ich habe eine Primfaktorzerlegung gemacht und will nun alle möglichen entschlüsselten texte herausbekommen. dazu muss ich die zahl, die vorher mit dem schlüssel multipliziert wurde durch den von mir vermuteten schlüssel teilen. Und zwar durch jeden schlüssel, der möglich ist, wenn ich garantieren will dass die lösung dabei ist.

Ich hoffe ich habe mich nun deutlich ausgedrückt ... anscheindend denke ich im moment etwas wirr^^

Zergling-new · 05.10.2007, 20:37

Das ist doch keine Verschlüsselung ..

Benutz lieber Open-Source Algorithmen, deren Quellcode liegt offen und ist somit vielen kritischen Blicken ausgesetzt. Fehler und Schwachstellen sind deshalb meist schneller bekannt und gefixt als mißbraucht:
http://www.phpfriend.de/forum/ftopic61226.html
Blowfish ist denk ich OK.

Oder machst du das zum Spass? Kann ich verstehen, fasziniert. Dann erklär aber nochmal genauer wie du ver- und entschlüsselst (ist ja anonym), hab das noch nicht so ganz verstanden.
Du erstellst Text, verschlüsselst ihn "irgendwie" mit einem Schlüssel der beiden (Sender und Empfänger) bekannt sein muss, versteckst den verwendeten Schlüssel dann aber nochmal, in dem du ihn mit einer Primzahl multiplizierst?
Wenn ja hast du hier schon nen Denkfehler, wenn der Originalschlüssel nicht auch eine Primzahl ist.

Der_Gerhard · 05.10.2007, 20:43

Und derjenige, der die Zahlen verschlüsselt, ist wohl der Meinung, dass sie Dich nix angeht?

Hmmmm. Jede Zahl ist entweder selbst eine Primzahl oder das Produkt mehrerer Primzahlen. Wobei Du das jetzt darauf beschränken willst, dass jede Primzahl nur einfach enthalten sein darf?

Jede zu verschlüsselnde Zahl ist natürlich auch selbst eine Primzahl oder... naja, Du weißt vermutlich was jetzt kommt.

Bei 6 Primfaktoren würde ich mal auf 2^6 = 64 mögliche Kombinationen tippen, weil Du ja einfach für jede Zahl entscheiden musst, ob sie mit drin ist oder nicht.

moose · 05.10.2007, 20:47

kennst du http://www.bright-shadows.net/ ?
Das ist eine Verschlüsselung dort. In diesem fall sind die Ver- und Entschlüsselungsmethode und der "cipher text" (das verschlüsselte) gegeben, jedoch nicht der schlüssel.
Ja, ich mach das zum spaß und ich kenne auch gute verschlüsselungsmethoden. Ich habe auch das problem hier vereinfacht, weil ich es teilweise schon gelöst hab.

Ich will hier allerdings nicht die ganze aufgabe reinschreiben, da es eine gute seite ist von der die meisten lösungen noch nicht im internet sind (und das soll so bleiben). allerdings hab ich mir gedacht, dass ich diesen teilbereich ja hier reinschreiben kann, allerdings muss ich das anscheinend alleine machen ... naja, dann muss ich halt noch ne nacht drüber schlafen

trotzdem danke für eure aufmerksamkeit und hilfsbereitschaft

edit:

Zitat:

Hmmmm. Jede Zahl ist entweder selbst eine Primzahl oder das Produkt mehrerer Primzahlen. Wobei Du das jetzt darauf beschränken willst, dass jede Primzahl nur einfach enthalten sein darf?

Ich hab mich schon ne ganze weile mit dem thema beschäftigt, also glaub ich nicht das von der mathematischen seite noch was neues für mich kommt (aber für leser dieses themas ist es vielleicht nicht schlecht)

jedoch noch mal ein beispiel:
text: 123456 (kenn ich nicht)
key: 33 (kenn ich nicht)
verschlüsselt: 33 * 123456 = 2*2*2*2*2*2*3*3*11*643 (kenn ich)

da ich weiß: text * key = verschlüsselt
ist der key folglich eine beliebige kombination aus den primfaktoren des verschlüsselten. jedoch gibt es ne ganze menge von hier möglichen schlüsseln:
2
4
8
16
33
66
44
643
3
.....

ich hoffe nun ist es klar ^^

Zergling-new · 05.10.2007, 21:00

Ja, damit ist klar, dass dein verschlüsselter Text nicht mehr herzustellen ist, weil weder Text noch Key Primzahlen sind. Dass du das Ergebnis kennst ist egal.
Oder aber dein Beispiel ist schlecht gewählt (seltsam, wenn du dich doch damit auskennst) .. aber dann reden wir sowieso aneinander vorbei.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
[gelöst] Zahlen sortieren mit Varchar	moose	Datenbanken	8	21.07.2008 13:53
Zahlen mit 0 darstellen?	GSJLink	PHP Tipps 2007	5	02.04.2007 11:05
Vorkommnisse eines Begriffs in einem Tabellfeld zählen	R4v3r	Datenbanken	2	06.02.2007 18:19
Zahlen (Double) formatiert darstellen	Marie	PHP Tipps 2007	2	24.01.2007 22:32
Doppelte Einträge nur einmal Zählen	Zangelo	Datenbanken	2	06.12.2006 17:41
Zahlen mit <>= im negativen Bereich?	BartTheDevil89	PHP Tipps 2006	5	15.10.2006 00:22
Zahlen effektiv verschlüsseln	Jacks Rache	PHP Tipps 2006	20	10.07.2006 01:44
Zahlen zusammenzählen	Sonja	PHP Tipps 2006	11	28.03.2006 11:07
Zahlen eintragen	Skazi	Datenbanken	6	23.01.2006 09:10
Abfrage nur bei Zahlen?	BartTheDevil89	Datenbanken	3	27.11.2005 13:21
Wie prüfe ich einen String ob nur Zahlen enthalten sind ?		PHP Tipps 2005	7	31.05.2005 13:02
Zahlen aus Array löschen, die größer (kleiner) sind als X	R4v3r	PHP Tipps 2005	5	06.03.2005 19:00
[Erledigt] Bestimmte Zahlen in zufälliger Reihenfolge ausgeben		PHP Tipps 2004	12	15.09.2004 20:04
[Erledigt] Zählen wie viele Arrays bereits diesen Wert haben		PHP Tipps 2004	6	04.09.2004 01:04
[Erledigt] "echte" Downloads zählen: wie geht sowas?		PHP Tipps 2004	22	28.06.2004 09:50

05.10.2007, 18:53
moose Erfahrener Benutzer Registriert seit: 14.01.2006 Beiträge: 111	[Algorithmus-Problem] Primzahlarray, welche zahlen sind mgl Hi, ich habe einen array, in dem Primzahlen gespeichert sind: $primes = array(2,2,2,3,11,37); Nun will ich in einen zweiten array speichern, welche zahlen möglich sind (man muss nicht alle primzahlen benutzen), also: $numbers[] = 2; $numbers[] = 4; $numbers[] = 12;... ich bin mir relativ sicher dass man das Problem rekursiv angehen muss, allerdings is mir nur eingefallen wieviele zahlen es gibt ... (n²+n)/2, also im beispiel sollte $numbers 21 elemente haben. Momentan muss man bei mir die funktion dem array anpassen, und das gefällt mir gar nicht: PHP-Code: <? $a_numbers = arraymit3elementen(array(2,3,4)); function get_all_numbers($faktors){ $produkt = 1; foreach($faktors as $faktor){ $produkt = $faktor; $a_numbers[]=$faktor; } $a_numbers[] = $produkt; foreach($a_faktors AS $key=>$faktor1){ unset($a_faktors[$key]); foreach($a_faktors AS $faktor2){ $a_numbers[]=$faktor1$faktor2; } } return $a_numbers; } Vielleicht hilft jemanden dieses Schema, das ich mir überlegt hab (mir hats nicht geholfen): Array Faktors : abcde Array Numbers: abcde abcd abc ab a ------ bcde bcd bc b ----- cde cd c ----- de d ---- e Es gibt count($a_faktors)-1 dieser Blöcke und jeder block hat ein element weniger (also 5, 4, 3, 2, 1) __________________ http://www.martin-thoma.de


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

05.10.2007, 19:46
agrajag Moderator Registriert seit: 02.10.2006 Beiträge: 3.820 PHP-Kenntnisse: Fortgeschritten	Sorry, aber kannst du nochmal erklären was du machen willst? Du sprichst andauernd von Zahlen die möglich sind? Wie "möglich"? Vielleicht fängst du einfach mal ganz von vorne an: Was willst du erreichen? __________________ Today you...Tomorrow me.

05.10.2007, 20:13
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	Und das noch: http://www.lugbz.org/documents/smart...s_de.html#goal

05.10.2007, 20:16
moose Erfahrener Benutzer Registriert seit: 14.01.2006 Beiträge: 111	okay: Ich habe eine Verschlüsselung. Diese multipliziert am ende einen schlüssel mit einer zahl. Nun bekomme ich nur die verschlüsselte zahl und muss den schlüssel rausbekommen. Natürlich muss der Schlüssel dann ein Primfaktor beziehungsweise das Produkt mehrerer Primfaktoren sein. Ich habe eine Primfaktorzerlegung gemacht und will nun alle möglichen entschlüsselten texte herausbekommen. dazu muss ich die zahl, die vorher mit dem schlüssel multipliziert wurde durch den von mir vermuteten schlüssel teilen. Und zwar durch jeden schlüssel, der möglich ist, wenn ich garantieren will dass die lösung dabei ist. Ich hoffe ich habe mich nun deutlich ausgedrückt ... anscheindend denke ich im moment etwas wirr^^ __________________ http://www.martin-thoma.de

05.10.2007, 20:37
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	Das ist doch keine Verschlüsselung .. Benutz lieber Open-Source Algorithmen, deren Quellcode liegt offen und ist somit vielen kritischen Blicken ausgesetzt. Fehler und Schwachstellen sind deshalb meist schneller bekannt und gefixt als mißbraucht: http://www.phpfriend.de/forum/ftopic61226.html Blowfish ist denk ich OK. Oder machst du das zum Spass? Kann ich verstehen, fasziniert. Dann erklär aber nochmal genauer wie du ver- und entschlüsselst (ist ja anonym), hab das noch nicht so ganz verstanden. Du erstellst Text, verschlüsselst ihn "irgendwie" mit einem Schlüssel der beiden (Sender und Empfänger) bekannt sein muss, versteckst den verwendeten Schlüssel dann aber nochmal, in dem du ihn mit einer Primzahl multiplizierst? Wenn ja hast du hier schon nen Denkfehler, wenn der Originalschlüssel nicht auch eine Primzahl ist.

05.10.2007, 20:43
Der_Gerhard Erfahrener Benutzer Registriert seit: 08.11.2004 Beiträge: 2.079	Und derjenige, der die Zahlen verschlüsselt, ist wohl der Meinung, dass sie Dich nix angeht? Hmmmm. Jede Zahl ist entweder selbst eine Primzahl oder das Produkt mehrerer Primzahlen. Wobei Du das jetzt darauf beschränken willst, dass jede Primzahl nur einfach enthalten sein darf? Jede zu verschlüsselnde Zahl ist natürlich auch selbst eine Primzahl oder... naja, Du weißt vermutlich was jetzt kommt. Bei 6 Primfaktoren würde ich mal auf 2^6 = 64 mögliche Kombinationen tippen, weil Du ja einfach für jede Zahl entscheiden musst, ob sie mit drin ist oder nicht. __________________ ******************************** Nein, ich bin nicht die Signatur. Ich putze hier nur. ********************************

05.10.2007, 21:00
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	Ja, damit ist klar, dass dein verschlüsselter Text nicht mehr herzustellen ist, weil weder Text noch Key Primzahlen sind. Dass du das Ergebnis kennst ist egal. Oder aber dein Beispiel ist schlecht gewählt (seltsam, wenn du dich doch damit auskennst) .. aber dann reden wir sowieso aneinander vorbei.