Finden von Teilern von großen Zahlen ...

20/01/2013 - 20:51 von Walter H. | Report spam
Hallo,

nur mal ein Gedanke:

wir haben ein Stellenwertsystem, z.B. eine 5 stellige und eine 6
stellige Zahl:

abcde und uvwxyz

a bis e und u bis z sind jeweils Ziffern;
aus der Menge A = {0,1,2,3,4,5,6,7,8,9}

dann lautet die eine geschrieben ja auch
a * 10^4 + b * 10^3 + c * 10^2 + d * 10 + e
und die andere
u * 10^5 + v * 10^4 + w * 10^3 + x * 10^2 + y * 10 + z

multipliziert man jetzt diese beiden

( u * 10^5 + v * 10^4 + w * 10^3 + x * 10^2 + y * 10 + z ) ( a * 10^4 +
b * 10^3 + c * 10^2 + d * 10 + e ) ergibt dies

au 10^9 + ( av + bu ) 10^8 + ( aw + bv + cu ) 10^7 +
( ax + bw + cv + du ) 10^6 +
( ay + bx + cw + dv + eu ) 10^5 +
( az + by + cx + dw + ev ) 10^4 +
( bz + cy + dx + ew ) 10^3 +
( cz + dy + ex ) 10^2 + ( dz + ey ) 10 + ez

damit ist doch eindeutig festgelegt, daß die Einerstelle des Produkts
nur das Ergebnis aus den Einstellen der Faktoren sein kann;



damit kann man doch die Suche von Teilern hinten beginnen ...

hat man jetzt eine große Zahl, welche es gilt in deren Primfaktoren zu
spalten, dann kann man doch bei den niederwertigsten Stellen beginnen;

828643570103799269582641 ist das Produkt 2er Primzahlen;

die beiden letzten Stellen der beiden Primzahlen lauten jeweils
37 und 93
das Produkt dieser beiden ergibt 3441

die letzten 6 Stellen des Produkts lauten 582641
der eine Faktor (x * 100 + 37) und der andere (y * 100 + 93)
mit x und y jeweils aus der Menge A wie oben
deren Produkt 10000 xy + 100 ( 93 x + 37 y ) + 3441
welches man von den letzten 6 Stellen subtrahiert

582641 - ( 10000 xy + 100 ( 93 x + 37 y ) + 3441 ) 579200 - ( 10000 xy + 100 ( 93 x + 37 y ) ) 100 ( 5792 - 100 xy - 93 x - 37 y )

das Problem reduziert sich auf den Ausdruck in der Klammer

5792 - 100 xy - 93 x - 37 y
dabei muss x und y so gewàhlt werden daß diese Differenz durch 10 od.
-10 teilbar ist;
für x = 6 und y = 2 ist dies der Fall
(ebenfalls für x = 9 und y = 5,
x = 8 und y = 4,
x = 7 und y = 3,
x = 5 und y = 1,
x = 4 und y = 0,
x = 3 und y = 9,
x = 2 und y = 8,
x = 1 und y = 7,
x = 0 und y = 6)
hier ein "falscher" nàchster Schritt, indem nicht x = 6 und y = 2
genommen werden sondern x = 9 und y = 5
ich kenne in dem Fall die beiden Primfaktoren

man nimmt die letzten 8 Ziffern des Produkts 69582641
der eine Faktor lautet jetzt (x * 1000 + 937) und
der andere (y * 1000 + 593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 1000000 xy + 1000 ( 593 x + 937 y ) + 555641
welches man jetzt von den letzten 8 Stellen subtrahiert
ergibt
1000 ( 69027 - 1000 xy - 593 x - 937 y )
wieder nur der Ausdruck in der Klammer
69027 - 1000 xy - 593 x - 937 y
(for x = 9 und y = 0
x = 8 und y = 9,
x = 7 und y = 8,
x = 6 und y = 7,
x = 5 und y = 6,
x = 4 und y = 5,
x = 3 und y = 4,
x = 2 und y = 3,
x = 1 und y = 2,
x = 0 und y = 1)

eine Möglichkeit ausgewàhlt (x = 7, y = 8) und für den nàchsten Schritt
verwendet

man nimmt die letzten 10 Ziffern des Produkts 9269582641
der eine Faktor lautet jetzt (x * 10000 + 7937) und
der andere (y * 10000 + 8593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 100000000 xy + 10000 ( 8593 x + 7937 y ) + 68202641
welches man jetzt von den letzten 10 Stellen subtrahiert
ergibt
10000 ( 920138 - 10000 xy - 8593 x - 7937 y )
wieder nur der Ausdruck in der Klammer
920138 - 10000 xy - 8593 x - 7937 y
(for x = 9 und y = 3
x = 8 und y = 2,
x = 7 und y = 1,
x = 6 und y = 0,
x = 5 und y = 9,
x = 4 und y = 8,
x = 3 und y = 7,
x = 2 und y = 6,
x = 1 und y = 5,
x = 0 und y = 4)

eine Möglichkeit ausgewàhlt (x = 5, y = 9) und für den nàchsten Schritt
verwendet

man nimmt die letzten 12 Ziffern des Produkts 799269582641
der eine Faktor lautet jetzt (x * 100000 + 57937) und
der andere (y * 100000 + 98593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 10000000000 xy + 100000 ( 98593 x + 57937 y ) +
68202641
welches man jetzt von den letzten 12 Stellen subtrahiert
ergibt
100000 ( 7935574 - 100000 xy - 98593 x - 57937 y )
wieder nur der Ausdruck in der Klammer
7935574 - 100000 xy - 98593 x - 57937 y
(for x = 9 und y = 1
x = 8 und y = 0,
x = 7 und y = 9,
x = 6 und y = 8,
x = 5 und y = 7,
x = 4 und y = 6,
x = 3 und y = 5,
x = 2 und y = 4,
x = 1 und y = 3,
x = 0 und y = 2)

eine Möglichkeit ausgewàhlt (x = 4, y = 6) und für den nàchsten Schritt
verwendet

man nimmt die letzten 14 Ziffern des Produkts 03799269582641
der eine Faktor lautet jetzt (x * 1000000 + 457937) und
der andere (y * 1000000 + 698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 1000000000000 xy + 1000000 ( 698593 x + 457937 y
) + 319911582641
welches man jetzt von den letzten 14 Stellen subtrahiert
ergibt
1000000 ( 3479358 - 1000000 xy - 698593 x - 457937 y )
wieder nur der Ausdruck in der Klammer
3479358 - 1000000 xy - 698593 x - 457937 y
(for x = 9 und y = 3
x = 8 und y = 2,
x = 7 und y = 1,
x = 6 und y = 0,
x = 5 und y = 9,
x = 4 und y = 8,
x = 3 und y = 7,
x = 2 und y = 6,
x = 1 und y = 5,
x = 0 und y = 4)

eine Möglichkeit ausgewàhlt (x = 5, y = 9) und für den nàchsten Schritt
verwendet

man nimmt die letzten 16 Ziffern des Produkts 0103799269582641
der eine Faktor lautet jetzt (x * 10000000 + 5457937) und
der andere (y * 10000000 + 9698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 100000000000000 xy + 10000000 ( 9698593 x +
5457937 y ) + 52934309582641
welches man jetzt von den letzten 16 Stellen subtrahiert
ergibt
10000000 ( 5086496 - 10000000 xy - 9698593 x - 5457937 y )
wieder nur der Ausdruck in der Klammer
5086496 - 10000000 xy - 9698593 x - 5457937 y
(for x = 9 und y = 7
x = 8 und y = 6,
x = 7 und y = 5,
x = 6 und y = 4,
x = 5 und y = 3,
x = 4 und y = 2,
x = 3 und y = 1,
x = 2 und y = 0,
x = 1 und y = 9,
x = 0 und y = 8)

eine Möglichkeit ausgewàhlt (x = 0, y = 8) und für den nàchsten Schritt
verwendet

man nimmt die letzten 18 Ziffern des Produkts 570103799269582641
der eine Faktor lautet jetzt (x * 10000000 + 05457937) und
der andere (y * 10000000 + 89698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 10000000000000000 xy + 100000000 ( 89698593 x +
05457937 y ) + 489569269582641
welches man jetzt von den letzten 18 Stellen subtrahiert
ergibt
100000000 ( 5696142300 - 100000000 xy - 89698593 x - 05457937 y )
wieder nur der Ausdruck in der Klammer
5696142300 - 100000000 xy - 89698593 x - 05457937 y
(for x = y )

eine Möglichkeit ausgewàhlt (x = y = 0) und für den nàchsten Schritt
verwendet

man nimmt die letzten 20 Ziffern des Produkts 43570103799269582641
der eine Faktor lautet jetzt (x * 100000000 + 005457937) und
der andere (y * 100000000 + 089698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 1000000000000000000 xy + 1000000000 ( 089698593
x + 005457937 y ) + 489569269582641
welches man jetzt von den letzten 20 Stellen subtrahiert
ergibt
1000000000 ( 43569614230 - 1000000000 xy - 089698593 x - 005457937 y )
wieder nur der Ausdruck in der Klammer
43569614230 - 1000000000 xy - 089698593 x - 005457937 y
(for x = y )

eine Möglichkeit ausgewàhlt (x = y = 0) und für den nàchsten Schritt
verwendet

man nimmt die letzten 22 Ziffern des Produkts 8643570103799269582641
der eine Faktor lautet jetzt (x * 1000000000 + 0005457937) und
der andere (y * 1000000000 + 0089698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 100000000000000000000 xy + 10000000000 (
0089698593 x + 0005457937 y ) + 489569269582641
welches man jetzt von den letzten 22 Stellen subtrahiert
ergibt
10000000000 ( 864356961423 - 10000000000 xy - 0089698593 x - 0005457937 y )
wieder nur der Ausdruck in der Klammer
864356961423 - 10000000000 xy - 0089698593 x - 0005457937 y
(for x = 9 und y = 8
x = 8 und y = 7,
x = 7 und y = 6,
x = 6 und y = 5,
x = 5 und y = 4,
x = 4 und y = 3,
x = 3 und y = 2,
x = 2 und y = 1,
x = 1 und y = 0,
x = 0 und y = 9)

eine Möglichkeit ausgewàhlt (x = 1 und y = 0) und für den nàchsten
Schritt verwendet

man nimmt die letzten 24 Ziffern (= alle Ziffern) des Produkts
828643570103799269582641
der eine Faktor lautet jetzt (x * 10000000000 + 10005457937) und
der andere (y * 10000000000 + 00089698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 10000000000000000000000 xy + 100000000000 (
00089698593 x + 10005457937 y ) + 897475499269582641
welches man jetzt von den letzten 24 Stellen (= allen Stellen)
subtrahiert ergibt
10^11 ( 8286426726283 - 10^11 xy - 00089698593 x - 10005457937 y )
wieder nur der Ausdruck in der Klammer
8286426726283 - 10^11 xy - 00089698593 x - 10005457937 y
(for x = 9 und y = 8
x = 8 und y = 7,
x = 7 und y = 6,
x = 6 und y = 5,
x = 5 und y = 4,
x = 4 und y = 3,
x = 3 und y = 2,
x = 2 und y = 1,
x = 1 und y = 0,
x = 0 und y = 9)

eine Möglichkeit ausgewàhlt (x = 1 und y = 0) und für den nàchsten
Schritt verwendet

alle Ziffern des Produkts 828643570103799269582641
der eine Faktor lautet jetzt (x * 10^11 + 110005457937) und
der andere (y * 10^11 + 000089698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 10^22 xy + 10^11 ( 000089698593 x + 110005457937
y ) + 9867334799269582641
welches man jetzt von allen Stellen subtrahiert ergibt
10^11 ( 8286337027690 - 10^11 xy - 000089698593 x - 110005457937 y )
wieder nur der Ausdruck in der Klammer
8286337027690 - 10^11 xy - 000089698593 x - 110005457937 y
(for x = y )

eine Möglichkeit ausgewàhlt (x = y = 1) und für den nàchsten Schritt
verwendet

alle Ziffern des Produkts 828643570103799269582641
der eine Faktor lautet jetzt (x * 10^12 + 1110005457937) und
der andere (y * 10^12 + 1000089698593)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 10^24 xy + 10^12 ( 1000089698593 x +
1110005457937 y ) + 1110105023864799269582641

und hier ist der Widerspruch, weil das Produkt deutlich größer ist als
die ursprüngliche Zusammengesetzte Zahl;
warum kommt der Widerspruch so spàt und nicht schon viel früher?

hier jetzt der nàchste richtige Schritt,
man nimmt die letzten 8 Ziffern des Produkts 69582641
der eine Faktor lautet jetzt (x * 1000 + 637) und
der andere (y * 1000 + 293)
mit x und y jeweils aus der Menge A wie oben
deren Produkt ist jetzt 1000000 xy + 1000 ( 293 x + 637 y ) + 186641
welches man jetzt von den letzten 8 Stellen subtrahiert
ergibt
1000 ( 69396 - 1000 xy - 293 x - 637 y )
wieder nur der Ausdruck in der Klammer
69396 - 1000 xy - 293 x - 637 y
hier ist x = 5 und y = 3
(auch für x = 9 und y = 7,
x = 8 und y = 6,
x = 7 und y = 5,
x = 6 und y = 4,
x = 4 und y = 2,
x = 3 und y = 1,
x = 2 und y = 0,
x = 1 und y = 9,
x = 0 und y = 8)

und so weiter

...

ein paar Schritte weiter

die letzten 10 Stellen des einen Faktors 2195345637
und die letzten 10 Stellen des anderen Faktors 7937203293
das sind die letzten 22 Stellen des Produkts 8643570103799269582641

der eine Faktor lautet jetzt (x * 10^10 + 2195345637) und
der andere (y * 10^10 + 7937203293)
mit x und y jeweils aus der Menge A wie oben
das Produkt dieser beiden Faktoren lautet jetzt
10^20 xy + 10^10 ( 7937203293 x + 2195345637 y ) + 17424904619269582641
dies von den letzten 22 Stellen des Produkts subtrahiert ergibt

10^10 ( 862614519918 - 10^10 xy - 7937203293 x - 2195345637 y )

jetzt reduziert sich das Problem wieder auf den Ausdruck in der Klammer

862614519918 - 10^10 xy - 7937203293 x - 2195345637 y

da x und y Ziffern sind, der Term durch 10 od. -10 teilbar sein soll;

was passiert wenn wir das Problem reduzieren, indem man einfach die
vorderen Stellen entsprechend kappt

9918 - 93 x - 37 y

es àndert am Ergebnis nichts ...
es ergeben sich damit folgende Paare (0;4), (1;5), (2;6), (3;7), (4;8),
(5;9), (6;0), (7;1), (8;2), (9;3)


kommt man mit diesem Schema, Algorithmus schneller zu den Primteilern
von sehr großen zusammengesetzten Zahlen?
verkürzt sich das Finden von Primteilern?

ist RSA in Gefahr, welches ja letztendlich darauf beruht, daß das Finden
von Primteilern sehr großer Zahlen ein schwieriges bzw. momentan bei
entsprechenden Schlüsseln (4096 bit) nur bei entsprechenden Resourcen
überhaupt möglich ist;

das Finden von Primteilern einer RSA-768 Zahl mit 100000 Rechnern etwa
ein halbes Jahr
(siehe hier: http://www.rsa.com/rsalabs/node.asp?id 94)

Grüße,
Walter
 

Lesen sie die antworten

#1 Helmut Richter
20/01/2013 - 23:10 | Warnen spam
On Sun, 20 Jan 2013, Walter H. wrote:

damit kann man doch die Suche von Teilern hinten beginnen ...

hat man jetzt eine große Zahl, welche es gilt in deren Primfaktoren zu
spalten, dann kann man doch bei den niederwertigsten Stellen beginnen;

828643570103799269582641 ist das Produkt 2er Primzahlen;



Richtig. 77937203293 * 10632195345637

die beiden letzten Stellen der beiden Primzahlen lauten jeweils
37 und 93



Wenn du die beiden Faktoren schon weißt, brauchst du sie nicht mehr zu
suchen. Wenn du sie noch nicht weißt, kannst du nur sagen, dass man die
letzten 2 Stellen der einen ausrechnen kann, wenn die letzten 2 Stellen der
anderen gegeben sind.

In deinem Beispiel folgt daraus, dass eine die Endziffern 37 hat, dass die
andere die Endziffern 93 hat und umgekehrt. Sonst nichts.

Hàtte eine die Endziffern 19 oder 73, hàtte eben die andere die Endziffern 39
bzw. 17. Eine von beiden kann alles als Endzifferpaar haben, was überhaupt am
Ende einer Primzahl stehen kann (Endziffer 1, 3, 7, 9, davor beliebig), die
andere ergibt sich daraus eindeutig. Für die Zerlegung hilft das genau gar
nichts. Und so bleibt es, wenn man làngere Ketten von Endziffern betrachtet.

Helmut Richter

Ähnliche fragen