Diskussion:Pseudoprimzahl/Archiv

Art der Pseudoprimzahlen

Welche Art von Pseudoprimzahlen sind in der Liste? --Hutschi 14:54, 6. Apr 2004 (CEST)

Alle Pseudoprimzahlen der Art n für die gilt:

b^{n-1}-1\equiv 0\mod n

mit 1 < b < n und b ist eine natürliche Zahl (um genauer zu sein b ist eine Primzahl). --Arbol01 15:05, 6. Apr 2004 (CEST)

Nachtrag: Ich sehe nicht ein, Zahlen in die Pseudoprimzahl-Tabelle aufzunehmen, die nur pseudoprim zu Nichtprimzahlen sind, wie die 35, die nur zur 6 pseudoprim ist, oder die 33, die nur zur 10 pseudprim ist. --Arbol01 15:17, 6. Apr 2004 (CEST)

Habe ich keine Probleme mit. --Hutschi 15:30, 6. Apr 2004 (CEST)

Soll ich denn dazu schreiben, das die Basen b alle Primzahlen sind? --Arbol01 15:34, 6. Apr 2004 (CEST)

gern / bitte auch den Text mal prüfen. --Hutschi 15:35, 6. Apr 2004 (CEST)

Asche auf mein Haupt! Ich habe eine meiner unvollständigen PSPR-Listen verwendet. 35 ist auch eine PSPR und einige mehr. Die Tabelle werde ich später vervollständigen. --Arbol01 15:54, 6. Apr 2004 (CEST)

Unterschied

Ich frage mich, ob es wirklich einen Unterschied zwischen den Pseudoprimzahlen so wie ich sie kenne, also die, die aus dem kleinen Fermatschen Satz hervor gebracht worden sind, und den anderen Spielarten der Pseudoprimzahlen gibt?

Carmichael-Zahlen sind übrigens eine echte Teilmenge der "Fermatschen" Pseudoprimzahlen. --Arbol01 00:41, 7. Apr 2004 (CEST)

Wozu braucht man Pseudoprimzahlen?

Und wenn mir jetzt noch einer im ersten Satz erklärt, wozu man die Dinger überhauptbraucht bzw. warum sie relevant sind, wärs rund. Gruss ThomasSD 00:42, 7. Apr 2004 (CEST)

Von Benutzer Diskussion:ThomasSD hierher kopiert. --Sikilai 09:26, 7. Apr 2004 (CEST)

Bist Du wirklich ein Informatikstudent? Nun, ein Jurist und Hobby-Mathematiker namens Pierre de Fermat hat einen satz aufgestellt: Für jede Primzahl p gilt, das

b^{p-1}\equiv 1\mod p

für jede Basis 1 < b < p und b ist eine natürliche Zahl. Oder im Programmierstil:

b^{p-1}\mod p==1

. Wenn man diesen Sachverhalt umkehren könnte, wenn man also sagen könnte, daß für ein beliebiges n, daß die Eigenschaft

b^{n-1}\equiv 1\mod n

gilt, n eine Primzahl ist, dann hätte man einen prima Primzahlgenerator, und die ganze Verschlüsselung über große Primzahlen wäre Essig.

Es ist aber nicht so, das jede Zahl n, die die Fermat-Eigenschaften hat eine Primzahl ist. Das interessante ist, das Primzahlen, und auch dei Pseudoprimzahle völlig unberechenbar sind.

Wenn man nämlich ein Schema aufstellen könnte, mit dem man vorhersehen könnte, wo wann die Pseudoprimzahlen zwischen den Primzahlen auftauchen, wäre auch schon einiges gelöst.

Einen geldwerten Vorteil aus den Pseudoprimzahlen, Carmichael-Zahlen und was da noch so keucht und fleucht zu holen, kann ich nicht nennen. --Arbol01 01:15, 7. Apr 2004 (CEST)

Ja, ich bin wirklich einer, schreibe an meinem Diplom und habe bis jetzt nichts über Pseudoprimzahlen gehört. Ich hoffe, das erschüttert dich jetzt nicht all zu sehr ^^ :P. Verstanden hab ich jetzt, was PPZ sind,danke. Vieleicht sollte man das mit dem Verschlüssungsalgorithmus / Zufälligkeit noch irgenwie im Artikel erwähnen, sowas würzt den artikel, oder? Gruss Thomas...

Ich kopiere dies mal nach Diskussion:Pseudoprimzahl. Dort gehört es schließlich hin und macht dort auch Sinn. --Sikilai 09:26, 7. Apr 2004 (CEST)

Liste aller Pseudoprimzahlen bis …

Das werden ja immer mehr und die obere Grenze wird immer kleiner. Ist es da nicht bald sinnvoller, die Nicht-Pseudoprimzahlen bis … aufzuzählen? ;) --Sikilai 09:13, 7. Apr 2004 (CEST)

Jetzt werden es nicht mehr. Ich habe die Tabelle abgeschlossen. Man soll ja nicht glauben, wie viele Pseudoprimzahlen es wirklich gibt. Wenn man tsors Artikel über den Fermatschen Primzahltest ließt, müßten das ja ganz wenige sein. --Arbol01 09:33, 7. Apr 2004 (CEST)

In dem Artikel steht, dass es nur sehr wenige Carmichael-Zahlen gibt. Das sieht man ja auch in Deiner Tabelle. -- tsor 17:13, 7. Apr 2004 (CEST)

Nunja, ich kann die Liste ja bis ca. 20.000 ereitern. --Arbol01 17:27, 7. Apr 2004 (CEST)

Eine solche Liste halte ich für weniger sinnvoll. In Fermatscher Primzahltest steht, dass nur 16 Zahlen < 100000 auch Carmichael-Zahlen sind. Diese sind dort auch aufgeführt. -- tsor 17:31, 7. Apr 2004 (CEST)

Das war auch nur eine rethorische Frage. Pseudoprimzahlen != Carmichael-Zahlen. --Arbol01 17:46, 7. Apr 2004 (CEST)

Noch ein Zitat aus Fermatscher Primzahltest:

C.Pomerance, J.L.Selfridge und S.S.Wagstaff Jr. zeigten im Jahre 1980, dass es unterhalb von 25.000.000.000 zwar 1.091.987.405 Primzahlen, aber nur 21.853 Pseudo-Primzahlen zur Basis 2 gibt.

http://www.tu-chemnitz.de/informatik/HomePages/ThIS/Seminare/ws01/EffAlg/Primzahlverfahren.PDF

http://www.hipilib.de/prime/primality-tests-on-commutator-curves.pdf

-- tsor 21:47, 7. Apr 2004 (CEST)

Schön, es gibt die seltenen Carmichael-Zahlen, und die Pseudoprimzahlen zur Basis 2, die ebenfalls selten sind.

Aber es gibt auch die Pseudoprimzahlen zur Basis p, wobei p eine Primzahl ist, und davon gibt es nun jede Menge, wenn auch nicht alle die Qualität der Pseudoprimzahlen zur Basis 2 haben, geschweige der der Carmichael-Zahlen. Aber sie gibt es. Sogar die meisten ungeraden Quadratzahlen fallen darunter. --Arbol01 22:33, 7. Apr 2004 (CEST)

zu Modulo

Wenn irgendwo ein Satz steht wie $b^{n-1}\equiv 1\mod n$ so bedeutet das nichts anderes, als populär ausgeschrieben: $(b^{n-1}\mod n)=(1\mod n)$ . Und da $1\mod n$ für alle n > 1 gleich 1 ist, könnte man populär schreiben $b^{n-1}\mod n=1$ . Da aber Wikipidia einen enzyklopedischen Anspruch erhebt, ist es geboten, die korrekte Mathematische Schreibweise zu benutzen. --Arbol01 13:38, 7. Apr 2004 (CEST)

Zustimmung Stern 14:05, 7. Apr 2004 (CEST)

Struktur der Artikel

M.E. ist die derzeitige Struktur noch nicht optimal. Zunächst gibt es Fermatscher Primzahltest. Hier wird die Bedeutung der Carmichael-Zahlen und der Pseudoprimzahlen im Zusammenhang beschrieben. Man erkennt (hoffentlich), wozu die Pseudoprimzahlen gut sind. Dies kann man wohl noch klarer darstellen.

Danach hat man eigene Artikel Pseudoprimzahl und Carmichael-Zahl angelegt und die Infos aus dem Fermat-Artikel kopiert, und natürlich noch ein wenig ergänzt. Allerdings wird in diesen Artikeln nicht klar, wozu Pseudoprimzahl und Carmichael-Zahlen vewendet werden - diese Frage wurde ja oben auf dieser Diskussionsseite auch gestellt.

Derzeit haben wir viele Informationen also doppelt, nämlich im Fermat-Artikel und in den beiden Einzelartikeln. Das ist nicht so toll.

Mein Vorschlag: Man arbeitet die wichtigen Zusatzinfos in Fermatscher Primzahltest ein und trägt in die Einzelartikel einen redirect ein.

Auf die Tabelle mit den Pseudoprimzahlen würde ich verzichten, die bringt in dieser Form nicht viel. Statt dessen könnte man noch ein oder zwei konkrete Beispiele für Pseudoprimzahlen darstellen (zur verschiedenen Basis b).

Gruss tsor 09:45, 8. Apr 2004 (CEST)

Darf ich das "Kompliment" zurückgeben? Die Artikel Pseudoprimzahl und Carmichael-Zahl habe ich deswegen in das Leben gerufen, gerade weil ich mit dem Artikel Fermatscher Primzahltest nicht zufrieden bin. Zuerst wird dort nämlich der Spezialfall "Carmichael-Zahl" als Pseudoprimzahl abgehandelt, und erst später die eigentliche "fermatsche" Pseudoprimzahl.

Ich wäre dafür, wenigstens den Artikel Carmichael-Zahl als eigenen Artikel (analog zu anderen Wikipedia) zu belassen.

Die Tabelle mit allen Pseudoprimzahlen halte ich sehr wohl für wichtig, da sich der interessierte ein Bild machen kann, was für lapidare Zahlen (15, 21, 49, 105) unter den Begriff Pseudoprimzahlen fallen. Die Tabelle könnte natürlich noch gekürzt werden, vielleicht bis zur 1200 (damit die 1105 noch mit drin ist). In der englischen Wikipedia ist auch eine, wenn auch nicht so lange Tabelle, mit nicht weniger lapidaren Zahlen.

Im Moment bin ich nicht bereit, in den Artikel Fermatscher Primzahltest etwas einzutragen, da ich ansonsten mit der Axt auf die Struktur losgehen müßte.

Gruß Arbol01 14:32, 8. Apr 2004 (CEST)

Eigenschaften von Pseudoprimzahlen

Im artikel steht, das die PPZ ähnliche Eigenschaften wie Primzahlen haben. Welche denn? Vielleicht wird es ja aus der Formel heraus klar, nur versteh ich dich als Nichtmathefreak nicht.. --Joh3.16 09:26, 15. Apr 2004 (CEST)

Zu jeder Primzahl p gibt es eine bestimmte Anzahl Basen a im Intervall 1<a<p oder a = [2;p-1]. Fuer die Primzahl 5 sind das die Basen 2, 3 und 4, fuer die gilt $a^{p}\mod p=a\mod p$ beziehungsweise $a^{p-1}\mod p=1\mod p$ . Wenn es nun fuer eine Nichtprimzahl n mindestens eine Basis a gibt, die kleiner als n aber groesser als 1 ist, so das fuer diese bestimmte Basis gilt: $a^{n-1}\mod n=1\mod n$ so ist die Nichtprimzahl n eine Pseudoprimzahl, und sie ist pseudoprim zur Basis a. Das ist alles, was fuer eine Pseudoprimzahl notwendig ist. Ob eine Pseudoprimzahl dann auch noch eine Eulersche oder andere Pseudoprimzahl ist, ist dann eine andere Sache. --Arbol01 18:12, 15. Apr 2004 (CEST)

Tabelle ausgelagert

Ich lagere die Tabelle aller Pseudoprimzahen hier auf die Diskussionsseite aus:

15	21	25	33	35	45	49	52	57	65	66	69	70	77	85	87	91	93	99
105	111	117	121	123	124	130	133	135	143	145	147	148	153	154	155	159	161	165
169	171	175	176	185	186	187	190	195	205	208	217	221	225	231	237	238	244	245
246	247	249	255	259	261	265	267	268	273	275	276	285	286	287	289	291	292	297
301	305	310	315	316	322	325	329	333	335	339	341	343	344	345	351	357	361	363
364	365	366	369	370	371	375	377	385	388	391	393	396	399	403	405	406	412	415
417	418	425	426	427	429	430	435	436	437	441	445	448	451	455	459	465	469	471
475	477	481	483	485	493	495	496	505	506	507	511	513	519	525	527	529	532	533
537	539	545	549	553	555	556	559	561	565	568	573	581	585	589	592	595	597	598
603	604	605	606	609	615	616	625	627	629	633	635	637	638	645	646	649	651	652
657	663	665	670	671	676	679	682	685	687	688	689	693	697	699	700	703	705	711
715	717	721	724	725	726	730	735	741	742	745	749	753	754	759	763	765	772	775
777	781	782	785	786	790	793	795	801	803	804	805	806	813	817	819	825	826	833
836	837	841	843	844	845	847	855	861	865	867	868	871	873	874	875	879	885	889
891	895	897	901	903	904	905	906	909	910	913	916	921	925	931	945	946	949	952
957	959	961	965	969	970	973	975	976	981	985	987	988	993	994	999	1001	1005	1011
1015	1016	1017	1023	1025	1027	1030	1035	1036	1037	1044	1045	1053	1055	1056	1057	1065	1066	1068
1071	1073	1075	1077	1078	1085	1086	1090	1095	1099	1101	1102	1105	1106	1107	1111	1113	1116	1120
1121	1125	1128	1131	1132	1133	1136	1137	1141	1145	1146	1147	1155	1157	1159	1161	1162	1165	1166
1173	1175	1177	1179	1183	1185	1189	1195	1197	1204	1205	1209	1215	1216	1221	1222	1225	1228	1233
1235	1239	1241	1245	1247	1251	1257	1261	1265	1267	1271	1273	1275	1281	1285	1288	1293	1295	1305
1309	1311	1313	1315	1317	1325	1329	1333	1335	1339	1341	1349	1351	1353	1355	1357	1365	1369	1377
1385	1387	1391	1393	1395	1403	1405	1407	1411	1413	1417	1419	1425	1431	1435	1441	1443	1445	1449
1455	1463	1465	1469	1473	1477	1485	1491	1495	1497	1501	1505	1513	1515	1516	1517	1519	1521	1525
1527	1533	1535	1537	1539	1541	1545	1547	1548	1551	1552	1558	1561	1562	1565	1573	1575	1581	1585
1591	1593	1595	1599	1603	1605	1611	1615	1617	1625	1629	1631	1635	1641	1643	1645	1647	1649	1651
1653	1655	1659	1661	1665	1675	1681	1683	1685	1687	1695	1705	1717	1725	1729
fett	Carmichel-Zahlen
grün	Quadratzahlen
rot	Pseudoprimzahlen der Form p₁p₂p₃

(1) Für alle aufgeführten Pseudoprimzahlen n gilt, das sie mindestens zu einer beliebigen Primzahl p für die 1 < p < n gilt
pseudoprim sind.

Ich arbeite noch an einer besseren Lösung für die Tabelle! --Arbol01 17:59, 10. Jul 2004 (CEST)

hallo, hier taucht wieder ein verständlichkeitsproblem auf, was sich nicht nur auf diese, sondern auch auf viele andere mathematischen und theoretisch-physikalischen seiten bezieht:

kann jemand bitte eine kurzerklärung schreiben, die man auch versteht, wenn man nicht 13 semester mathematik studiert hat (oder einfach keine lust hat, sich über 3 stunden in den artikel zu vertiefen)? quasi eine art kurzabriß für den mathematischen DAU ;-)

natürlich wird darunter die präzision leiden, aber das schadet ja nichts. denn wenn ich irgendwo das wort pseudoprimzagl aufschnappe, will ich erstmal wissen, worum es ungefähr geht, wenn ich das thema abschließend beherrschen will kann ich ja auch noch den rest des artikels lesen... ;-) --Carbenium 13:54, 31. Okt 2004 (CET)

Worum es bei dem Artikel geht, sagt der nachfolgende kurze Abschnitt aus:

Eine (Fermatsche) Pseudoprimzahl ist eine natürliche Zahl n, für die bei bestimmten Basen a mit

2\leq a<n

gilt:

a^{n-1}\equiv 1\mod n

,

die aber keine Primzahl ist. Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis a".

Das ist das Minimum, was zur Pseudoprimzahl zu sagen ist.

Für die Carmichael-Zahl, die auch eine Pseudoprimzahl, ist das auf eine gewisse Art einfacher, denn dort kann man sich an das Korselt-Kriterium halten. --Arbol01 15:42, 31. Okt 2004 (CET)