Zahlentheorie und angewandte Mathematik. Zahl N hat 400 Dezimalstellen und ist aus 3 Primfaktoren zusammengesetzt.

Question

Gegeben ist eine Zahl N.


N hat 400 Dezimalstellen und ist aus 3 Primfaktoren zusammengesetzt.


Aufgabe1: Um welche Art handelt es sich bei der Zahl N?

Aufgabe2: Zerlegen Sie N in seine 3 Primfaktoren.


Hinweis: Mit herkömmlichen Verfahren ist N nicht in Polynomialzeit
 zerlegbar. Analysieren Sie N. Wenn Sie wissen, um welche Art von
Zahl es sich bei N handelt, ist die  Primfaktorzerlegung einfach.


N=

1863510760341182562859512389716611514434807702932688009288416628408489561663514067231785234625934466528167808166548995795725437868481962630980851061075438897444401253161142671870469639396910266291044877946306427814091219932776775672569080239780356823928699850192024398136948384029539764231434068363440667957771656540028301513381117028008993730932497925106717282247431252882716159814285986453974140481

Comments

Das ist ziemlich speziell für Dechiffrieraufgaben.

Wo hast du das her ?

---

Man kann durchaus einen Bezug zur Kryptographie herstellen.
Das RSA-Verfahren beispielsweise basiert auf der Tatsache,dass es schwierig ist eine große Zahl zu faktorisieren, während umgekehrt die Multiplikation ihrer Primfaktoren stets einfach auszuführen ist. Insofern also ein asymmetrisches Verfahren.

Die Aufgabe soll zeigen, dass dies nicht für alle Zahlen gilt.

---

Die Zahl ist wahrscheinlich Carmichael wenn nicht sogar Chernick.

---

Darf man fragen wie hoch die Wahrscheinlichkeit für eine Carmichael Zahl ist und wie das ermittelt werden kann?

---

Selbstverständlich darf man das fragen. Das ist sogar eine gute Mathefrage und passt daher ins Forum!

Answer 1

Bist Du sicher, dass alle Stellen exakt sind?

Habe getestet auf:

a) Primzahl-Drilling -> nein

{nicht nur Form p * (p+2)*(p+6)=N, sondern auch Faktoren Mrd. Steps vor & nach N^{1/3} }

b) große Fibonacci-Primzahlen -> nein

c) Carmichael-Zahl vom Typ Chernik (6m + 1)(12m + 1)(18m + 1)=N -> nein, da Nachkommastellen bei m:

m = 11286...759,262178951...

d) Carmichael-Zahl vom Typ Pinch  (12936k+1)*(14784k+7537)*(20328k+10363) {vermutlich Schreibfehler}

daher auch noch (12936k+6595)*(14784k+7537)*(20328k+10363)=N -> NEIN

Auf über 400 Stellen vor & nach dem Komma: k=7826154...6284,155843...

e) Typ m(2m-1)(3m-2)=a -> nein, da

m= 6772154925...6556,573...

f) Mersenne: 11. 12. 13. 14. 15. -> alle NEIN

Hattet Ihr schon Sophie Germain Primzahlen ?

Oder was gibt es sonst noch wie n!-1 oder ?

N soll wirklich eine Fastprimzahl 3. Ordnung {A014612} sein?

Das wird ja ein Faß ohne Boden -> richtig was für Kryptologen...

Comments

Alle Stellen von N sind korrekt.
Deine Analyse ist sehr gut! Mach weiter so.
Ich schlage einen probabilistischen Test für N vor.

---

g) Fermat-Primzahl ist nicht dabei  ( kein Modulo (2^n+1) mit Ergebnis 0)

Analyse Endstelle:

die 3 Primzahlen enden mit 1 1 1 oder 1 3 7 ; die Endziffern 2,4,5,6,8,9,0 sind nicht dabei.

Die vielen zeitaufwendigen Tests {Fermatscher Primzahltest

Solovay-Strassen-Test

Miller-Rabin-Test

Lucas-Test

Lucas-Lehmer-Test

APRCL-Test

AKS-Methode }

mache ich nicht allein -> da sollte der Aufgabensteller auch mal etwas beisteuern...

---

Nein, das musst du auch gar nicht. Danke an hyperG, du hast schon einiges beigesteuert.
Wir lösen das zusammen.
Wie hoch ist die Wahrscheinlichkeit, dass N eine Carmichael Zahl ist?

---

Wenn es nicht noch andere "Carmichael" als die unter c) d) e) beschriebenen Typen gibt, beträgt die W. =0, da ich bereits m und k exakt (PQRST-Formel für Gleichung 3. Grades) für reelle Zahlen (450 Nachkommastellen) ausgerechnet habe.  

Sobald m und k keine ganze Zahlen sind, kann es unter den ganzen Zahlen (und das sind Primzahlen) keine Lösung geben. Zusätzlich hatte ich auch eine Kontrolle mit eingebaut: das Produkt dieser 3 reellen Zahlen (mit den 450 NK) ergab immer N -> d.h. diese 3 (eigentlich 4, da ich auch den Schreibfehler (12936k+1) mit durchgerechnet habe) Carmichael-Typen sind es nicht. 

Oder gibt es noch andere der Form (a1 * m + o1)(a2 * m + o2)(a3 * m + o3)=N ?

---

Es gibt sehr viele Carmichaelzahlen die nicht von den obigen Typen ist, z.B. 561. Mehr Kontext zur Aufgabenstellung wär hier wohl hilfreich statt rumraten. Und wieso wollt ihr Primzahltests auf N loslassen,wenn schon bekannt ist, dass N nicht prim ist. Was soll das bringen?

---

Habe schon zig 400 stellige Zahlen gefunden, die mit 1 beginnen und enden und aus dem Produkt 3er Primzahlen bestehen, ABER diese war nicht dabei :-(

Auch Untersuchungen in Richtung

m=(sqrt(5-4*k+4*sqrt(1-2*k+4*(N)*k+k^2))-3)/24  mit k um 10^125 herum

mit Lösung, wenn m GANZZAHLIG -> zu viele Möglichkeiten ...

Wir brauchen Tricks der Zahlentheoretiker, die Sätze wie

"If a prime p divides the Carmichael number n, then n=1 (mod p-1) implies that n≡p (mod p(p-1)).

Aufgrund der Identität n-1 = n/p - 1 + (p-1)·n/p gilt für jeden Primteiler p einer natürlichen Zahl n:

n-1 ≡ n/p - 1 mod p-1."  in Algorithmen wandeln...

---

zu bh872: ja, ich habe ein extra Programm geschrieben, mit dem ich jede beliebige Kombination

(k1 * m + o1)(k2 * m + o2)(k3 * m + o3)=N

mit der Monster-Formel durchrechne! Wenn man weniger als 300 Stellen durch die Formel jagt, ist die Rundung so stark, dass die Test-Multiplikation für N nicht mehr stimmt!

Habe alle erdenkliche Kombinationen wie

(6m+1)(18m+1)(14011356m+1); (1+51 n) (1+12305 n) (1+367566078 n) ; (12m+1)(96m+1)(420m+1)   (156n+1)(312n+1)(2340n+1);935.794.081 = 72n+1 *   936n+1 * 13680+1=349489.8167;

6,10,118=163441590.267    ;  m(2m-1)(3m-2)=556.57 ; 6,12,18=759.26 ; (4+1)(2+1)(2-1)=9993.58; 256+1)(16+1)(16-1)=999.602

k[0]=220;k[1]=221;k[2]=249;o[0]=1;o[1]=1;o[2]=1; m=...186.1514

k[0]=7;k[1]=8;k[2]=11;o[0]=1;o[1]=1;o[2]=1; m=61.999358

k[0]=12936;k[1]=14784;k[2]=20328;o[0]=-59827428149;o[1]=-68374203599;o[2]=-94014529949; M=..01163.1558  1,3,4 521.80

k[0]=1;k[1]=2;k[2]=5;o[0]=1;o[1]=1;o[2]=1; 1,2,5=4188.78

auch alle Perrin-Zahlen Index 798 bis 3030...

---

Das ist doch super! Mit deinem Programm sollte N zerlegbar sein.

Also, N ist von der Form N=(A*m+1)*(B*m+1)*(C*m+1).
Wir schränken ein: A,B,C sind Teiler von N-1.


Meine Überlegung zur Grösse von A,B,C:
hierzu habe ich einige Carmichael Zahlen mit 3 Faktoren untersucht.

Carmichael1:
561 = 3*11*17 = (2+1)*(10+1)*(16+1) = (1*m+1)*(5*m+1)*(2^3*m+1) mit m=2
Chernick1:
1729 = 7*13*19 = (6+1)*(12+1)*(18+1) = (1*m+1)*(2*m+1)*(3*m+1) mit m=6
Carmichael100:
9439201 = 61*271*571 = (2*m+1)*(3^2*m+1)*(19*m+1) mit m=30
Carmichael421:
366532321 = 241*337*4513 = (5*m+1)*(7*m+1)*(2*47*m+1) mit m=48

egal welche Zahl ich nehme, alle lassen sich in eine Grundform bringen. Aus dieser Form lässt sich jeweils eine Konstruktionsmethode wie die von Chernik bzw. Michon herleiten.

Es scheint, dass A,B,C zueinander teilerfremd sind. A,B,C sind stets Teiler von n-1.
die Faktoren von A,B,C sind immer klein. Ich vermute die Faktoren sind kleiner 3*log(n) oder kleiner log(n)*log(log(n)). 3*log(n) gefällt mir als obere Grenze, da Harman die Anzahlfunktion für Carmichaelzahlen zu C(X) > X^0.332 verbessert hat. Beweisen kann ich das allerdings nicht.

Die Faktoren von N-1 bis zur Obergrenze 3*log(n):
1,2^6, 3^3, 5, 7, 11^2, 47, 53

Also können wir doch weiter einschränken:

N=(A*m+1)*(B*m+1)*(C*m+1)

mit A,B,C bilden eine Teilmenge aus (1,2^6, 3^3, 5, 7, 11^2, 47, 53)
und A,B,C sind zueinander Teilerfremd.

---

kurze Zusammenfassung:

-selbst die Suche aller Variationen aus 1,2^6=64, 3^3=27, 5, 7, 11^2=121, 47, 53 (Ergebnisse siehe Bild: http://lamprecht.bplaced.net/Bilder/3aus8Carmichael.png

1 und 27 fest, die anderen Kombinationen jeweils dazu, passte nicht mehr ins Bild) 

brachte nicht mal Ergebnisse mit mehr als 4 Nullen oder 9 (und das bei 450 Stellen Genauigkeit)!

Vermutung: die 3 Multiplikatoren liegen weiter auseinander als gedacht: erst bei einem Faktor 1111*m kam ,99994...

(weitere Vorschläge zum Testen?)

Test mit positivem Ergebnis:

-Eulersche Pseudoprimzahl: denn 2^{(N-1)/2}%N=1

-Teiler(wenn x[n-1]=x[n], dann gefunden): x:=[(N-1)%floor(N/x-1)]+1 ergibt Iterationsformel (verfängt sich jedoch oft in Periode)

Tests mit negativem Ergebnis:

- Primzahl-Drillinge oder Werte um N^{1/3} sind keine Teiler von N

- alle Perrin-Zahlen (A001608) Index 798 bis 3030... (98...371stellig) sind keine ganzzahligen Teiler von N

- N lässt sich nicht mit a^b+c (alle ganz und c < 10^40) darstellen

- N lässt sich nicht allein (mit offset<10^10) darstellen mit: Perin, Fibonacci, Lucas, Fakultät,

- alle in Frage kommenden 2^n+a mit n=80...1200 a=-1001...1000 sind keine Teiler von N

- alle in Frage kommenden 3^n+a mit n=78...800 a=-873; < 800 sind keine Teiler von N

- 5^n+a n=70; count < 530 a=-501; count < 500

- 7^n...

- alle 42- 200stelligen Pierpont-Primzahlen http://oeis.org/A005109/b005109.txt sind keine Teiler von N

offen:

-https://en.wikipedia.org/wiki/Catalan_pseudoprime da C[200stellig] hypergigantisch (würde Suche was bringen?)

-https://en.wikipedia.org/wiki/Frobenius_pseudoprime x²-x-1 (zu viele Möglichkeiten; Vorschläge?)

- Fibonacci-Pseudoprim... (würde das was bringen?)

Mich stören 2 Dinge besonders:

a) Zahl lässt sich nicht kurz darstellen: 211!/12 + ...

  (mit Potenzen , Fibonacci, Lucas... ist man noch weiter weg)

b) "... welche Art von Zahl es sich bei N handelt, ist die  Primfaktorzerlegung einfach" -> d.h. wir haben bestimmt noch nicht die richtige ART gefunden... :-(

---

Dankeschön für die Berechungen!
Das mit der 3 aus... Kombi bietet sich an, für A,B,C.
Nur das scheint komplexer zu werden als ich zuerst dachte.
Die Faktoren allein zu testen reicht nicht.

Ich halte trotzdem daran fest:
Es ist eine Carmichael Zahl und mit geeigneten Teilern von N-1
sollte die Lösung zu finden sein.


habe mal die Divisoren von N-1 bis Grenze sqrt(log(n)*log(log(n))) rausgelassen:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 27, 28, 30, 32, 33, 35, 36, 40, 42, 44, 45, 47, 48, 53, 54, 55, 56, 60, 63, 64, 66, 70, 72, 77

44 Elemente, kannst du damit eine 3 aus 44 Kombi testen?  leider 13244 Möglichkeiten :(

allerdings kommen nur die wenigen Kombinationen in frage, bei denen A,B,C zueinander teilerfremd sind.
eventuell kann man die schon im Voraus aussieben z.b. durch ein statement wie:

if gcd(A,B)=1 and gcd(A,C)=1 and gcd(B,C)=1 then do hyperG's-mega-formula.

---

Ergebnisse:

for(ja =0;ja <=41; ja += 1)

for(jb =ja+1;jb <=42; jb += 1)

for(jc =43;jc >jb; jc -= 1)

{

if((ggt(aj[ja],aj[jb])==1)&&(ggt(aj[ja],aj[jc])==1)&&(ggt(aj[jb],aj[jc])==1))

{wird Anzahl Kombinationen: lcount=1329

ergibt leider nur uninteressante krumme m-Faktoren!

#### etwas mehr Kombinationen mit Änderung for(jb =ja; und anderen Offset für den mittleren Faktor:

(k0=15+1)( k1=35-1)( k2=53+1)

ergibt 1 interessantes m=

406099302847735981269659118926365398619945701505143714870880185921090433222349560769118437300299018104785441690453694408473960928864.0000579343050693255242753128846933103775385539831748756465014235981877536534995424874107099059252341

lcount=3122

Wie weit dieses m noch vom Ergebnis entfernt ist, zeigen die ganzen gerundeten Faktoren daraus (p1=k0*floor(m)+o0):

p1 * p2 * p3 je untereinender:

6091489542716039719044886783895480979299185522577155723063202788816356498335243411536776559504485271571781625356805416127109413932961

14213475599670759344438069162422788951698099552680030020480806507238165162782234626919145305510465633667490459165879304296588632510239

21523263050930007007291933303097366126857122179772616888156649853817792960784526720763277176915847959553628409594045803649119929229793

Divisionsreste zu N:

mod p1=2430681710459095125068851959351231797733369030760707903184743761370268200331748052150255353791421336826221400028195176086114233870383

mod p2=3775362229045193810102009475908269329874921117498898347326834192199029405108820589002757455068916839989664928732799550320203027948761

mod p3=6783439581427085616225802280579016508913354355849478638131953095373446615309067271951263010359815847040270536159600787431831414589713

#### mir liegen die Faktoren noch zu dicht beieinander (in diesem Bereich hatte ich ja bereits per nextPrime() alles untersucht!

Warum endet die Folge schon bei 77? Bei der letzten war doch auch 121 dabei?

Und warum sollten die Offsets alle 1 sein?

Weiterer Algorithmus, der seit über 4 Stunden läuft:

https://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat

da Suche der Faktoren "von hinten" beginnt und Vermutung "2 Faktoren liegen dicht bei einander".

---

Ok, wenn die faktoren dicht bei einander liegen sollten, teste bitte nochmal auf

N=(A*m+1)*(47*m+1)*(53*m+1)   mit 40<A<56.  ich halte das für plausibel.

---

So viele verschiedene anonyme Gäste hier...

Nein, selbst die Vergrößerung des Suchbereiches  A=40... 1056

bringt nicht mal ein m zustande, welches 4 richtige Nachkommastellen erzeugt!

Mit Raten & Probieren kommt man bei solch großen Zahlen nicht mal in die Nähe eines Ergebnisses!

Übrigens: Fermats 2-Faktoren-Suche hätte bei wenigen Schritten bis zum Erfolg ein Ergebnis mit folgenden Ziffern-Längen: p1 = 200stellig ; p2 und p3 je 100stellig (wobei p2 & p3 natürlich weiter auseinander liegen können)

Da die Fermat-Suche jetzt schon über 7 h läuft, scheint auch diese Suche erfolglos zu bleiben...

---

Heureka -  ich hab's !!!!!

Die Lösung: unter   

http://www.lamprechts.de/gerd/php/primfaktorzerlegungsergebnis.html  

---

Entschuldige je213:

Die Lösung (44m+1)*(47m+1)*(53m+1) {die ja in Deinem vorgeschlagenen Suchbereich enthalten war} wurde von mir zunächst übersehen, da ich mich wegen der großen

For - Schleife hinleiten ließ, die Genauigkeit auf nur 136 Nachkommastellen herunterzuschrauben, -> was zur Folge hatte, dass die Rundungsfehler sich durch die Mega-Formel bis auf die ersten 2 Nachkommastellen hochschaukelten!   

Gleichzeitig habe ich einen völlig anderen Algorithmus gefunden, der OHNE Nachkommastellen auskommt!

Diese "Faktorisierungs-Findung" funktionierte sogar mit dem 2. Faktor: (N/p1) und konnte damit sofort p2 und p3 ermitteln. -> Da dieser 2. Faktor keine Carmichael-Zahl ist folgende Frage:

 Kann es sein, dass ich einen neuartigen Algorithmus gefunden habe, den noch niemand kennt???

Allerdings funktioniert er nicht bei "echten RSA" (RSA-129 ... RSA-768) nicht (das wäre ja auch eine Sensation).

Kennt jemand noch andere ungerade große Zahlen, die nicht vom Typ Carmichael sind wie diese hier

136737468391757104134996764234681403607914136411261244588019357511903275480037519816253457840477425830355739805417755823140829750935572440213346052302375734592444731165091362745577204914454575043191810628607042051317343977867871099841880227685284847544389797719753321  

die ich mal testen könnte?

---

Kein Problem :)

Die 3 Fraktoren p1,p2,p3 sind alle prim und p1*p2*p3=N. Aufgabe gelöst! Dein Algorithmus war doch der Schlüssel um N zu zerlegen. Also schlag ich vor, dass du die Lösung reinstellst.

Du schreibst: ...Diese "Faktorisierungs-Findung" funktionierte sogar mit dem 2. Faktor: (N/p1) und konnte damit sofort p2 und p3 ermitteln. -> Da dieser 2. Faktor keine Carmichael-Zahl ist...

p2*p3 ist ein Divisor von N. Mit der Methode von http://crypto.stackexchange.com/questions/5279/carmichael-number-factoring sollten einzelne Divisoren von Carmichael Zahlen ermittelt werden können.

wenn du nun eine zahl n=p2*p3 alleine hast, ohne wissen von p1,p2,p3, wie zerlegst du dann n? das würde mich auch interessieren.

---

Was meinst Du mit "...dass Du die Lösung reinstellst." ? Unter

http://www.lamprechts.de/gerd/php/primfaktorzerlegungsergebnis.html    

sind doch alle Fakten (alle 3 Primfaktoren usw.) enthalten.  

Die "Mega-Formel" kann sich jeder bei WolframAlpha ansehen {(a1 * m + o1)(a2 * m + o2)(a3 * m + o3)=N }.  

Der 2. Algorithmus basiert auf Deinem letzten LINK.  

Die Zerlegung von n: ich tue so, als wenn es eine Carmichael-Zahl wäre. Nur wenn es bei W=2 keine Lösung ergibt, versuche ich es weiter durch Inkrementierung von W, bis was herauskommt. 

Ich überlege auch, ob ich einen "Carmichael-Faktorisierer" online stellen sollte. Habe jetzt schon zu wenig Zeit... Das könnte jedoch meinen Server noch mehr belasten ... und dann noch alles kostenlos & ohne Werbung ...

---

Dachte nur dass du dann positive punkte kassieren kannst, als Moderator, wenn du Antworten einstellst.
Mir ist das nicht so wichtig, ich habe noch keinen Account. Egal.

Also wie sollte dein n aussehen? das produkt von 2 faktoren einer Carmichael Zahl? willst du das testen?

ein "Carmichael-Faktorisierer" warum nicht? sowas hat das web noch nicht :) (wenn du genügend zeit hast natürlich)

---

Als Angemeldeter kann man nicht noch einmal antworten. (oder bist Du der Frager?)

Muss der Professor sich nun eine neue Aufgabe ausdenken?

Die selbst gebastelten n sehen z.B. so aus (beide Faktoren = prime):

100980575039537519982805885166411*((100980575039537519982805885166410*Prime(78)+1))=

4048239384520320198159152895702691412734136987483292987079034606881  

Diese Übergebe ich Algo 2 und tue so, als wenn es eine Carmichael wäre.

Sobald jedoch ein ...-1))  dabei ist, kommt es zu keinem Ergebnis.

(2^107-1)(2^107*NextPrime(735)-1)=

19456445885765940242440355614557992299051015257362538536506339885057  

funktioniert nicht.

---

Die Erstellung vom Typ mit krummen Offset:

(60*10000000000000000183+13)*(150*10000000000000000183+31)=

900000000000000032978100000000000302098633

funktioniert jedoch. Vermutlich, weil man mit noch einem 3. Faktor daraus eine Carmichael Zahl basteln könnte.

---

Du hast recht! Die Zahl muss gar nicht vom Typ Carmichael sein.

Dein Beispiel:
n=p1*p2=(60*10000000000000000183+13)*(150*10000000000000000183+31)
mit m=ggT(p1-1,p2-1)=300000000000000005496
(p1-1)/m=2 ; (p2-1)/m=5
n kann somit dargestellt werden als:
n=(2*m+1)*(5*m+1)

Es scheint mir, dass der Algo 2 immer dann funktioniert, wenn
n in eine Form n=(A*m+1)*(B*m+1)*... mit ausreichend kleinen A,B,... gebracht werden kann.
Siehst du das auch so?

bei n=(A*m-1)*(B*m-1)
funktioniert er nicht, wie du schon sagst wegen -1.
Möglicherweise gibt es aber einen ähnlichen Algorithmus der das lösen kann.

---

So, Carmichael-Zahl-Faktorisierer ist online:

http://www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php  

3 andere Tests sind auch gleich dabei.

Answer 2

Zu Aufgabe 1.  

Wie prüft man, ob eine beliebige ganze Zahl \(n\) eine Carmichael Zahl ist, ohne sie dabei in seine Primfaktoren zerlegen zu müssen?

Zuerst wählt man einen starken Primzahltest, wie z.b.
Miller–Rabin,Solovay–Strassen oder den neueren APRCL-test.
Bekommt man als Ergebnis nicht-Primzahl, dann ist bewiesen,
dass \(n\) zusammengesetzt ist.

Nun wählen wir eine Methode, die auf dem kleinen fermatschen Satz basiert:

\(a^{p}\equiv a \ (mod\ p)\)      für alle \(a\in\mathbb N^{+}\)  , \(p\in\mathbb P\)  und  \(0<a<p\).

Der Test für eine beliebige ungerade zusammengestzte Zahl \(n\) mit \(n\in\mathbb N^{+}\) und  \(n\neq1\) lautet:

Wähle eine zufallige Basis \(a\) mit \(1<a<n-1\).

Fall1: \(a^{n-1}\equiv 1 \ (mod\ n)\)   \(\rightarrow\)   wähle ein andere Basis \(a\) und wiederhole den Test.

Fall2: \(a^{n-1}\not\equiv 1 \ (mod\ n)\ \ und\ \ ggt(a,n)=1\)   \(\rightarrow\)   \(n\) ist zusammengesetzt aber nicht Carmichael Zahl. Der Test ist beendet.

Fall3: \(a^{n-1}\not\equiv 1 \ (mod\ n)\ \ und\ \ ggt(a,n)\neq1\)   \(\rightarrow\)   \(n\) ist zusammengesetzt und \(ggt(a,n)\) ist ein echter Teiler von \(n\). Wähle ein andere Basis \(a\) und wiederhole den Test.

Für den Fall 1 und 3 wiederhole den Test \(k\)-mal. Nach Bendigung ist \(n\) eine Carmichael Zahl mit Wahrscheinlichkeit \(1-2^{-k}\).

Hier meine Implementierung für Pari-GP:

iscarmichael(n)={         \\input: positive integer n > 1
    my(a=0,k=100);          \\returns 1, if n is a Carmichael number with probability 1-2^-k
    if(n%2==0||ispseudoprime(n)==1,return(0));
    for(t=1,k,a=random(n-3)+2;if(lift(Mod(a,n)^{n-1})<>1&&gcd(a,n)==1,return(0)));
return(1)
};

Die Funktion iscarmichael(n) gibt 1 zurück, falls \(n\) eine Carmichael Zahl mit  Wahrscheinlichkeit \(1-2^{-k}\) ist. Andernfalls gibt sie 0 zurück. Parameter \(k\) ist auf 100 gesetzt. \(k\) kann erhöht bzw. erniedrigt werden um höhere bzw. niedrigere Wahrscheilichkeiten zu erhalten.

Wenn wir nun N mit dem obigen Test prüfen erhalten wir die Aussage:

N ist Carmichael Zahl, mit beliebig hoher Wahrscheinlichkeit.

Comments

gibt es für die lift-Funktion ein Code-Beispiel?

Habe zig unterschiedliche Interpretationen (Lambda lifting) mit kryptischen Zeichen gefunden, die alle nicht kompatibel mit den üblichen Sprachen (c, pas, bas, JAVA, php, ...) waren.

---

in pari-gp wird mit lift(Mod(a,n)^{n-1}) das modulare potenzieren beschrieben.

a^{n-1}%n , wobei % für mod steht, kann nicht funktionieren, da pari zuerst versucht a^{n-1} zu berechnen.Das ergibt natürlich einen overflow.Für andere Sprachen brauchst du eine Funktion die modular potenziert.powermod(x,k,m)=lift(Mod(x,m)^k) .

ich hoffe das hilt dir, ansonsten frag einfach nochmal.

---

Danke bi817. Natürlich kenne ich JAVAs  BigInteger modPow() .

Außerdem hatte ich den "abgekürzten" Mod-Algorithmus bei der Pow(x,y,...,N) schon vor Jahren bei

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php  eingebaut um die letzten Stellen der größten bekannten Primzahlen zu überprüfen.

Ich könnte Denkanstöße gebrauchen:

a) gehen meine Untersuchungen mit dem etwas allgemeineren Spezialfall

N=(6m+1)*(12m+1)*(1+((6m+1)*(12m+1)-1)/floor(k))

m=(sqrt(5-4*k+4*sqrt(1-2*k+4*(N)*k+k2))-3)/24  mit k um und oberhalb 10^125 herum

mit Lösung, wenn m GANZZAHLIG -> überhaupt in die richtige Richtung (selbst die Umstellung nach k und die damit verbundene Verkleinerung der m-Suche ist noch extrem...)  ? Oder gibt es bessere Abkürzungen für GANZ-Zahl-Suche? Vermutlich ist die Annahme der ersten beiden Faktoren mit dem Verhältnis  (6m+1)*(12m+1) immer noch eine zu starke Einschränkung...

b) Was außer diese Aussagen:

"If a prime p divides the Carmichael number n, then n≡1 (mod p-1) implies that n=p (mod p(p-1)). "

"Aufgrund der Identität n-1 = n/p - 1 + (p-1)·n/p gilt für jeden Primteiler p einer natürlichen Zahl n:

n-1 ≡ n/p - 1 mod p-1."

gibt es denn noch um daraus Algorithmen oder Formelumstellungen hinzubekommen?  

Solche Sätze "Wenn Sie wissen, um welche Art von Zahl es sich bei N handelt, ist die  Primfaktorzerlegung einfach. " mögen bei Primzahlendrillingen oder bei speziellen festen Verhältnissen gelten... -> aber hier? (hatte im Studium keine zahlentheoretischen Entschlüsselungs-Suchen...)

---

a) ja ich halte das für eine zu starke Einschränkung.
Ich vermute N = (A*m+1)*(B*m+1)*(C*m+1)  wobei A,B und C teilen  N-1.
Wie löst du nach m auf? Auf Wolfram Alpha bekomme ich einen Monster-Term über
23 Zeilen, sowas kann ich nicht abtippen, da wird mir ja schwindelig.

b) die verschärfte Form von Korselts Satz.
n-1 ≡ n/p - 1 mod p-1.   -> p-1 durch Phi(p) ersetzen und versuchen zu verallgemeinern?
Habs probiert, komme aber zu keinem Ergebnis.

weiterer Denkanstoss:
http://crypto.stackexchange.com/questions/5279/carmichael-number-factoring
http://crypto.stackexchange.com/questions/9137/algorithm-for-proving-carmichael-numbers
Da wird gesagt, die Zerlegung einer Carmichael Zahl sei einfach. Lösung mittels Miller-Rabin-test?

---

beim 2. LINK steht: Random!!! bei Zahlen, die zig Mrd.  mal größer  als Anzahl der Atome im Weltall nicht realisierbar!

Rest siehe oben zur Mega-Formel...