Die Mathe-Redaktion - 20.06.2018 13:03 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 581 Gäste und 25 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Faktorisierung: Ein simples Beispiel - Zur Erinnerung: Das Neubert-Verfahren ;-)
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Faktorisierung: Ein simples Beispiel - Zur Erinnerung: Das Neubert-Verfahren ;-)
Siggi43
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 24.10.2016
Mitteilungen: 22
Aus: Hamburg, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-02-18


Zur Erinnerung: Das Neubert-Verfahren ;-)

Bitte ich warte auf eure Anmerkungen!

Zu jeder natürlichen Zahl k
gibt es eine multipl. Restegruppe Z2k* (Modulo 2k).
Die Elemente von Z2k* sind die zu 2k Teilerfremden Elemete aus
Z2k= {0,1,...,2k-1). Die Ordnung dieser Gruppen ist phi(2k).

Seien p1,p2,...,pn genau die verschiedenen Primteiler von 2k, so gilt mit der Eulerschen phi-Funktion: phi(2k)= 2k*( (1-1/p1)(1-1/p2)...(1-1/pn) )


Satz:
Seien Z2k* und Z(2k²)* die multiplikativen Restegruppen mod 2k bzw. 2k².
(Hier ohne Beweis)

Für jedes ungerade N und geeignetes k
existiert eine immer formal gleiche Definition der Folgen
YY= YY(t)=YY((p,q),t), mit (p*q) mod 2k= N mod 2k.

Wobei YY= YY(t)= X(t)² -Nu und X(t)= (P+Qu)/2= 2k²*t +r
und r konstant von der Form r= U*(Nu +p²)/2 mod 2k²,
mit p,U=p⁻¹ aus Z(2k²)* und p,q,u=(pq⁻¹) aus Z2k*

(YY= YY(t)= X(t)² -Nu und X(t)= (P+Qu)/2= 2k²*t +r
und r= U*(Nu +p²)/2 mod 2k²,
erhält man durch Umformen und Ausrechnen von N= (2k)²nm +qP +pQ -pq
unter Berücksichtigung von u=pq⁻¹ (mod 2k) und U= p⁻¹ (mod 2k²) )


Simples Beispiel mit kleinem k:

N=1001, k=3,  N mod 2k= 5, Z2k*={1,5}, Z(2k²)*={1,5,7,11,13,17}
Es gibt die Paare (p,q)= (1,5) und (5,1).
a) Sei p=1, q=q⁻¹=5, u=pq⁻¹=5, p²=1 und U=1, bzw.
b) Sei p=5, q=q⁻¹=1, u=5, p²=25 und U=11.

Also: a) r= 1(1001*5+1)/2 mod 18= 2503 mod 18=1 und sqrt(5005)= 70,...
Daher X0=18*4 +1=73 und 73² -5005= 324= 18²
Und P= X+Y= 91 und Qu= X-Y= 55 also Q=11
(Und für X=X0+7*2k²= 199 und 199² -5005= 34596= 186² und Pu=77*5, Q=13)

Bzw.: b) r= 11(5005+25)/2 mod 18= 27665 mod 18= 17.
Daher X0=18*4+17= 89 und 89² -5005= 2916= 54².
Und P=143 Qu= 35=7*5 also Q= 7

Insgesamt zeigt sich 1001= 7*11*13,
wobei man gleich beim jeweils 1. Folgenglied
bzw. in a) nach 7 Schritten zum 2. Mal erfolgreich war!

Das liegt aber an diesem simplen Beispiel,
im Allgemeinen ist das nicht so, man muß Suchen,
i.d.R. (bei größeren und großen Zahlen) sogar sehr viel mehr!
Das ist - besonders bei bei sehr großen Zahlen - sehr aufwendig.

Mit größerem k findet man die Faktoren eher
(die Suchschrittweite wächst mit 2k²),
aber wegen der größeren Gruppen wächst leider auch der Auffand mit
1< 2k/phi(2k)< 2k (damit sinkt der Gesamtaufwand mit wachsendem k).

Für N= 1001 und k=12 ist phi(2k)=8, Z2k*= {1,5,7,11,13,17,19,23)
und man findet für p= 5, 11 und 23 _sofort_ die Faktoren 13, 11 und 7.

Trotzdem wächst für größere N im Allg. die Anzahl der Suchschritte.
Beschränkt man sich aber darauf die "Quadratischen Reste" bezgl. eines Moduls m zu betrachten, kann man die Anzahl zu ziehender Wurzeln einschränken - ggf. sogar ganz entscheidend.

Weiter geht's demnächst mit: Was sind (reale) quadratische Reste?



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4043
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-02-19

\(\begingroup\)
2018-02-18 17:06 - Siggi43 im Themenstart schreibt:
Satz:
Seien Z2k* und Z(2k²)* die multiplikativen Restegruppen mod 2k bzw. 2k².
(Hier ohne Beweis)

Für jedes ungerade N und geeignetes k
existiert eine immer formal gleiche Definition der Folgen
YY= YY(t)=YY((p,q),t), mit (p*q) mod 2k= N mod 2k.

Wobei YY= YY(t)= X(t)² -Nu und X(t)= (P+Qu)/2= 2k²*t +r
und r konstant von der Form r= U*(Nu +p²)/2 mod 2k²,
mit p,U=p⁻¹ aus Z(2k²)* und p,q,u=(pq⁻¹) aus Z2k*

(YY= YY(t)= X(t)² -Nu und X(t)= (P+Qu)/2= 2k²*t +r
und r= U*(Nu +p²)/2 mod 2k²,
erhält man durch Umformen und Ausrechnen von N= (2k)²nm +qP +pQ -pq
unter Berücksichtigung von u=pq⁻¹ (mod 2k) und U= p⁻¹ (mod 2k²) )

Ich habe da eine Menge Probleme mit diesem Satz - und vermutlich andere auch, was auch der Grund sein dürfte, dass hier niemand sonst antwortet.

1. Wenn du z.B. $\mathbb{Z}_{2k}^*$ sagst, so meinst du offenbar die Elemente in $\{1,2,...,2k-1\}$, welche zu $2k$ teilerfremd sind. Sag jetzt bitte nicht, dass dies selbstverständlich ist: Das Vertretersystem für die primen Restklassen mod $2k$ kann man sich nämlich im Prinzip aussuchen, auch wenn das obige sowas wie "Standard" ist. Ich selbst gehe nachfolgend von dessen Verwendung aus.

2. Leider fehlt jegliche Motivation für deine Formeln aus welchem Grund auch immer. Ich vermute mal, du gehst gedanklich von einer Faktorisierung

$N=P\cdot Q$

aus, wobei man $P$ und $Q$ noch nicht kennt und wendest darauf den Homomorphismus $x\mapsto x \mod 2k$ mit einem im Folgenden dann festen k<<N an, welches überdies zu N teilerfremd ist. Mit

$s:=N \mod 2k,\ p:= P \mod 2k,\ q:=Q \mod 2k$

erhält man daraus dann die Beziehung

$s\equiv p\cdot q  \mod 2k$. (*)

Dies bedeutet aber nicht, dass $p$ und $q$ jetzt wirklich Teiler(!) von $s$ sind, daher verstehe ich auch nicht, warum du im Folgenden nur einfach alle Faktorisierungen von $s$ mit $s=p\cdot q$ betrachtest, obwohl doch viele andere Werte für $p$ und $q$ ebenfalls in Frage kämen.

3. Bei der Original Fermatmethode wäre es gut wenn in $N=P\cdot Q$ die beiden Faktoren $P$ und $Q$ etwa "gleich groß" wären. Indem man $N$ mit einem $U\approx P/Q$ multiplziert, würde dann $N\cdot U$ diese Bedingung erfüllen, was natürlich in der Praxis darin scheitert, dass man $P$ und $Q$ ja nicht kennt und man also gewissermaßen dann nur "raten" kann, z.B., mit einem $U$, das "sehr zusammengesetzt" ist. Mir kommt es vor also wolltest du dasselbe mit (*) nachstellen, indem du

$u:=\frac pq \mod 2k$

setzt. (Bitte keine Angst vor "modularen Brüchen" haben, solange der Nenner zum Modul teilerfremd ist, da dies die Lesbarkeit der Formeln deutlich erhöht!) In meinen Augen ist es aber ein Irrglaube, dass man damit eine echte Chance auf ein "gutes" $u$, insbesondere eines mit $u\equiv U \mod 2k$ bekommt, wobei $U$ wie oben gewählt ist.

4. Deine Formel für $r$, nämlich

$r:=\frac{Nu+p^2}{2p}\mod 2k^2$

macht mir "schwer zu schaffen", zumal darin Größen vorkommen, die $\mod 2k$ berechnet wurden, wie $p$ und $u$, aber dann bei dir $1/p \mod 2k^2$ und auch das ganze $r \mod 2k^2$. Aber ich sehe natürlich, dass

$\left(\frac{Nu+p^2}{2p}\right)^2-Nu\equiv\left(\frac{Nu-p^2}{2p}\right)^2 \mod 2k^2$

ist, d.h., die linksstehende Differenz ist tatsächlich ein quadratischer Rest $\mod 2k^2$, obwohl das jetzt nicht wirklich viel bedeutet.

5. Und ja, da sind dann diese mysteriösen Parameter $t$, deren Bedeutung mir schon klar ist, obwohl du über sie kein Wort verlierst, insbesondere wie man den allerersten Wert wählen muss. Aber wie du auf die Schrittweite $2k^2$ kommst, ist mir auch nicht wirklich klar, das gilt aber schon für obige Formel für $r$.

Ich könnte jetzt noch vieles anderes anführen, aber ich belasse es mal dabei.

Prinzipiell ist die Fermatmethode i.Allg. so "grottenschlecht", dass man da eigentlich kaum Hoffnung haben könnte, mit Verbesserungen da einen Durchbruch zu erzielen. Lehmann hat das aber mit einer genialen Modifikation trotzdem geschafft, wie du vermutlich weißt, und das ist auch das Beste, was man hier erreichen kann. Wenn es dir das Ganze also Spaß macht und du es als "netten Zeitvertrieb" siehst, ist es ok, allzu große Hoffnungen auf eine umwälzende Entdeckung würde ich mir hier aber nicht machen.

PS: Und ja, deine Beispiele sind in Ordnung, insofern sie deinen Algorithmus illustrieren, um zu sehen, ob er was taugt, müsste man natürlich viel größere Zahlen testen und das geht dann natürlich nur mit einem Computerprogramm. Hast du in dieser Hinsicht schon was versucht?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Siggi43
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 24.10.2016
Mitteilungen: 22
Aus: Hamburg, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-02-19





Erneut danke für die Mühe des durchsehens.

Ich versuchs nochmal, in der Hoffnung es hilft zum besseren Verständnis.
Meine Erfahrungen mathematische Texte zu schreiben waren wohl nie gut
- Pardon!

Ich möchte zeigen, daß es zu einer natürlichen Zahl N - abhängig von einem Parameter k>1 - Familien von Folgen gibt, die, wenn sie ein Quadrat als Folgenglied enthalten, analog zur Fermat-Faktorisierung, zu einer Zerlegung von N=P*Q führt.
(Wobei ggt(N,k)=1 sein soll, sonst hätte man schon einen Faktor von N gefunden!)

Ich benötige die beiden Gruppen Z2k* und Z(2k²)*.
Wobei Die Elemente aus Z2k* auch Elemente in Z(2k²)* sind.

Die Folgen YY schreiben sich formal alle gleich.
Mit s= N mod 2k, gibt es genau phi(2k) Paare (p,q) mit p,q aus Z2k*, so daß (p*q) mod 2k= s.

Die Folge YY |--> IN, t |--> YY(t)= X(t)² -Nu (siehe später) bildet abhängig von 2k, durch die phi(2k) verschiedenen Paare (p,q) als Parameter) eine Familie von Folgen YY((p,q),t).

Bei der Suche nach Quadraten für nichttriviale Zerlegungen von N in den Folgegliedern (also nicht N=1*N), muß man alle Folgen der Familie betrachten.
Weil p (wegen p*q= s mod N) q bestimmt, betrachtet man (siehe später) alle Folgen YY((p,q),t) für alle p aus Z2k*.

Also ausgehend von Fermat. Einführung des Parameter k (bzw. 2k) führt mit Hilfe der Gruppe Z2k* zu einer Darstellung
N=PQ= (2kn +p)(2km +q) mit p,q,s aus Z2k* und s= (p*q)= N mod 2k.
Da es phi(2k) verschiedene Paare (p,q) mit p,q aus Z2k* gibt,
muß man nachfolgende Betrachtung für alle p (und q=s*p⁻¹) durchführen.

Durch Umformung von N= (2kn +p)(2km +q) findet man letztlich
X= 2k²*t +r mit t Laufparameter und r= U*(Nu +p²)/2 mod 2k².
(Weil N= PQ= (2kn +p)(2km +q)= (2k)²nm +2knq +(pq -pq) +2kmp +pq= ...
... = (2k)²nm +q(2kn +p) +p(2km +q) -pq oder
X'':= (qP +pQ)/2= 2k²*t'' +(N+pq) mod 2k².
Multipliziert man mit u=pq⁻1 folgt
X':= p(P+Q)/2= 2k²*t' +(Nu+p²) mod 2k².
Multipliziert man mit U folgt letztendlich
X:= (Pu+Q)/2= 2k²*t + U(Nu+p²)/2 mod 2k²

Und mit Y:= (Pu-Q)/2 folgt X² -Y²= PuQ= Nu.)

Wobei für ein gewähltes p sich jeweils r bzw. U und u ergeben.
Weil YY(t)= X(t)² -Nu ergibt sich ein kleinstes t0 mit X(t0)² -Nu >= 0
und damit betrachtet man nur YY(t)=X(t0+t)² -Nu, t=0,1,2,...
Weil eben für alle p aus Z2k* muß man für alle YY((p,q),t) in den jeweiligen Folgen (der Familie) nach Quadraten suchen.

Die Einführung von k erhöht die Suchschrittweite auf 2k²,
aber in phi(2k) Folgen einer Familie.
Das mindert die Effizienz auf nur noch 2k²/phi(k)>k,
aber immerhin besser als linear mit k!

Siehe weiteres Beispiel für N=11111, k=12 und _nur_ p=7:
Es ergibt sich (unter Verwendung des erweiterten euklidischen Algorithmus)
u=23, U=247, r=31, t0=2, X(0)=607 und es ergibt sich sofort

607²-11111*23= 607² -255553= 336² und P=943= 41*u und Q=271

Ich habe den Algorithmus mehrfach (verschiedene k) in EXCEL programmiert.
Er funktioniert leidlich - siehe auch oben. Und auch in C (und Fortran), aber irgendwann braucht man dann eine MPA - multiple precision arithmetic.

Für großes k ergeben sich schon schöne "Fortschritte". Und ja, den Lehman kenne ich natürlich. Ich wollte so auch nicht RSA knacken, aber ich fand diese Idee doch schön!

Man muß nur i.d.R. viele Wurzeln ziehen, aber ich werde _demnächst_ noch zeigen, wie man die stringente Verwendung von quadratischen Resten als exzellenten Filter Verfahren benutzen kann.

Bitte melde Dich doch nochmal mit einem Kommentar.

VG Siggi N



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4043
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-02-19

\(\begingroup\)
2018-02-19 13:56 - Siggi43 in Beitrag No. 2 schreibt:
Ich versuchs nochmal, in der Hoffnung es hilft zum besseren Verständnis.
Meine Erfahrungen mathematische Texte zu schreiben waren wohl nie gut
- Pardon!

Ich denke, es würde auch sehr helfen, wenn du sowas wie einen Anfängerkurs in LaTeX machen würdest, wofür es im Internet unzählige Möglichkeiten gibt z.B. hier , ab S 41, für eine Liste an math. Symbolen, die man für die Verwenung hier nur mit Dollarzeichen einschließen muss. Ich bin mir sicher, dass du dafür nur ein paar Stunden an Einarbeitung benötigen würdest, speziell für deine relativ einfachen Formeln hier!  

X'':= (qP +pQ)/2= 2k²*t'' +(N+pq) mod 2k².
Multipliziert man mit u=pq⁻1 folgt
X':= p(P+Q)/2= 2k²*t' +(Nu+p²) mod 2k².
Multipliziert man mit U folgt letztendlich
X:= (Pu+Q)/2= 2k²*t + U(Nu+p²)/2 mod 2k²

Und mit Y:= (Pu-Q)/2 folgt X² -Y²= PuQ= Nu.)

Du hast dich hier imho verrechnet, denn es ist

$X'=p(P+Qu),\ X=(P+Qu)/2,\ Y=(P-Qu)/2$

wie du speziell für $X$ auch in einem früheren Posting selbst geschrieben hast.


Siehe weiteres Beispiel für N=11111, k=12 und _nur_ p=7:
Es ergibt sich (unter Verwendung des erweiterten euklidischen Algorithmus)
u=23, U=247, r=31, t0=2, X(0)=607 und es ergibt sich sofort

607²-11111*23= 607² -255553= 336² und P=943= 41*u und Q=271

Hm, jetzt kenn ich mich gar nicht mehr aus, denn das würde wieder mit den obigen Formeln übereinstimmen. Wo habe ich mich da geirrt?  confused

Ich habe den Algorithmus mehrfach (verschiedene k) in EXCEL programmiert.
Er funktioniert leidlich - siehe auch oben. Und auch in C (und Fortran), aber irgendwann braucht man dann eine MPA - multiple precision arithmetic.

Du brauchst dafür unbedingt ein CAS um dich nicht um die Länge der Zahlen kümmern zu müssen. Ich empfehle in diesem Zusammenhang immer Maxima, das man gratis im Internet downloaden kann, und das unter Windows auch eine sehr komfortable Ein- und Ausgabe besitzt.  wink
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Siggi43
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 24.10.2016
Mitteilungen: 22
Aus: Hamburg, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-02-20


2018-02-19 13:56 - Siggi43 in Beitrag No. 2 schreibt:
Ich versuchs nochmal, in der Hoffnung es hilft zum besseren Verständnis.
Meine Erfahrungen mathematische Texte zu schreiben waren wohl nie gut
- Pardon!

Ich denke, es würde auch sehr helfen, wenn du sowas wie einen Anfängerkurs in LaTeX machen würdest, wofür es im Internet unzählige Möglichkeiten gibt z.B. hier , ab S 41, für eine Liste an math. Symbolen, die man für die Verwenung hier nur mit Dollarzeichen einschließen muss. Ich bin mir sicher, dass du dafür nur ein paar Stunden an Einarbeitung benötigen würdest, speziell für deine relativ einfachen Formeln hier!  


     Moin moin und nochmal danke, daß Du mit mir diesen Dialog führst.
     Ich habe sowas gesucht, um meine Idee zu diskutieren,
     auch damit sie nicht untergeht (falls was dran ist!).
     Speziell auch danke für den Hinweis zum "LaTeX-Schnellkurs".
     Ich habe vor Jahren schon mal in LaTeX geschrieben,
     davon ist aber wohl nichts mehr übrig. :-(


X'':= (qP +pQ)/2= 2k²*t'' +(N+pq) mod 2k².
Multipliziert man mit u=pq⁻1 folgt
X':= p(P+Q)/2= 2k²*t' +(Nu+p²) mod 2k².
Multipliziert man mit U folgt letztendlich
X:= (Pu+Q)/2= 2k²*t + U(Nu+p²)/2 mod 2k²

Und mit Y:= (Pu-Q)/2 folgt X² -Y²= PuQ= Nu.)



Du hast dich hier imho verrechnet, denn es ist

X′=p(P+Qu), X=(P+Qu)/2, Y=(P−Qu)/2

wie du speziell für X auch in einem früheren Posting selbst geschrieben hast.

     Ja, Pardon, ich habe schon vorher einen Verschreiber:    
     Multipliziert man mit u=pq⁻1 folgt
     X':= p(P+Q)/2= 2k²*t' +(Nu+p²) mod 2k².
     Muß heißen: ...  X':= p(P+Qu)/2= 2k²*t' +(Nu+p²) mod 2k².

     Denn aus Q=(2km +q) wird Qu= (2kl +p) und damit letztlich X=(P+Qu)/2

Siehe weiteres Beispiel für N=11111, k=12 und _nur_ p=7:
Es ergibt sich (unter Verwendung des erweiterten euklidischen Algorithmus)
u=23, U=247, r=31, t0=2, X(0)=607 und es ergibt sich sofort

607²-11111*23= 607² -255553= 336² und P=943= 41*u und Q=271


Hm, jetzt kenn ich mich gar nicht mehr aus, denn das würde wieder mit den obigen Formeln übereinstimmen. Wo habe ich mich da geirrt?  confused

     Da liegt viel Symmetrie in den Formeln.
     Statt u=pq⁻¹(mod 2k) und U=p⁻¹ (mod 2k²)
     ginge auch u= q'p'⁻¹ und U= q'⁻¹.
     Da man für alle p rechnen muß gibt es ein p'q'=s und p'= q⁻¹,
     also auch  q=p'⁻¹ und damit dann u= pq⁻¹= sq⁻²= sp'⁻²= q'p'⁻¹.



Ich habe den Algorithmus mehrfach (verschiedene k) in EXCEL programmiert.
Er funktioniert leidlich - siehe auch oben. Und auch in C (und Fortran), aber irgendwann braucht man dann eine MPA - multiple precision arithmetic.


Du brauchst dafür unbedingt ein CAS um dich nicht um die Länge der Zahlen kümmern zu müssen. Ich empfehle in diesem Zusammenhang immer Maxima, das man gratis im Internet downloaden kann, und das unter Windows auch eine sehr komfortable Ein- und Ausgabe besitzt.  wink

     Da ich sicher bin, daß "mein Verfahren" funktioniert, bringt es      
     nichts es mit einem CAS für größere Zahlen zu rechnen - denke ich.
     Es geht dann ja um Laufzeiten, und ich meine ein CAS ist langsamer
     als eine MPA!?

     Da ich aber auch denke, das die Laufzeit nicht so doll ist,
     braucht's das dafür letztlich auch nicht!
     Dafür habe ich noch eine konsequente Anwendung von quadratischen
     Resten als Filter - ich nenne es (neubertsches) QRS-Verfahren ;-).

     Demnächst auch hier!





  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4043
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-02-20


2018-02-20 16:51 - Siggi43 in Beitrag No. 4 schreibt:
2018-02-19 13:56 - Siggi43 in Beitrag No. 2 schreibt:
Ich versuchs nochmal, in der Hoffnung es hilft zum besseren Verständnis.
Meine Erfahrungen mathematische Texte zu schreiben waren wohl nie gut
- Pardon!

Für das Zitieren von meinen Textpassagen schließe diese bitte mit

{backslash}quoteon

(Zitierter Text)

{backslash}quoteoff

ein, wobei du natürlich {backslash} durch einen echten backslash (auf Tastatur neben ß und natürlich ohne die Klammern {}) ersetzen musst.


   Speziell auch danke für den Hinweis zum "LaTeX-Schnellkurs".
   Ich habe vor Jahren schon mal in LaTeX geschrieben,
   davon ist aber wohl nichts mehr übrig. frown

Ich denke, du wärst in kurzer Zeit wieder drinnen, wenn du das irgendwann schon einmal gekonnt hast! Probiers einfach aus, zunächst einmal nur mit ganz einfachen Formeln, um zu sehen, wie das dann hier aussieht, nämlich gleich viel besser!


     Ja, Pardon, ich habe schon vorher einen Verschreiber:    
     Multipliziert man mit u=pq⁻1 folgt
     X':= p(P+Q)/2= 2k²*t' +(Nu+p²) mod 2k².
     Muß heißen: ...  X':= p(P+Qu)/2= 2k²*t' +(Nu+p²) mod 2k².

     Denn aus Q=(2km +q) wird Qu= (2kl +p) und damit letztlich X=(P+Qu)/2

Ok, dann habe ich schon ein gutes Stück verstanden und mich also doch nicht geirrt!  wink


     Da ich sicher bin, daß "mein Verfahren" funktioniert, bringt es      
     nichts es mit einem CAS für größere Zahlen zu rechnen - denke ich.
     Es geht dann ja um Laufzeiten, und ich meine ein CAS ist langsamer
     als eine MPA!?

     Da ich aber auch denke, das die Laufzeit nicht so doll ist,
     braucht's das dafür letztlich auch nicht!

Zunächst ist ein CAS (=Computer Algebra System) nicht automatisch langsam, das kommt auf die Anwendung an und dann geht es hier ja in erster Linie auch um einen Rechenzeitvergleich. Ich denke, du möchtest doch wissen, wie gut dein Verfahren im Vergleich zu gängigen, das wäre hier die Original Fermatmethode, aber auch die Lehmann-Methode abschneidet, oder etwa nicht?

Vor allem stellt ein CAS schon viele Routinen bereit, die man sonst erst mühsam selbst schreibe müsste. Ich selbst programmiere eigentlich seit Jahren fast ausschließlich in Maple und bin damit sehr zufrieden, allerdings ist das nicht gratis. Der Hauptvorteil ist aber, dass Zahlen im Prinzip beliebig lange sein können, jedenfalls soweit dies der Speicher zulässt und man damit auch symbolisch rechnen kann, was ja mit Excel und auch den meisten gängigen Programmiersprachen leider nicht möglich ist. Von daher würde ich dir den Umstieg auf ein CAS schon sehr empfehlen, da es alles gleich viel einfacher macht!  wink
 



  Profil  Quote  Link auf diesen Beitrag Link
Siggi43 hat die Antworten auf ihre/seine Frage gesehen.
Siggi43 wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]