XProfan

Deutsch

p.specht

Jede beliebige natürliche Zahl lässt sich in Primzahl-Faktoren zerlegen. Diese Tatsache ist Mathematikern unter dem von Gauss geprägten Begriff "Fundamentalsatz der Arithmetik" bekannt. Je größer die Zahl, um so quadratisch-überproportional zeitaufwändig wird diese Zerlegung aber, denn bisher wurde kein auch für riesige Ganzzahlen funktionierender rascher Faktorisierungsalgorithmus bekannt. Genau deshalb kann man damit wirksam Nachrichten verschlüsseln, denn nur derjenige, dem die Primfaktoren bekannt gegeben werden (z.B. einer von zwei großen Faktoren plus ein öffentlicher Schlüssel), der kann die Botschaft in vernünftiger Zeit wieder entschlüsseln. Bei nicht allzu großen Zahlen ist eine Zerlegung jedoch in kurzer Zeit möglich, wie das nachstehende in XProfan-11 übersetzte Progrämmchen beweist.

Nachsatz: Selbst heutige Supercomputer oder sogar Quantencomputer schaffen eine Zerlegung wirklich großer Zahlen nicht in militärisch interessanter Zeit (Wenn die Schlacht vorbei ist, hat nämlich niemand mehr was davon). Allerdings sollten wir die Findigkeit der Crypto-Experten nicht unterschätzen: Jemand hat z.B. vor einiger Zeit einen derartigen Code geknackt, in dem er ihn als DNA-Strang synthetisierte. Anschließend wurde dieser billionenfach geklont (heute kein Problem mehr, dauert ca. 19 Stunden) und schließlich durch Einsatz verschiedener Enzyme, die große Primzahlen kodieren 8O und sich an den Strang anlagern, die fehlende Zahl herausgefiltert - somit der Code geknackt!

Kompilieren Markieren Separieren

WindowTitle upper$("Faktorisierung von natürlichen Zahlen")
' *******************************************
'* Sample run:                               *
'* ? 394616                                  *
'*     2 2 2 107 461                         *
'* ----------------------------------------- *
'* Ref.: "Mathématiques par l'informatique   *
'*        individuelle (1) par H. Lehning    *
'*        et D. Jakubowicz, Masson, Paris,   *
'*        1982"                                   *
'* ----------------------------------------- *
'*               C++ version by J-P Moreau.  *
'*                    (www.jpmoreau.fr)      *
'*   XProfan Version by P.Specht, Wien (AT)  *
'*     Ohne Gewähr! No warranty whatsoever!  *
'* ----------------------------------------- ********
'* Gegenprüfungsmöglichkeit:                         *
'* https://de.numberworld.info/faktorisierungsRechner *
' ***************************************************
set("decimals",0):windowStyle 24:font 2
Declare d!,eps!,m!,n!,i!:eps!=0.000001
start:
Cls:print
rept:
'print " Integer number to be factorized ?: ";:input n!
print " Integerzahl, die in Primfaktoren zerlegt werden soll ?: ";:input n!
case n!<0:End
case n!=0:n!=4294967295

if n!>4294967295:print " *** Overflow Error ***\n" : goto "rept":endif

    print "   ";
    e50:
    d!=n!-2*intf(n!/2)

    if (abs(d!)<eps!): print "2 ";: n!=n!/2: goto "e50":endif

        e100:
        d!=n!-3*intf(n!/3)

        if abs(d!)<eps!:print "3 ";: n!=n!/3: goto "e100":endif

            ' // All Prime numbers >3 are of the form 6i-1 or 6i+1
            m!=floor(sqrt(n!))+1
            i!=6

            while i!<(m!+1)

                e150:
                d!=n!-(i!-1)*intf(n!/(i!-1))

                if (abs(d!)<eps!) :print i!-1,: n!=n!/(i!-1): goto "e150":endif

                    e200:
                    d!=n!-(i!+1)*intf(n!/(i!+1))

                    if (abs(d!)<eps!):print i!+1,: n!=n!/(i!+1): goto "e200":endif

                        i!=i!+6

                    endwhile

                    case (n!>1):print n!,
                    print

                    if %csrlin>32:waitinput :goto "start":endif

                        goto "rept"
                        END
                        '===================== Math2.inc ==========================================

                        proc Sgn :parameters x!:return (x!>0)-(x!<0):endproc

                            proc floor :parameters x!:case abs(x!)<(10^-35):return 0:case x!>0

                                return intf(x!):return (abs(x!-intf(x!)) < 10^-35)-intf(abs(x!-1)):endproc

                                proc ceil :parameters x!:return -1*floor(-1*x!):endproc

                                    proc modf :parameters x!,y!:case abs(x!)<10^-35:return 0

                                        case abs(y!)<10^-35:return x!:return sgn(y!)*abs(x!-y!*floor(x!/y!)):endproc

                                        proc remn :parameters x!,y!:case abs(x!)<(10^-35):return 0

                                            case abs(y!)<(10^-35):return x!:return sgn(x!)*abs(x!-y!*floor(x!/y!)):endproc

                                            proc IsNeg :parameters x!:return byte(Addr(x!),7)&%10000000>>7:endproc

                                                proc frac :parameters x!:var s!=sgn(x!):x!=abs(x!):x!=x!-round(x!,0)

                                                    case x!<0:x!=1+x!:return s!*x!:endproc

                                                    proc intf :parameters x!:var s!=sgn(x!):x!=abs(x!):x!=x!-frac(x!):return s!*x!

                                                    endproc

                                                    '============================================================================