Laden...

Zufalls(prim)zahl mit 512-1024 bits...

Erstellt von stellina vor 18 Jahren Letzter Beitrag vor 17 Jahren 14.109 Views
S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren
Zufalls(prim)zahl mit 512-1024 bits...

Hallo, ich hab ein kleines (oder doch großes Problem)

Ich soll in C# zwei Zufallsprimzahlen erzeugen, (beide circa gleich groß) und das Produkt der beiden Primzahl soll dann genau die Anzahl an Bits haben, die ich vorher eingegeben habe.

d.h. im normalfall sind es 1024 bits, und ich muss dann zwei Primzahlen erzeugen, die je (etwa) 512 bits haben und das Produkt der beiden soll dann auf jeden fall genau 1024 bits haben!

Nur irgendwie weiß ich nicht wie ich das machen soll.
Uns wurde erklärt, dass wir zwei Strings erzeugen sollen und diesen müssen wir dann mit Zufallszahlen füllen. (falls einer der beiden Strings kleiner also weniger Elemente enthält als der andere, muss dieser mit Nullen aufgefüllt werden.)
Die zwei Strings sollen dann (komponentenweise) addiert werden und das solange bis man eben die gewünschte bit länge hat.

So habe ich die Anleitung verstanden, nur mit der umsetzen gibts noch heftigste Probleme, da ich noch nie objektorientiert programmiert habe und noch nie mit C# zu tun hatte...

Wäre super falls mir jemand von euch helfen könnte!

Danke

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,

ich könnte es Programmieren, da ich noch schon viel objektorientiert programmiert habe und schon oft mit C# zu tun hatte... aber ich have die Anleitung nicht verstanden.

herbivore

2.921 Beiträge seit 2005
vor 18 Jahren

Und was hat Dein Chef/Auftraggeber sonst noch für Hobbies? Sowas. Ts.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

2.921 Beiträge seit 2005
vor 18 Jahren

Ich schon. Sie soll große Primzahlen errechnen. Ich nehme mal an die Chars sind die Bits daran. also 1 Zeichen 1 Byte (8 Bits).

512/8 = 64

also soll sie 1. eine Primzahl mit 64 Zeichen Länge haben
also soll sie 2. ebenfalls eine Primzahl mit 64 Zeichen Länge haben.

und diese beiden sollen multipliziert eine Länge von 128 Zeichen (128*8 = 1024 Bits) haben.

Stimmt das so ungefähr? @stellini

Sag dem Typ mal dass das keine einfache Aufgabe ist.

Ich weiß zufällig ich das bisher die größte bekannte Primzahl immer eine Mersenne Primzahl war und bisher keiner geschafft hat eine Primzahl-Formel zu entwickeln die 100% zuverlässig ist. Deshalb werden die ja immer mit Computern angenähert.
Ist auch nicht ganz so einfach im I-Net was dazu zu finden. Ich hatte schon mal an einem solchen Wettbewerb mitgemacht, daher weiß ich das.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo dr4g0n76,

unter C# sind Zeichen in Strings Unicode 2byte = 16bit.

Was ich z.B. nicht verstanden habe ist, wenn ich Zufallsstrings bilde, sind das doch nicht automatisch Primzahlen, wenn man mit Nullen auffüllt schon gar nicht.

herbivore

308 Beiträge seit 2005
vor 18 Jahren

Hallo Herbivore,

zwar sind zeichen per default Unicode, aber wenn man einen string nur aus Zeichen der CodePage 1252 (standard windows, deutsch) enthält bekommt man mit Encoding.Default.GetBytes(unicodeString) ein Byte-Array in dem jedes Zeichen ein Byte belegt.

Für Verschlüsselungen arbeitet man eh (fast) immer mit Byte- oder Bit-Streams und nicht mit Strings....

Wie man allerdings das problem mit den Primzahlen löst!?

ok, ich würde cheaten! einfach links mit Nullen padden! Steht doch nirgendwo, dass das Most-Significant-Bit das 1024. sein mus, oder?! Die Zahl Null ist als byte acht bit, als Int32 32 bit etc....
d.h.
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 * 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

1*1 = 1
Gelöst!!!

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

ja ich kenn mich leider auch nicht so gut aus, wenn ichs mir aussuchen könnte würd ich das am liebsten natürlich gar nicht machen.

Wie das mit den bits und so aussieht weiß ich nicht also in bezug auf die char und so... (ich weiß nur die zahl 4 hat zB 2 bits gg wegen 2^2)

und mein vortragender hat mir erklärt dass ich zwei strings brauche in denen zufallszahlen stecken und die zwei strings muss ich dann komponentenweise addieren (und dann modulo 10 nehmen, damit sich das ganze wieder im bereich 0-9 abspielt), damit ich dann zu ner großeren zahl komme.

ich hätte dann anschließens geprüft ob die erhaltene zahl dann eine primzahl ist und wenn nicht solange rechnen lassen bis er eine primzahl erwischt hat.

wie gesagt in der theorie würd ichs so tun, beim umsetzen ist nur mehr ein großes fragezeichen da gg

und es kann sehr wohl sein dass ich irgendetwas falsch verstanden habe, nur im endeffekt muss ich das RSA verschlüsselungsverfahren im c# programmieren und für jemanden der noch nie in der sprache programmiert hat, ist das doch eine etwas heftige angelegenheit (besonders wenn in der EINZIGEN vorlesung nur erklärt wurde wie man natürliche zahlen addieren, subtrahieren etc kann...)

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,

dann programmier es mal in einer Sprache deiner Wahl. Ich denke den Code umzusetzten ist einfacher, als hier noch lange darüber zu spekulieren, was eigentlich getan werden soll. Oder schreib es zumindest in Pseudocode.

Dir ist aber schon klar, dass die klassische Prüfung IstPrimzahl bei so großen Zahlen ein paar Jahre dauert? (Ok, Jahre ist übertrieben)

herbivore

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

na ja es geht darum dass ich noch nie objektorientiert gearbeitet habe, nur in derive und derive is für mathematische sachen wie Primzahlen berechnen (auch wenn die nochsoviele bits haben müssen) ein absoluter traum, also bringt mir die sprache meiner wahl so gut wie gar nichts...

in c# gibt es ja keinen eigenen befehl (wie zB random für zufallszahlen) um primzahlen zu bekommen?!

In erster linie geht es darum dass ich es mal schaffe zwei strings komponentenweise zu addieren, das mit den primzahlen is noch grad nicht so wichtig, weil ichhab den vortragenden gefragt wie ich eben so lange zahlen zusammenkriegen soll mit C#, und er meinte das geht so irgendwie und quasi als aufgabe muss ich das bis morgen irgendwie "ausprobiert" haben, nur in die sprache hab ich mich noch nicht richtig eingelebt und da ich heute eine prüfung hatte, bin ich auch nicht so wirklich dazu gekommen...

beim probieren hat eine freundin und ich das zusammengebracht:
static void Main()
{
Application.Run(new Form1());
}

	private void Form1_Load(object sender, System.EventArgs e)  
	{  
	  
		Random s1 = new Random();    
		Random s2 = new Random();  
		string t1 = Convert.ToString(s1.Next());   
		string t2 = Convert.ToString(s2.Next());  
		this.textBox1.Text = t1;  
		this.textBox2.Text = t2;   

Das Problem dabei ist nur, dass die zwei Zufallszahlen immer gleich sind...

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,


Random rand = new Random();
string t1 = Convert.ToString(rand.Next());
string t2 = Convert.ToString(rand.Next());
this.textBox1.Text = t1;
this.textBox2.Text = t2; 

herbivore

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,

Grosse Zahlen

herbivore

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

okay, danke

gesamt sieht das ganze jetzt so aus

		static void Main() 
		{
			Application.Run(new Form1());
		}

		private void Form1_Load(object sender, System.EventArgs e)
		{
			Random rand = new Random();
			string t1 = Convert.ToString(rand.Next());
			string t2 = Convert.ToString(rand.Next());
			this.textBox1.Text = t1;
			this.textBox2.Text = t2; 


		}
		private string Zahlen(string t1,string t2)
		{
			t1 = t1.PadRight(t2.Length);
			t2 = t2.PadRight(t1.Length);
			int Hilfserg;
			int uebertrag = 0;
			string erg = String.Empty; 
			for (int i=0;i < t2.Length; i++)
			{
				int hilfs1 = Convert.ToInt16(t1[i]);
				int hilfs2 = Convert.ToInt16(t2[i]);
				Hilfserg = (hilfs1 + hilfs2 +uebertrag) % 10;
				uebertrag = (hilfs1 + hilfs2 + uebertrag) / 10;
				erg[i] = Convert.ToString(Hilfserg);
			}
			return erg; 
  

(ich hoffe das haut mit so nem kästchen jetzt auch hin gg

mit dem erg_ versuchen wir quasi das i-te Element dem erg zuzufügen....

bei dem Convert.toString kommt nur folgende fehlermeldung:
impliziete Konvertierung des Typs "string" zu "char" nicht möglich

und zu erg_ kommt:
Einer Eigenschaft oder einem Indexer "string.this[int]" kann nicht zugewiesen werden..

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,

ich würde es nicht mit Strings machen, sondern mit byte-Arrays (oder eben mit BigInt).

Dann geht das ganze recht einfach: Random.NextBytes

herbivore

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

das problem ist nur dass unser vortragender gemeint hat dass wir das mit nem string machen müssen, und er will das immer so wie er gesagt hat (es ist so schon schwer genug es ihm recht zu machen 🙁 )

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo stellina,

sorry, wenn man die Wahl hat, zwischen Strings und byte-Array, dann ist es Schwachsinn (noch mal sorry) Strings zu benutzen.

Aber bitte, man kann ein byteArray ganz locker in einen String umwandeln: Encoding.GetString.

herbivore

I
1.739 Beiträge seit 2005
vor 18 Jahren

Ich vermisse jetzt irgendwie den Bezug zu Primzahlen?.

>in c# gibt es ja keinen eigenen befehl (wie zB random für zufallszahlen) um >primzahlen zu bekommen?!

Na ich dachte das wär Teil der Aufgabe.

Hier etwas Google-Futter:
Fermat-Test,
Lucas-Lehmer-Test,
Miller-Rabin-Test,
Solovay-Strassen-Test,
Sieb des Eratosthenes,
Wikipedia Primzahl

Wenn echte Berechnung nicht gefragt ist kann man auch auf Tabellen zugreifen, Wertebereich auswählen->Zufallszahl ermitteln(da sind wir wieder bei Primzahlaritmethik: Wie zufällig solls sein?)

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

so zufällig damit das RSA Verfahren danach hinhaut

na ja man muss sich ja mal klein vorarbeiten

im großen und ganzen soll ich mir mit der methode dann zwei primzahlen berechnen können, und auf den weg dorthin hat unser vortragender eben gemeint wir sollen einmal eine funktion schreiben wo wir quasi zwei strings ertsellen müssen, in denen zufallszahlen stecken und der kürzere string soll mit nullen aufgefüllt werden damit die gleich lang sind und dann muss man diese zwei strings komponentenweise addieren und das ergebnis modulo 10 nehmen (damit man wieder eine zahl zwischen 0 und 9 hat) und in einen neuen string rienplazieren, somit erhält man dann einen größeren string und damit kommen wir dann anscheinend den größeren zahlen im bezug auf die bits näher

so hab ich das verstanden und momentan sind wir noch in der umsetzung von der gestellten "kleinaufgabe"

deswegen können wir uns nicht einfach aussuchen mit was wir das machen 🙁

I
1.739 Beiträge seit 2005
vor 18 Jahren

Na dann ist ja alles klar. Mit den Strings hat herbivore geholfen. Arrays sind halt besser zu handlen(irgenwie ist ein String ein CharArray). Demontier ihn(den String).
Char2Byte und % ist auch recht simpel.
Zufallszahlen: nimm nicht die Randomklasse, wenn du "gute" Zufallszahlen brauchst. Stichwort: CryptoAPI(Oder. Net Cryptography- Namespace).

ps:
RSA: Prima Sache für Shakehands und gleichfolgendes Umschalten auf AES/Rijandel. (nur wenns um echte Komm. geht). Für Anmeldung oder Signaturen , asynchr. Komm siehts anders aus.

Wenn du noch Fragen zu Details hast, wie Typumwandlung unter C# oder sonstige Sprachtypische Eigenheiten der Programmierung, helfen wir gern.

Ansonsten: hausaufgaben.de(Sorry, sah ein wenig danach aus).

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

So ist der aktuelle stand:

				static void Main() 
		{
			Application.Run(new Form1());
		}

		private void Form1_Load(object sender, System.EventArgs e)
		{
			Random rand = new Random();
			string t1 = Convert.ToString(rand.Next());
			string t2 = Convert.ToString(rand.Next());
			int [] Ergeb = Zahlen(t1, t2);
 			this.textBox1.Text = t1;
			this.textBox2.Text = t2; 
			for (int i = 0; i < Ergeb.Length; i++)
			{
				
				this.textBox3.Text += Convert.ToString(Ergeb[i]); 

			}
			}
		private int[] Zahlen(string s1,string s2)
		{
			if (s2.Length > s1.Length) {
				s1 = s1.PadLeft(s2.Length + 1);
				s2 = s2.PadLeft(1);
				}
			if (s2.Length < s1.Length)
			{
				s2 = s2.PadLeft(s1.Length);
				s1 = s1.PadLeft(1);
			}
			int i = s1.Length-1; 
			int Hilfserg;
			int uebertrag = 0 ;
			int[] erg = new int [i+1];
			for (i= s1.Length-1;i <=0; i--)
			{
				int hilfs1 = Convert.ToInt16(s1[i]);
				int hilfs2 = Convert.ToInt16(s2[i]);
				Hilfserg = (hilfs1 + hilfs2 +uebertrag) % 10;
				uebertrag = (hilfs1 + hilfs2 + uebertrag - Hilfserg)/ 10;
				erg[i] = Hilfserg;
			}
			return erg; 
			}
		}
	}

Okay jetzt ist "einiges" verändert worden, nur eine Frage, wieß jemand wie ich einen string links mit Nullen auffüle (in unserem beispiel wird der string mit leerzeichen aufgefüllt, jedoch wollen wir es mal mit nullen probieren.)

danke

3.728 Beiträge seit 2005
vor 18 Jahren
Replace

Hallo stellina,

Du könntest die Leerzeichen mit String.Replace in Nullen umwandeln.

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

dankeschön
das ganze ist jetzt noch mehr umgeändert worden und jetzt funktionier es endlich

danke nochmal an alle die geholfen haben!

1.271 Beiträge seit 2005
vor 18 Jahren

Erst mit Leerzeichen auffüllen und dann die Leerzeichen durch Nullen zu ersetzen ist ein wenig umständlich. Nimm halt einfach .PadLeft(...,'0');

A wise man can learn more from a foolish question than a fool can learn from a wise answer!
Bruce Lee

Populanten von Domizilen mit fragiler, transparenter Außenstruktur sollten sich von der Translation von gegen Deformierung resistenter Materie distanzieren!
Wer im Glashaus sitzt, sollte nicht mit Steinen werfen.

S
stellina Themenstarter:in
15 Beiträge seit 2005
vor 18 Jahren

okay dankeschön...

Q
992 Beiträge seit 2005
vor 18 Jahren

Ich habe mir nochmal die BigInt Klasse angeguckt.
Das könnte helfen, ich habe allerdings nur ganz kurz reingeschaut.

http://www.codeproject.com/csharp/BigInteger.asp#PrimalityTest

B
2 Beiträge seit 2006
vor 17 Jahren

Hallo ich bin neu hier und weiß nicht ob die Frage hier reinpasst.

Ich hab ein ähnliches Problem.

Ich muss zwei zufällige Primzahlen erzeuge. Wie ich "normale" Zahlen erzeuge ist mir klar, aber kann mir vielleicht jemand erklären wie ich Primzahlen erzeuge?

Danke BlueJayes

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo bluejayes,

große oder kleine Primzahlen? Wertebereich?

herbivore

564 Beiträge seit 2006
vor 17 Jahren

Hi!

Ich habe den Thread mal eben kurz überflogen.
Es gibt einige mathematische Bedingungen (Formeln), bei denen Primzahlen herauskommen. *4k+1 *4k+3 *6k+-1

Hier der Link zur Wikipedia

Vielleicht hilft euch das ein Stück weiter. Im Prinzip könnte man ja k mit einer Zufallszahl füllen. 🙂

der Marcel

:] 😄Der größte Fehler eines modernen Computers sitzt meist davor 😁 :]

B
2 Beiträge seit 2006
vor 17 Jahren

Die Primzahlen sollen beliebig groß sein und ich soll die Bitlänge von den Primzahlen eingeben.

Ich hab das Programm schon in Derive programmiert und muss das gleich ich CSharp machen. Ich Derive ist es mir aber wesentlich leichter gefallen 😉

BlueJayes