Science is what we understand well enough to explain to a computer.
Art is everything else we do.
Donald E. Knuth


Auf das Thema antworten  [ 11 Beiträge ] 
UE5 
Autor Nachricht

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag UE5
hallo,
hat sich schon jemand bsp 30 angesehen?
ich habs mit einem siebintervall von bis zu {-5,-4,...,4,5} probiert und komm dabei auf nichts sinnvolles, da die b_i hauptsächlich große primfaktoren(2 stellig haben). in der vo meinte der wiesenbauer allerdings, dass man schon mit einer sehr kleinen faktorbasis auskäme. wenn man davon ausgeht, dass die siebintervall-schranke C in etwa halb so groß wie der größte primfaktor sein soll, und man eine faktorbasis wählt, in der 7 der größte primfaktor ist, dann wäre C=3 bzw C=4. ich habs bis C=5 probiert und komm auf nix gscheites. was überseh ich?


Fr 22-05-2009 13:19:54
Diesen Beitrag melden
Profil ICQ

Registriert: 05/2008
Beiträge: 23 + 1
Mit Zitat antworten
Beitrag Re: UE5
hallo alex,

bin bis p=23 ( oder c=11) gegangen und habe nichts gefunden. :shock: :cry:
Vielleicht mache ich auch irgendetwas falsch.

Hast du vielleicht 29 schon gemacht?


Sa 23-05-2009 20:07:02
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: UE5
ja, 29 hab ich gemacht:
$ln(ln(\frac{n}{P(n)})) \approx ln(ln(n))-1 \Leftrightarrow$
$ln(\frac{n}{P(n)}) \approx \frac{ln(n)}{e} \Leftrightarrow$
$ln(n)-ln(P(n)) \approx \frac{ln(n)}{e} \Leftrightarrow$
$1-\frac{ln(P(n))}{ln(n)} \approx \frac{1}{e} \Leftrightarrow$
$1-\frac{1}{e} \approx \frac{ln(P(n))}{ln(n)}$


So 24-05-2009 01:10:48
Diesen Beitrag melden
Profil ICQ
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: UE5
danke! hui so kurz ist das, und ich habe mit der Exponentialreihe herumgeeiert...
bei den ersten 4 BSP gibts keine probleme, oder soll ich etwas posten?

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


So 24-05-2009 09:20:15
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: UE5
ich frag mich, was das bsp25 mit einer common modulus attack zu tun ham soll.
@SOADdict: was hast du beim 26er?


So 24-05-2009 10:07:08
Diesen Beitrag melden
Profil ICQ
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: UE5
stimmt: 25 hat direkt nichts damit zu tun, man kann n so faktorisieren bei gegebenen (e,d) ...
bei 27:mir kommt für keine der Primzahlpotenzen ein nicht-trivialer Teiler raus
(ich habe das gefühl er hat die demonstrativen Beispiele die woche ungünstig gewählt :) )
26:


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


So 24-05-2009 10:32:27
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: UE5
@SOADdict: ich versteh die if-bedingung in deiner schleife nicht.
sollte nicht, unter der annahme, dass wenn ich b schreib als $b:=a^{\frac{ed-1}{2}} \bmod n$, gelten, dass $b^2 \equiv 1 \bmod n \land b \not\equiv \pm \bmod n$? daraus würde dann folgen, dass $pq|(b+1)(b-1) \land pq \nmid b \pm 1 \Rightarrow \{(b+1,n),(b-1,n)\}=\{p,q\}$.


So 24-05-2009 12:40:14
Diesen Beitrag melden
Profil ICQ

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: UE5
dh sollte die schleife nicht so aussehn?
Code:
b:=a^((ed-1)/2) mod n;
for j from 1 to t-1
   if (b^2 = 1 mod n and b != +-1 mod n)
      return {ggt(b-1,n), ggt(b+1,n)};
   end if
   b=b^2 mod n;
end for


So 24-05-2009 13:17:50
Diesen Beitrag melden
Profil ICQ
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: UE5
naja, du initialisierst dein b mit der "ersten Wurzel" also $b:= a^{\frac{ed-1}{2}}$
in der Angabe steht man soll von unten kommen. also stelle ich den Exponenten (ist gerade!) als $ed-1=u2^t$ mit u ungerade dar. und ziehe sozusagen die t-te Quadratwurzel indem ich $b:= a^u$ initialisiere und dann in jedem schritt das Quadrat davon betrachte.
Wenn nun mein derzeitiges b $\not \equiv \pm 1 \mod n$ ist schaue ich noch ob das Quadrat davon $b^2 \equiv 1 \mod n$ist. somit hätte ich eine weitere Wurzel von 1 gefunden.
der code sieht dann so aus:
Code:
b:=a^u mod n;
for j from 1 to t-1
 c:=b^2 mod n;
   if (c = 1 mod n and b != +-1 mod n)
      return {ggt(b-1,n), ggt(b+1,n)};
   end if
  b:=c;
end for


gibts übrigends etwas zum 30er bzw eine idee warum 27 nicht klappt? (oder ist das nur bei mir so?)

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


So 24-05-2009 16:06:01
Diesen Beitrag melden
Profil

Registriert: 05/2008
Beiträge: 23 + 1
Mit Zitat antworten
Beitrag Re: UE5
hallo,
bei mir klappt der 27er, allerdings bin ich mir nicht ganz sicher ob ich den Algorithmus richtig verstanden habe.

Sollte es stimmen, dann liegt der Trick darin, dass man, wenn man die Primzahl erhöht, dh wenn von p=3 auf p=5 übergangen wird, dann soll man auch den Wert von a so übernehmen, wie sie momentan ist.( beim Übergang von schritt 3 auf Schritt 2), dann klappt es.
Falls ich mich nicht verrechnet habe, so terminiert der Algorithmus beim vierten Schleifendurchlauf und ich bekomm die gesuchten Faktoren.

Hoffe die Erklärung ist nicht zu konfus.


So 24-05-2009 16:38:22
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: UE5
ok. danke ich habs zuerst falsch verstanden und die a's nicht mitgenommen. dann machte ich es bereits so wie du es beschrieben hast nur habe ich mich sicherlich irgendwo vertippt, denn nun passt es!

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


So 24-05-2009 16:55:47
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 11 Beiträge ] 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2022  |  Deutsche Übersetzung durch phpBB.de