/* [wxMaxima batch file version 1] [ DO NOT EDIT BY HAND! ]*/
/* [ Created with wxMaxima version 0.8.4 ] */

/* [wxMaxima: input   start ] */
/* Kurzanleitung zur Benutzung dieser Datei mit dem SW-Werkzeug Maxima:
Auswertung eines Befehls durch Hineinklicken und dann shift-Enter druecken.
Zuweisung von Variablen mit <varname>: <Wert>;
Variablen muessen nicht extra deklariert werden.
Sie gelten ab Benutzung in allen Befehlen mit ihren zuletzt zugewiesenen Werten.
Alle Befehle werden in der Reihenfolge ausgewertet, in der sie angeklickt werden
(geht auch mehrfach).
Es kommt nicht darauf an, in welcher Reihenfolge sie hier stehen.
Man kann jederzeit einen Befehl editieren und veraendern und dann wieder auswerten.
Das gilt wie ein neuer Befehl.
Neue Befehle koennen jederzeit an beliebiger Stelle (Position vorher anklicken)
eingefuegt werden.
Die Position eines Befehls in dieser Datei spielt aber keine Rolle.
Wichtig ist alleine die Reihenfolge der Auswertung.
Weitere Erklaerungen ueber Help-Menu von Maxima oder Tutorials im Internet
oder auf dem Handout-Server: https://stud.fh-wedel.de/handout/Iwanowski/ComputerAlgebra/maxima%20tutorials/
Befehle, die wie dieser hier nur aus einem Kommentar bestehen,
muessen nicht ausgewertet werden.
Aber die Auswertung schadet nicht, solange man sich nicht an der incorrect
syntax-Fehlermeldung stoert.
Im Folgenden müssen Sie zunächst alle benötigten Funktionen und Variablen auswerten,
bevor Sie diese benutzen.
*/;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* ermoeglicht eine Zeitmessung fuer die Auswertung der Befehle */
showtime:true;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Erklaerung zum kryptographischen Verfahren RSA (fuer interessierte Leser):
RSA ist ein private-public-key-Verfahren, das eine Botschaft mit Hilfe einer
grossen RSA-Zahl verschluesselt.
Die RSA-Zahl muss aus zwei grossen Primfaktoren zusammengesetzt sein.
Die Verschluesselung und Entschluesselung verlaufen
ueber modulare Arithmetikfunktionen, wobei die RSA-Zahl der oeffentlich
bekannte Modul ist. Eine der beiden Funktionen benutzt eine oeffentlich bekannte Zahl,
die andere eine geheime. Je nach Anwendung kann man damit Botschaften verschicken,
die nur ein bestimmter Empfaenger lesen kann, oder Unterschriften eines bestimmten
Signaturgebers ueberpruefen.
Die verschluesselte Botschaft ist vor unbefugter Entschluesselung sicher,
solange die beiden Faktoren der RSA-Zahl geheim bleiben.
Sonst kann sie leicht geknackt werden, weil das
grundsaetzliche RSA-Verfahren jedem bekannt ist, siehe Wikipedia.
Anmerkung: RSA hat gewisse Anfaelligkeiten.
In moderner Kryptographie werden noch sicherere Verfahren verwendet.
*/
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* die groesste oeffentlich bekannte RSA-Zahl,
gilt als sehr sicher gegen Zerlegungsversuche */
rsa2048: 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* testet, ob Primzahl: */
primep(rsa2048);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* faktorisiert eine Zahl: (Achtung: Das hier kann etwas laenger dauern,
bei erfolgreichem Ende bei Geheimdienst anheuern!) */
factor(rsa2048);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Vorbereitung für eigene Verschlüsselungsversuche: */
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
n1: 68547645316547382384; /* gerne ersetzen Sie diese Zahlen durch andere */
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
n2: 25374892834657634858;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* naechste Primzahl groesser n1 bzw. n2 */
p1: next_prime(n1);
p2: next_prime(n2);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
myRSA: p1 * p2;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
primep(myRSA);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Wenn es keine kleinen Primfaktoren gibt,
dauert auch die Faktorisierung nicht so grosser Zahlen lange: */
factor(myRSA);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
-------------------------------------------------------------------------------------

/* Definition eigener Funktionen,
vor dem Benutzen der unten angegebenen Befehle einmal auswerten durch shift-Enter: */
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* findet die ersten beiden Primzahlen, die sich um diff unterscheiden */
firstPrimesDiffering(diff) := block(
   [p,pDiff], /* local variables */
   p: 2,
   pDiff: 2+diff,
   if (not primep (pDiff) and (mod(diff,2) = 1))
      then false
      else
         (while not primep(pDiff) do
            (p: next_prime(p),
             pDiff: p+diff),
          [p,pDiff]));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* findet die ersten beiden hintereinanderfolgenden Primzahlen,
   die sich um diff unterscheiden */
firstConsecPrimesDiffering(diff) := block(
   [p,nextp], /* local variables */
   if (diff = 0) then false
   else if (diff = 1) then [2,3]
   else if (mod(diff,2) = 1) then false
   else
      (p: 3,
       nextp: 5,
       while (not (nextp-p = diff)) do
         (p: nextp,
          nextp: next_prime(p)),
       [p,nextp]));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
firstPrimesDiffering(1007);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
firstConsecPrimesDiffering(100);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* gibt alle zu n teilerfremden (auf Englisch: prime to) Zahlen aus */
primeDivisors (n):= block(
   [divisor,result], /* local variables */
   divisor: 1,
   result: [],
   while divisor <= n do
      (if (gcd(divisor,n) = 1) then result: cons (divisor, result),
       divisor: divisor + 1),
   reverse(result));
/* phi(n) ist die Anzahl der zu n teilerfremden Zahlen */
phi (n) := length (primeDivisors(n));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
primeDivisors (100);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
phi(100);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* gibt eine Liste aller Zahlen k aus, sodass phi(k)=n.
   upperLimit ist die obere Schranke für k, bis wohin gesucht werden soll. */
numbersWithThisPhiUL (n,upperLimit) := block(
   [number, result], /* local variables */
   number: 1,
   result: [],
   while number < upperLimit do
      (if (phi(number) = n) then result: cons (number, result),
       number: number + 1),
   reverse(result));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* 4 n^2 ist die maximale obere Schranke für Kandidaten k mit phi(k)=n,
   aber meistens ist das viel zu groß.
   Daher sollte man das zur Beschleunigung mit numbersWithThisPhiUL
   mit einer kleineren Schranke einschränken. */
numbersWithThisPhi (n) := numberWithThisPhiUL (n, 4*n*n);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
numbersWithThisPhi (6);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
numbersWithThisPhiUL (16,61);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Tests mit der logarithmischen Schranke für das Vorkommen von Primzahlen: */
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
primesBetween (n,m):= block(
   [p,result], /* local variables */
   p: next_prime(n-1),
   result: [],
   while p <= m do
      (result: cons (p, result),
       p: next_prime(p)),
   reverse(result));
primesLessThan(n):= primesBetween (2,n);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Hier kann der Parameter fuer die Primzahlen festgelegt werden:
Es sollte mit verschiedenen Werten fuer n gearbeitet werden. */
n: 1000000;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Bestimme alle Primzahlen kleiner gleich n: */
primes: primesLessThan (n);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Anzahl der Zahlen in primes: */
anzahl: length (primes);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Erklaerung zum naechsten Befehl (fuer interessierte Nutzer, sonst einfach ausfuehren):
Hier werden 2 Anweisungen auf einmal ausgefuehrt (getrennt durch ;).
% ergibt den Wert der letzten ausgefuehrten Auswertung,
numer wertet den exakten Ausdruck numerisch aus.
Der Logarithmus ist zur Basis e, in Maxima dagestellt durch %e
(analoge Konstantendefinitionen: %pi, %i)
*/;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* logarithmische Abschaetzung: */
abschaetzung: n / log(n), numer;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
anzahl/abschaetzung, numer;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Hier kann eine neue Primzahl an p1 zugewiesen werden.
Ersetzen Sie 123456789 gerne durch eine andere Zahl */
p1: next_prime(123456789);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
p1: p1Nachfolger;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
p1Nachfolger: next_prime(p1);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
p1Nachfolger - p1;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Die naechste Zahl ergibt den durchschnittlichen Abstand von p1 zum Nachfolger
(jede ln (p1)-te Zahl ist eine Primzahl)
Vergleichen Sie mit der Differenz oben */
log(p1), numer;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
/* Die Differenz ist meistens kleiner und kann sogar nur 2 betragen.
Ein realistischerer Vergleich ist es, die Anzahl der letzten 10000 Primzahlen
vor p1 mit der logarithmischen Schranke für p1 zu vergleichen. */
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
anzahlLetzte10000: length (primesBetween(p1-10000,p1));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
10000/log(p1), numer;
/* [wxMaxima: input   end   ] */

/* Maxima can't load/batch files which end with a comment! */
"Created with wxMaxima"$