+1 Punkt
1,1k Aufrufe

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


von

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!

2 Antworten

+2 Daumen

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...

von 5,2 k
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 im LINK: 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:

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

-http://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:

http://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.

+1 Punkt

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.

von

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...

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...