--------------------------------------------------------------------------------
directly from my Sun workstation ULTRA 1 under SunOS 5.5.1 and CDE V 1.0.2
--------------------------------------------------------------------------------
An alle DMUG-Leser ! Stuttgart, den 8. Januar 2001
In einer eMail vom 14.12.2000 fragte Herr Dr. Jentschura nach der Primzahlen-
zerlegung einer recht grossen Zahl :
xx1 = 18402786717172645644535779054968269097752223096614652509534106463;
Ich faktorisierte diese Zahl als Test fuer Mathematica 4.0 auf einer SUN Work-
station ULTRA_1 unter SunOS 5.5.1 ueber die Weihnachtszeit. Diese Workstation
lief unter der Unix-Betriebssystemvariante SunOS ueber den erforderlichen Zeit-
raum stabil durch.
Die Zerlegung dieser Zahl finden Sie im Anhang.
Vielleicht waere es sinnvoll, den Algorithmus FactorInteger so mit Optionen zu
versehen, dass er auf Anfrage mitteilen kann, welche Zerlegung er im Augenblick
der Abfrage versucht, und dass er die jeweils bekannten Faktoren schon dann
angeben kann, wenn sie vorliegen.
Das waere in der praktischen Anwendung sicher vorteilhaft !
Solche grossen Zahlen koennen in verschiedenen Zusammenhaengen verwendet
werden. Dazu erkundigte ich mich vorab bei Herrn Dr. Maeder. Sie finden seine
freundliche Erklaerung ebenfalls im Anhang !
Mit freundlichen Gruessen,
Gunter Woysch File : mail_01/dmug_010108_email_to
--------------------------------------------------------------------------------
Dr. G. Woysch ASIC Technology and Qualification
c/o Alcatel SEL AG VLSI Layout Verification
Research Center VLSI Interconnects
ZFZ/TM
Holderaeckerstr. 35 Phone +49-711- 821 32176
D-70499 Stuttgart Fax +49-711- 821 32455
Germany eMail gwoysch@XXXXXXX.de
--------------------------------------------------------------------------------
----- Begin Included Message -----
Date: Thu, 14 Dec 2000 12:06:53 +0100 (NFT)
From: Ulrich Jentschura <ulj@XXXXXXX.fr>
To: dmug@XXXXXXX.ch
Subject: FactorInteger[]
Sehr geehrte Mathematica-Freunde,
ich stehe vor dem Problem, die Primzahlen-Zerlegung der folgenden
Zahl zu suchen,
18402786717172645644535779054968269097752223096614652509534106463
Wenn ich mit FactorInteger herangehe, so braucht Mathematica auch auf
einem recht schnellen Rechner (IBM RISC/6000 mit 300 MHz) unverhaeltnis-
maessig lange. Durch Herumprobieren findet man schnell heraus, dass
zumindest zweimal die 7 und einmal die 3 in der Primfaktorzerlegung der
obigen Zahl vorkommt, und dass fuer weitere Primfaktoren gilt:
p > 2750159 = Prime[200000]
Daher die Frage: Wie geht die Zerlegung weiter?
Falls jemand (a) eine Idee hat, wie man FactorInteger im obigen Fall
beschleunigen kann, oder (b) das Problem anderweitig loesen kann, so
waere ich fuer eine kurze Info sehr dankbar.
Gruss,
Ulrich Jentschura
P.S.: Mein Herumprobieren fuehrte auf das folgende naive Programm:
xx1 = 18402786717172645644535779054968269097752223096614652509534106463;
xx2 = Table[Prime[n],{n,1,200000}];
xx3 = xx1/xx2;
xx4 = Table[{Prime[n],xx3[[n]]},{n,1,200000}];
xx5 = Select[xx4, IntegerQ[#[[2]]]&];
---------------------------------------------------------
Dr. Ulrich Jentschura
Laboratoire Kastler-Brossel, Case 74
4 Place Jussieu, F-75252 Paris Cedex 05
Paris/France
Voice 0033-1-44 27 43 96
Institut fuer Theoretische Physik, 01062 Dresden, Germany
Tel. +49-351-463 40 02, Fax +49-351-463 72 99
jentschura@XXXXXXX.de, ulj@XXXXXXX.gov
http://www.phy.tu-dresden.de/itp/members/jentschura.html
---------------------------------------------------------
----- End Included Message -----
----- Begin Included Message -----
In[1] := Timing[FactorInteger[
18402786717172645644535779054968269097752223096614652509534106463 ] ]
Out[1] = {859674. Second, {{3, 2}, {7, 2}, {1406956463719,
1}, {109522253082122323037981, 1}, {270808302454534186160412037, 1}}}
In[2] := 3 * 3 * 7 * 7 * 1406956463719 * 109522253082122323037981 * \
270808302454534186160412037
Out[2] = 18402786717172645644535779054968269097752223096614652509534106463
----- End Included Message -----
----- Begin Included Message -----
Von: Roman Maeder, INTERNET:maeder@XXXXXXX.ch
An: Gunter Woysch, Gunter_Woysch
Datum: Son, 7. Jan 2001 7:31:02
Empf.: Re: FactorInteger[ 65 Stellen dezimal ]
Sender: maeder@XXXXXXX.ch
To: Gunter Woysch
Subject: Re: FactorInteger[ 65 Stellen dezimal ]
Sehr geehrter Herr Woysch,
Ihr Ergebnis ist sehr interessant, allerdings sind 65-stellige Zahlen,
also 215 Bit, für kryptographische Anwendungen viel zu klein, es besteht
also keine Gefahr, dass Ihr Resultat in falschen Händen irgendwelche
Konsequenzen hat. Außerdem hat die gesagt Zahl ja einige kleine
Primfaktoren,
was bei kryptographischen Anwendungen nicht vorkommen würde.
Warum schreiben sie nicht darüber an die DMUG!
Das Minimum an Bits, das als genügend sicher gilt, ist ca. 700;
Standard sind 1000bit, also 300 Dezimalstellen. Mit den besten Algorithmen
kann man heute mit einem Aufwand von mehreren CPU-Jahren etwa 120-stellige
Zahlen faktorisieren.
mit freundlichen Grüßen,
Roman Mäder
----- End Included Message -----
DMUG-Archiv, http://www.mathematica.ch/archiv.html