Index-Calculus-Algorithmus - Versionsgeschichte

Benji104: /* 2. Schritt */

2024-11-02T07:58:45Z

2. Schritt

← Nächstältere Version		Version vom 2. November 2024, 09:58 Uhr
Zeile 21:		Zeile 21:
	<math>\alpha^s \beta = \prod \limits_{i=1}^{n_t} p_{i}^{b_i}</math><br>		<math>\alpha^s \beta = \prod \limits_{i=1}^{n_t} p_{i}^{b_i}</math><br>
	Es gilt:<br>		Es gilt:<br>
	<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{~~n_t~~} b_i \log_{\alpha} p_i - s \mod n</math>		<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \mod n</math>

	[[Kategorie:Zahlentheoretischer Algorithmus]]		[[Kategorie:Zahlentheoretischer Algorithmus]]

Benji104: /* 1. Schritt */

2024-11-02T07:42:29Z

1. Schritt

← Nächstältere Version		Version vom 2. November 2024, 09:42 Uhr
Zeile 8:		Zeile 8:
	=== 1. Schritt ===		=== 1. Schritt ===
	Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>		Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>
	<math>\alpha^{a} = \prod \limits_{i=1}^{~~n_t~~} p_{i}^{\lambda_{i}} </math>		<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}} </math>

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{~~n_t~~}\lambda_i \log_{\alpha} p_i \mod n</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

	Wenn eine genügend große Anzahl (<math>~~n_t >~~ t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>\ge t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

	=== 2. Schritt ===		=== 2. Schritt ===

Franz Scheerer aus Wiesbaden: /* 1. Schritt */ So ergibt es für mich mehr Sinn

2023-02-18T08:07:58Z

1. Schritt: So ergibt es für mich mehr Sinn

← Nächstältere Version		Version vom 18. Februar 2023, 10:07 Uhr
Zeile 8:		Zeile 8:
	=== 1. Schritt ===		=== 1. Schritt ===
	Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>		Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>
	<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}} ~~\mod n~~</math>		<math>\alpha^{a} = \prod \limits_{i=1}^{n_t} p_{i}^{\lambda_{i}} </math>

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod (n~~-1)~~</math>		<math>a \equiv \sum \limits_{i=1}^{n_t}\lambda_i \log_{\alpha} p_i \mod n</math>

	Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>n_t > t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

	=== 2. Schritt ===		=== 2. Schritt ===
Zeile 19:		Zeile 19:
	<math>\beta \in G</math> ist gegeben.		<math>\beta \in G</math> ist gegeben.
	Es werden solange Zufallszahlen <math>s</math> gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus <math>S</math> schreiben lässt:<br>		Es werden solange Zufallszahlen <math>s</math> gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus <math>S</math> schreiben lässt:<br>
	<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>		<math>\alpha^s \beta = \prod \limits_{i=1}^{n_t} p_{i}^{b_i}</math><br>
	Es gilt:<br>		Es gilt:<br>
	<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \mod n</math>		<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{n_t} b_i \log_{\alpha} p_i - s \mod n</math>

	[[Kategorie:Zahlentheoretischer Algorithmus]]		[[Kategorie:Zahlentheoretischer Algorithmus]]

Datesa: /* 1. Schritt */ mod n ist gleich mod (n-1) im Exponenten.

2020-07-15T11:27:35Z

1. Schritt: mod n ist gleich mod (n-1) im Exponenten.

← Nächstältere Version		Version vom 15. Juli 2020, 13:27 Uhr
Zeile 8:		Zeile 8:
	=== 1. Schritt ===		=== 1. Schritt ===
	Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>		Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>
	<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>		<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}} \mod n</math>

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod (n-1)</math>

	Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

Leryra: Änderung 136649159 von Leryra rückgängig gemacht; ich hatte was übersehen.

2014-12-10T15:11:10Z

Änderung 136649159 von Leryra rückgängig gemacht; ich hatte was übersehen.

← Nächstältere Version		Version vom 10. Dezember 2014, 17:11 Uhr
Zeile 11:		Zeile 11:

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \~~pmod{~~n~~-1}~~</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

	Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.
Zeile 21:		Zeile 21:
	<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>		<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>
	Es gilt:<br>		Es gilt:<br>
	<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \~~pmod{~~n~~-1}~~</math>		<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \mod n</math>

	[[Kategorie:Zahlentheoretischer Algorithmus]]		[[Kategorie:Zahlentheoretischer Algorithmus]]

Leryra: mod n war falsch, schon in Z/nZ stimmt das nicht, es soll mod n-1 sein

2014-12-10T14:15:16Z

mod n war falsch, schon in Z/nZ stimmt das nicht, es soll mod n-1 sein

← Nächstältere Version		Version vom 10. Dezember 2014, 16:15 Uhr
Zeile 11:		Zeile 11:

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i ~~\mod~~ n</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \pmod{n-1}</math>

	Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.
Zeile 21:		Zeile 21:
	<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>		<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>
	Es gilt:<br>		Es gilt:<br>
	<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \~~mod~~ n</math>		<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \pmod{n-1}</math>

	[[Kategorie:Zahlentheoretischer Algorithmus]]		[[Kategorie:Zahlentheoretischer Algorithmus]]

Quartl: /* Vorgehensweise */ links

2013-05-07T05:22:21Z

Vorgehensweise: links

← Nächstältere Version		Version vom 7. Mai 2013, 07:22 Uhr
Zeile 3:		Zeile 3:

	== Vorgehensweise ==		== Vorgehensweise ==
	Es sei <math>G</math> eine endliche [[~~Gruppentheorie\|~~zyklische Gruppe]] der [[Ordnung]] <math>n</math>, die durch <math>\alpha</math> erzeugt wird.<br>		Es sei <math>G</math> eine endliche [[zyklische Gruppe]] der [[Gruppenordnung\|Ordnung]] <math>n</math>, die durch <math>\alpha</math> erzeugt wird.<br>
	Es sei <math>S= \{p_{1},p_{2},...,p_{t}\}</math> (die ''Faktorbasis'') eine [[Untermenge]] von <math>G</math> mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente in <math>S</math> schreiben lässt.		Es sei <math>S= \{p_{1},p_{2},...,p_{t}\}</math> (die ''Faktorbasis'') eine [[Untermenge]] von <math>G</math> mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente in <math>S</math> schreiben lässt.

Zeile 10:		Zeile 10:
	<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>		<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>

	Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

KLBot2: Bot: 3 Interwiki-Link(s) nach Wikidata (:d:Q657705) migriert

2013-04-03T10:10:51Z

Bot: 3 Interwiki-Link(s) nach Wikidata (d:Q657705) migriert

← Nächstältere Version		Version vom 3. April 2013, 12:10 Uhr
Zeile 24:		Zeile 24:

	[[Kategorie:Zahlentheoretischer Algorithmus]]		[[Kategorie:Zahlentheoretischer Algorithmus]]

	[[en:Index calculus algorithm]]
	[[he:תחשיב אינדקסים]]
	[[nl:Indexcalculusalgoritme]]

Oktavianus: math-Mode an fehlenden Stellen ergänzt

2012-05-31T16:04:52Z

math-Mode an fehlenden Stellen ergänzt

← Nächstältere Version		Version vom 31. Mai 2012, 18:04 Uhr
Zeile 7:		Zeile 7:

	=== 1. Schritt ===		=== 1. Schritt ===
	Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis S zu schreiben:<br>		Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>
	<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>		<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>

Zeile 16:		Zeile 16:

	=== 2. Schritt ===		=== 2. Schritt ===
	In diesem Schritt werden die individuellen Logarithmen in G berechnet.		In diesem Schritt werden die individuellen Logarithmen in <math>G</math> berechnet.
	<math>\beta \in G</math> ist gegeben.		<math>\beta \in G</math> ist gegeben.
	Es werden solange Zufallszahlen s gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus S schreiben lässt:<br>		Es werden solange Zufallszahlen <math>s</math> gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus <math>S</math> schreiben lässt:<br>
	<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>		<math>\alpha^s \beta = \prod \limits_{i=1}^{t} p_{i}^{b_i}</math><br>
	Es gilt:<br>		Es gilt:<br>

Oktavianus: /* 1. Schritt */ Kommas ergänzt

2012-05-31T15:59:46Z

1. Schritt: Kommas ergänzt

← Nächstältere Version		Version vom 31. Mai 2012, 17:59 Uhr
Zeile 10:		Zeile 10:
	<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>		<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}}</math>

	Wenn eine entsprechende Darstellung gefunden wurde kann eine [[Kongruenz\|lineare Kongruenz]] gebildet werden.<br>		Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz\|lineare Kongruenz]] gebildet werden.<br>
	<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>		<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

	Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.		Wenn eine genügend große Anzahl (<math>> t</math>) an [[Relation (Mathematik)\|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem\|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

	=== 2. Schritt ===		=== 2. Schritt ===