Discussion:
Das Neubert-Verfahren zur Faktorisierung - Ein simples Beispiel mit kleinem k.
(zu alt für eine Antwort)
Siegfried Neubert
2018-02-18 15:54:31 UTC
Permalink
Raw Message
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².

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. des Modul 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?
Jens Kallup
2018-02-18 18:02:45 UTC
Permalink
Raw Message
Post by Siegfried Neubert
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).
Als ich noch für den Amiga 500 programmiert hatte,
verwendete ich für immer wieder vorkommende Zahlen
eine oder mehrere Look-Up Tabellen.

Das sind dann so die Referenz-Dinger, einmal
berechnet, und schon braucht man sich nicht mehr
den Rest bzw. um den Anfang kümmern, damit
verkürzt sich die Zeit von Berechnungen, die
immer wieder vorkommen.

Schön war dies bei 3D Spielen, mit denen man mit
Sinus, und Cosinus und Co. arbeiten will bzw.
muss.

Irgendwo hab ich noch was, das sich ein Zyklus
entwickelt; also die gleichen Zahlenreihen entstehen;
so ähnlich wie 1/3.

Ich traue den heutigen Computern nicht mehr so,
da bei Gleitkommazahlen nur bis 5 Stellen nach dem
Komma stabil gerechnet wird.
Oder C ist daran schuld, das die Feinschritte für
Allgemeine Computer-Anwendungen keine Präzissen
Werte nötig sind.

Nun gut, hab nur mal meinen Senf wieder geben wollen.

Gruß
Jens

Loading...