Diskussion:Pseudoprimzahl/Archiv

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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: 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 für jede Basis 1 < b < p und b ist eine natürliche Zahl. Oder im Programmierstil: . Wenn man diesen Sachverhalt umkehren könnte, wenn man also sagen könnte, daß für ein beliebiges n, daß die Eigenschaft 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 so bedeutet das nichts anderes, als populär ausgeschrieben: . Und da für alle n > 1 gleich 1 ist, könnte man populär schreiben . 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 beziehungsweise . 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: 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 p1*p2*p3

(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 gilt:
,
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)