Goldbach Vermutung



  • Bengo schrieb:

    Ich habe gerade die Befürchtung, dass dieser ganze Milleralgo bei der mod_pow Funktion gar keinen richtigen Vorteil mehr bringt.

    Doch.
    Millimiller (also strake Pseudoprimzahlen) ist schneller und viel stärker als nur Pseudoprimzahlen wie in https://www.c-plusplus.net/forum/333757-19

    Gegen 2^64 kackt TrialDivision natürlich total ab. Aber auch Eratostenes kackt wonderbar ab. Bei Miller muss man immer schauen, was gemeint ist. Deswegen hab ich Millimillerrabin als Wort erfunden, damit klar ist, daß man hier nur einen SPRP-Test macht, statt bis unten hin zu millern und dennoch nicht ganz sicher ist. Nur der eine SPRP-Test macht nicht sicher, dazu doch die Lügner-Liste.



  • Welches BS, welcher Compiler, welcher Prozessor?

    Windows 7

    MS VS 2015 Community

    Intel Core i7 3930K (Sandy Bridge-E) mit 6 echten und 12 virtuellen Kernen (cpu noch bei 8%)

    3,2 GHz (könnte man sicher tunen)
    32 GB RAM (bitset bis 200 Mrd. passt hier rein, Berechnung 52 min., Laden fehlt noch, z.Z. nicht notwendig)

    MMX, SSE, SSE2, SSE3, SSSE3, SSE 4.1 u. 4.2, EM64T, VT-x, AES, AVX (hier habe ich AVX2 eingestellt bei Optimierung)



  • Erhard Henkes schrieb:

    Nochmal zur praktischen Klarstellung:
    x86 mit dem C-code für mulmod:
    `

    Now Goldbach first prime number pair will be detected

    2000000000000000000 601 1999999999999999399 time: 10 ms

    2000000000000000002 131 1999999999999999871 time: 4 ms

    2000000000000000004 593 1999999999999999411 time: 9 ms

    2000000000000000006 397 1999999999999999609 time: 8 ms

    2000000000000000008 137 1999999999999999871 time: 4 ms

    2000000000000000010 139 1999999999999999871 time: 4 ms`

    x32 mit dem asm code für mulmod:
    `

    Now Goldbach first prime number pair will be detected

    2000000000000000000 601 1999999999999999399 time: 41 ms

    2000000000000000002 131 1999999999999999871 time: 13 ms

    2000000000000000004 593 1999999999999999411 time: 41 ms

    2000000000000000006 397 1999999999999999609 time: 30 ms

    2000000000000000008 137 1999999999999999871 time: 13 ms

    2000000000000000010 139 1999999999999999871 time: 14 ms`

    Die Zielplattform x86 bringt hier also wirklich Vorteile.

    Junge, junge, Du hast gerde für 2000000000000000000 augenblickliche Ergebnisse. Gestern hatten wir noch auf die Primzahlen bis 10000000000 einen kaffetrinkenwarten müssen bevor die Untersuchung anfing. 👍



  • Hab mal die jetige MillierRabin (mit basis 2) funktion mit der divisionprime Funktion gleichgesetzt. Es gibt bei mir aber ein paar mehr unstimmigkeiten, als es eigentlich geben sollte:
    2027, 2039, 2047 (ok das ist normal), und dann gibt es noch ein paar mehr



  • War ein Fehler in meiner implementierung der modpow Funktion.

    Mit der C-Variante unter 64bit funktionert es so wie es soll.

    übrigens kann man for(int i = 0;...) durch for(int i = 1; ...) ersetzen.
    Eigentlich sogar muss.



  • Junge, junge, Du hast gerde für 2000000000000000000 augenblickliche Ergebnisse. Gestern hatten wir noch auf die Primzahlen bis 10000000000 einen kaffetrinkenwarten müssen bevor die Untersuchung anfing. 👍

    Ja, begeistert mich auch sehr. Hätte ich nicht erwartet, dass man in dem Bereich noch so gut arbeiten kann, und wir haben noch Multithreading in der Hinterhand und x64 Assembler-Routinen (das sollte man aber vermeiden, solange man die Vorgehensweise und die Algos variiert/optimiert).

    for(int i = 1; ...)

    Habe ich abgeändert. Vergleich:

    `Start number to be executed: 2000000000000000000

    Last number to be executed: 2000000000000000010

    We generate vector<bool>(primes) up to: 100000000

    In 1 s we found 5761455 prime numbers (2 to 100000000 ).

    Now Goldbach first prime number pair will be detected

    2000000000000000000 601 1999999999999999399 time: 9 ms

    2000000000000000002 131 1999999999999999871 time: 4 ms

    2000000000000000004 593 1999999999999999411 time: 10 ms

    2000000000000000006 397 1999999999999999609 time: 7 ms

    2000000000000000008 137 1999999999999999871 time: 4 ms

    2000000000000000010 139 1999999999999999871 time: 4 ms`

    Ich habe getestet, wie weit wir uns mit dem code an 2^64 heran arbeiten können. 10^19 klappt bisher nicht, aber 8 Trillionen (9 geht auch blitzschnell) geht locker:

    `Start number to be executed: 8000000000000000000

    Last number to be executed: 8000000000000000010

    We generate vector<bool>(primes) up to: 100000000

    In 0 s we found 5761455 prime numbers (2 to 100000000 ).

    Now Goldbach first prime number pair will be detected

    8000000000000000000 97 7999999999999999903 time: 3 ms

    8000000000000000002 41 7999999999999999961 time: 3 ms

    8000000000000000004 43 7999999999999999961 time: 3 ms

    8000000000000000006 103 7999999999999999903 time: 3 ms

    8000000000000000008 47 7999999999999999961 time: 3 ms

    8000000000000000010 107 7999999999999999903 time: 4 ms`

    Ich lasse das Programm nun von 9 nach 10 Trillionen "durchsausen", um festzustellen, wo es aushakt.



  • Übrigens reicht es in vector<bool> primes, wenn man dort nur die ungeraden zahlen aufnimmt, dann kann man doppelt soviel Primes in den RAM packen, wird in sehr hohen Zahlenbereichen wichtig. Im Bereich 10^19 findet man bei dem Goldbachschen Primzahlenpaar die erste Primzahl noch im Bereich < 1000. das wird sich bei 10^1000 sicher ändern.

    Ausschnitt aus dem run von 9 nach 10 Trillionen:
    `

    9000000000000678000 37 9000000000000677963 time: 3 ms

    9000000000000679000 113 9000000000000678887 time: 4 ms

    9000000000000680000 727 9000000000000679273 time: 11 ms

    9000000000000681000 23 9000000000000680977 time: 3 ms

    9000000000000682000 233 9000000000000681767 time: 5 ms

    9000000000000683000 199 9000000000000682801 time: 5 ms`

    Bin sehr gespannt, was den "Bruch" verursacht.

    Er liegt zwischen 9125 und 9250 Billiarden. 😉

    Klingt sehr nach 2^64 / 2 = 9.223.372.036.854.775.808

    Nein, da ist es einfach weiter gelaufen(aber mit Anstieg der ersten Primzahl a des Paares):

    `Now Goldbach first prime number pair will be detected

    9223372036854775000 41 9223372036854774959 time: 2 ms

    9223372036854776000 601 9223372036854775399 time: 8 ms

    9223372036854777000 1217 9223372036854775783 time: 6 ms

    9223372036854778000 2357 9223372036854775643 time: 5 ms

    9223372036854779000 3217 9223372036854775783 time: 3 ms

    9223372036854780000 4217 9223372036854775783 time: 3 ms`



  • Hier erfolgt gerade ein Paradigmenwechsel:
    `Now Goldbach first prime number pair will be detected

    9223372036854775000 41 9223372036854774959 time: 2 ms

    9223372036854776000 601 9223372036854775399 time: 8 ms

    9223372036854777000 1217 9223372036854775783 time: 6 ms

    9223372036854778000 2357 9223372036854775643 time: 5 ms

    9223372036854779000 3217 9223372036854775783 time: 3 ms

    9223372036854780000 4217 9223372036854775783 time: 3 ms

    9223372036854781000 5741 9223372036854775259 time: 9 ms

    9223372036854782000 6217 9223372036854775783 time: 5 ms

    9223372036854783000 7649 9223372036854775351 time: 9 ms

    9223372036854784000 8663 9223372036854775337 time: 8 ms

    9223372036854785000 9601 9223372036854775399 time: 8 ms

    9223372036854786000 10357 9223372036854775643 time: 6 ms

    9223372036854787000 11903 9223372036854775097 time: 11 ms

    9223372036854788000 12601 9223372036854775399 time: 10 ms

    9223372036854789000 13217 9223372036854775783 time: 6 ms

    9223372036854790000 14741 9223372036854775259 time: 10 ms

    9223372036854791000 15217 9223372036854775783 time: 6 ms

    9223372036854792000 16217 9223372036854775783 time: 6 ms

    9223372036854793000 17903 9223372036854775097 time: 13 ms

    9223372036854794000 18217 9223372036854775783 time: 7 ms

    9223372036854795000 19709 9223372036854775291 time: 11 ms

    9223372036854796000 20357 9223372036854775643 time: 11 ms

    9223372036854797000 21493 9223372036854775507 time: 3477 ms

    9223372036854798000 22709 9223372036854775291 time: 11 ms

    9223372036854799000 23357 9223372036854775643 time: 9 ms

    9223372036854800000 24709 9223372036854775291 time: 11 ms

    9223372036854801000 25357 9223372036854775643 time: 9 ms

    9223372036854802000 26357 9223372036854775643 time: 10 ms

    9223372036854803000 28429 9223372036854774571 time: 18 ms

    9223372036854804000 28493 9223372036854775507 time: 11 ms

    9223372036854805000 29663 9223372036854775337 time: 13 ms`

    Was ist genau da los? Ich nenne es mal den "Henkesschen Primzahlpaarenumbruch". 😉 😃

    Wir gehen von 3 nach oben und suchen das erste Primzahlenpaar:

    for (a=3; a<=grenze; a+=2)
    	{
    		if (IsPrime(primes, a, primeLimit) && IsPrime(primes, i-a, primeLimit))
    

    ... und über riesige Zahlenbereiche befindet sich a < 1000, und kurz hinter 2^64 / 2 steigt a massiv an. Entweder eine echte Besonderheit - was ich nicht für realistisch halte, da die Primzahlenpaare die aktuelle 2^64 Grenze nicht kennen - oder eine Schwäche bei der z.Z. angewandten Milli-Miller-Rabin-Methodik. Das halte ich für wahrscheinlicher, und es würde heißen, dass massenhaft Primzahlen durch diese Methodik in diesem Zahlenbereich nicht entdeckt werden!

    Aktuell:

    `

    9223372036854891000 115601 9223372036854775399 time: 28 ms

    9223372036854892000 116663 9223372036854775337 time: 27 ms

    9223372036854893000 117709 9223372036854775291 time: 29 ms

    9223372036854894000 118493 9223372036854775507 time: 28 ms`

    ...

    `9223372036854934000 158357 9223372036854775643 time: 34 ms

    9223372036854935000 159721 9223372036854775279 time: 37 ms

    9223372036854936000 160217 9223372036854775783 time: 33 ms

    9223372036854937000 161741 9223372036854775259 time: 36 ms`

    ...

    `9223372036854971000 195493 9223372036854775507 time: 42 ms

    9223372036854972000 196663 9223372036854775337 time: 42 ms

    9223372036854973000 197741 9223372036854775259 time: 45 ms

    9223372036854974000 198841 9223372036854775159 time: 45 ms`

    ...

    `9223372036854997000 222041 9223372036854774959 time: 51 ms

    9223372036854998000 222493 9223372036854775507 time: 46 ms

    9223372036854999000 223217 9223372036854775783 time: 44 ms

    9223372036855000000 225287 9223372036854774713 time: 53 ms`

    ...

    `9223372036855009000 233357 9223372036854775643 time: 47 ms

    9223372036855010000 234217 9223372036854775783 time: 47 ms

    9223372036855011000 235493 9223372036854775507 time: 48 ms

    9223372036855012000 237287 9223372036854774713 time: 54 ms`

    Ich denke, nun ist klar, warum man bei 10^19 kein Ergebnis sieht, es dauert einfach zu lange.



  • Die Goldbach-Vermutung und unsere Primzahlen-Aktivitäten strahlen aus: http://pkeus.de/Optimieren.html#BessereAlgorithmen

    Nochmals die Frage nach einer BigInt Library. Ich habe bisher https://mattmccutchen.net/bigint/ genutzt, z.B. für Collatz-Analysen im C++-Tutorial. Was haltet ihr davon? Gibt es schnellere Alternativen für unseren Zweck?



  • Unser Milli-Miller-Rabin hat ab einer gewissen Zahlengröße massive Probleme bei der Rückgabe von "false". Er übersieht Primzahlen!

    Ich habe die Methodik umgekehrt, also bei false eine Überprüfung durch den Divisionstest angestoßen und nur die nicht gefundenen Primes ausgegeben.
    Ich weiß nicht genau, wo es anfängt, aber es ist unterhalb 2^64 / 2.
    Dadurch wird der Prime Pair Check immer langsamer. Schlimm ist, dass man sich auf ein false nicht verlassen kann. Ich dachte bisher, der algo gibt nur falsche Primes aus.

    Beispiel:

    `Start number to be executed: 9223372030000000000

    Last number to be executed: 9223372035000000000

    We generate vector<bool>(primes) up to: 100000000

    In 1 s we found 5761455 prime numbers (2 to 100000000 ).

    Now Goldbach first prime number pair will be detected

    ALARM 9223372030000000004 31 9223372029999999973 time: 12142 ms

    ALARM 9223372030000000034 61 9223372029999999973 time: 12120 ms

    ALARM 9223372030000000044 71 9223372029999999973 time: 12126 ms

    ALARM 9223372030000000052 3 9223372030000000049 time: 12126 ms

    ALARM 9223372030000000054 5 9223372030000000049 time: 12134 ms

    ALARM 9223372030000000056 7 9223372030000000049 time: 12133 ms

    ALARM 9223372030000000060 11 9223372030000000049 time: 12131 ms

    ALARM 9223372030000000062 13 9223372030000000049 time: 12132 ms

    ALARM 9223372030000000066 17 9223372030000000049 time: 12133 ms

    ALARM 9223372030000000068 19 9223372030000000049 time: 12133 ms

    ALARM 9223372030000000072 23 9223372030000000049 time: 12138 ms

    ALARM 9223372030000000074 101 9223372029999999973 time: 12137 ms

    ALARM 9223372030000000076 3 9223372030000000073 time: 12142 ms

    ALARM 9223372030000000078 5 9223372030000000073 time: 12132 ms

    ALARM 9223372030000000080 7 9223372030000000073 time: 12137 ms

    ALARM 9223372030000000084 11 9223372030000000073 time: 12129 ms

    `

    Schwierig den Anfang zu finden, also die erste Primzahl, die von Miller-Rabin übersehen wird:

    `Now Goldbach first prime number pair will be detected

    ALARM 9000000000000000004 47 8999999999999999957 time: 17525 ms

    Now Goldbach first prime number pair will be detected

    ALARM 8000000000000000026 173 7999999999999999853 time: 20899 ms

    Now Goldbach first prime number pair will be detected

    ALARM 7000000000000000002 29 6999999999999999973 time: 10705 ms

    ALARM 7000000000000000004 31 6999999999999999973 time: 10601 ms

    Now Goldbach first prime number pair will be detected

    ALARM 6000000000000000002 829 5999999999999999173 time: 17242 ms

    ALARM 6000000000000000012 199 5999999999999999813 time: 12212 ms

    Now Goldbach first prime number pair will be detected

    ALARM 5000000000000000018 181 4999999999999999837 time: 9681 ms

    ALARM 5000000000000000048 211 4999999999999999837 time: 9730 ms

    ALARM 5000000000000000078 241 4999999999999999837 time: 9104 ms

    Now Goldbach first prime number pair will be detected

    ALARM 3000000000000000004 131 2999999999999999873 time: 7063 ms

    ALARM 3000000000000000010 137 2999999999999999873 time: 6987 ms

    ALARM 3000000000000000012 139 2999999999999999873 time: 7008 ms

    ALARM 3000000000000000022 149 2999999999999999873 time: 6968 ms

    ALARM 3000000000000000028 167 2999999999999999861 time: 6947 ms

    ALARM 3000000000000000034 173 2999999999999999861 time: 6956 ms

    ALARM 3000000000000000040 3 3000000000000000037 time: 6960 ms

    ALARM 3000000000000000042 5 3000000000000000037 time: 6966 ms

    ALARM 3000000000000000044 7 3000000000000000037 time: 6936 ms

    Now Goldbach first prime number pair will be detected

    ALARM 1000000000000000000 11 999999999999999989 time: 4155 ms

    ALARM 1000000000000000002 13 999999999999999989 time: 4156 ms

    ALARM 1000000000000000018 29 999999999999999989 time: 4137 ms

    ALARM 1000000000000000030 41 999999999999999989 time: 4126 ms

    ALARM 1000000000000000058 181 999999999999999877 time: 4133 ms

    ALARM 1000000000000000066 317 999999999999999749 time: 5423 ms`

    Also im Trillionenbereich übersieht unser Milli-Miller-Rabin Primzahlen.

    // double check if false
    	if (!IsPrimeMillerRabinOptimized(number, 2))
    	{
    		if (IsPrimeDivisionTest(number) == true)
    		{
    			cout << " ALARM ";
    			alarmflag = true;
    			return true;
    		}
    	}
    	else
    	{
    		alarmflag = false;
    		return true;
    	}
    

    Das fängt nach meinen Analysen deutlich tiefer an, so etwas im bereich 4,3 Mrd. Genaueres demnächst (Tests laufen).

    `Now Goldbach first prime number pair will be detected

    ALARM 4295497744 3 4295497741 time: 2 ms

    ALARM 4295497746 5 4295497741 time: 2 ms

    ALARM 4295497748 7 4295497741 time: 1 ms

    ALARM 4295497752 11 4295497741 time: 1 ms

    ALARM 4295497754 13 4295497741 time: 2 ms

    ALARM 4295497778 37 4295497741 time: 1 ms

    ALARM 4295497788 47 4295497741 time: 2 ms

    ALARM 4295497802 61 4295497741 time: 2 ms

    ALARM 4295497808 67 4295497741 time: 1 ms

    ALARM 4295497844 103 4295497741 time: 2 ms

    `

    Alle diese Zahlen werden übersehen von unserem Miller-Rabin. Daher wird er immer langsamer.



  • Bengo schrieb:

    Hab mal die jetige MillierRabin (mit basis 2) funktion mit der divisionprime Funktion gleichgesetzt. Es gibt bei mir aber ein paar mehr unstimmigkeiten, als es eigentlich geben sollte:
    2027, 2039, 2047 (ok das ist normal), und dann gibt es noch ein paar mehr

    Nee.
    Die Unstimmigkeiten (Lügner-Zahlen, die man in der Liste nachschauen muss) fangen so an: https://oeis.org/A001262 (Die ersten 10000 hier: https://oeis.org/A001262/b001262.txt )
    Also wenn er bei 2047 falsch liegt, ist alles. ok. 3277 kann er sich auch leisten. Aber keine anderen dazwischen.



  • Die Tests deuten darauf hin, dass die "übersehenen" Primzahlen (also Rückgabe von false, obwohl die Primzahl true ist) bei 2^32 beginnen.

    Ausschnitt (der durch den Milli-Miller-Rabin übersehenen Primes):
    ` ALARM 4299154420 3 4299154417 time: 1 ms

    ALARM 4299154422 5 4299154417 time: 1 ms

    ALARM 4299154424 7 4299154417 time: 2 ms`

    Im Bereich darunter habe ich bisher noch nichts gefunden. Tests laufen weiter.

    Ich hatte den Miller-Rabin-Test bool isPrime(number) bisher so verstanden, dass man sich auf ein false verlassen kann, auf ein true jedoch nicht völlig sicher. Dies ist eindeutig aber nicht der Fall. Dies wirkt sich nun nach meinen bisherigen Untersuchungen ab 2^32 (erste Primes werden übersehen) und 2^64 / 2 (starke Verlangsamung der Prüfung der Goldbach-Vermutung durch Übersehen von Primzahlen in der Nähe von number) aus.

    @Volkard: Diese Lügner-Listen sind doch zur Absicherung von true gedacht, also 2047 (= 23 * 89) ist keine Prime usw., habe ich das richtig verstanden?



  • Ich habs schon irgentwo man geschreiben, der Algrotithmus quadriert im schlimmsten Fall seine Eingabezahl und wenn die größer ist, als der zahlbereich des Speichertypes, dann kann das Programm nicht mehr richtig funktioneren.
    Du kannst also maximal für 2^32 garantieren, dass der algrotihmus bei einer primzahl auch true ausgibt.



  • Das Hauptproblem für die Analyse der Goldbach-Vermtung ist, wie oben gezeigt, dass wir im Bereich 10^19 keine rasche Reaktion mehr sehen, weil die Primzahlen in der Nähe (im code: i-a) der untersuchten Goldbach-Geradzahl ein false erhalten, obwohl es sich um eine Primzahl handelt. Da könnte für diesen Bereich der Untersuchung die Divisionsmethode vorteilhaft sein. Kann man diesen Fall rasch erkennen und zur Disviiosons-Methode switchen, oder soll man ab ca. 2^64 / 2 generell für die Primzahlen a bis 100 das entsprechende i-a mit der Divisionsmethode testen, denn da findet sich fast immer etwas?!

    Man könnte auch per MT beide Methoden starten ("prime check race") und jeweils abbrechen, wenn der Sieger durchs Ziel geht.



  • Denke dem MillerRabin Test sollte man sowieso vorher einen Divisionstest mit den Zahlen 2,3,5,7,11 voranstellen, das geht schnell und kann schon einen Großteil der zusammengesetzten Zahlen vorab erkennen. Aber an einer BigInterger Lib wirst du nicht vorbeikommen, wenn du die Grenze 2^32 bzw. 2^64 überschreiten willst. Hab selbst noch keine benutzt, kann dir daher da auch keine gute Empfehlung machen.



  • Hab mal die mzp_class der gmp genutzt:

    #include <iostream>
    #include <cmath>
    #include <gmpxx.h>
    
    using namespace std;
    
    mpz_class mulmod(mpz_class a, mpz_class b, mpz_class mod)
    {
        mpz_class x = 0;
        mpz_class y = a % mod;
    
        while (b > 0)
        {
            if (b % 2 == 1)
            {
                x = (x + y) % mod;
            }
            y = (y * 2) % mod;
            b /= 2;
        }
        return x % mod;
    }
    
    mpz_class powmod(mpz_class x, mpz_class exp, mpz_class mod)
    {
        mpz_class res = 1;
    
        for (; exp; exp >>= 1)
        {
            if (exp % 2 == 1)
                res = mulmod(res, x, mod);
    
            x = mulmod(x, x, mod);
        }
    
        return res;
    }
    
    bool IsPrimeMillerRabinOptimized(mpz_class number, mpz_class base)
    {
        mpz_class d = number - 1;
        int counter = 0;
        while (d % 2 == 0)
        {
            d /= 2;
            ++counter;
        }
    
        mpz_class temp = powmod(base, d, number);
    
        if (temp == 1 || temp == number -1) //Hier
        {
            return true;
        }
    
        for (int i = 1; i < counter; ++i)
        {
            temp = (temp * temp) % number;
    
            if (temp == number - 1)
            {
                return true;
            }
        }
        return false;
    }
    
    bool IsPrimeDivisionTest(mpz_class number)
    {
        if (number<2)    return false;
        if (number == 2)   return true;
        if (number % 2 == 0) return false;
    
        for (mpz_class i=3; i*i<=number; i+=2)
        {
            if (number%i == 0) return false;
        }
        return true;
    }
    
    int main(int argc, char** argv) {
    
        for (int i = 2; i < 10000; ++i) {
            cout << i<<":"<< (int)(IsPrimeMillerRabinOptimized(i, 2)==IsPrimeDivisionTest(i))<< endl;
        }
    
    }
    

    Bei der Zahl 100000000000000000039, gibt der Miller zur Basis 2, aus, dass es eine Primzahl sein könnte. Die einfache Division kommt auf meinem Computer nicht mehr zum Ende. Und die zahl ist tatsächlich prim.

    Auch die zahl 1000000000000000000000000000, macht keine Probleme.

    Die Zahl 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000019, ist prim zur Basis 2. Wird auch von http://primzahlen.zeta24.com/de/online_primzahltest.php bestätigt. Der Test dauert etwa eine halbe Sekunde.



  • Bengo: Ja, Du hast Recht. Wir müssen eine Stufe höher klettern. Probiere bitte https://mattmccutchen.net/bigint/ C++ Big Integer Library als Vergleich dazu aus, welches schneller ist (GMP soll schneller sein. Die Frage ist um wieviel). Schaffe es momentan nicht gmpxx/gmp unter Windows zum Laufen zu bekommen.

    Recht einfach für Dich:

    //#include <gmpxx.h>
    #include "BigIntegerLibrary.hh"
    
    #define mpz_class BigUnsigned
    

    Auf diese Weise findet man alle Lügner (falsche Primes nach Miller-Rabin) bis 10^6:

    int main(int argc, char** argv)
    {
    
         for (int i = 3; i < 1000000; ++i)
         {
             if (((int)IsPrimeMillerRabinOptimized(i, 2) == 1 && (int)IsPrimeDivisionTest(i) == 0))
                 cout << i << " Luegner" << endl; // Rabin-Miller Lügner
             if (((int)IsPrimeMillerRabinOptimized(i, 2) == 0 && (int)IsPrimeDivisionTest(i) == 1))
                 cout << i << " Ueberseher" << endl; // Rabin-Miller Primzahlen-Überseher
         }     
    
         wait();
     }
    

    `15841 Luegner

    29341 Luegner

    42799 Luegner

    49141 Luegner

    52633 Luegner

    65281 Luegner

    74665 Luegner

    80581 Luegner

    85489 Luegner

    88357 Luegner

    90751 Luegner

    104653 Luegner

    130561 Luegner

    196093 Luegner

    220729 Luegner

    233017 Luegner

    252601 Luegner

    253241 Luegner

    256999 Luegner

    271951 Luegner

    280601 Luegner

    314821 Luegner

    357761 Luegner

    390937 Luegner

    458989 Luegner

    476971 Luegner

    486737 Luegner

    489997 Luegner

    514447 Luegner

    580337 Luegner

    635401 Luegner

    647089 Luegner

    741751 Luegner

    800605 Luegner

    818201 Luegner

    838861 Luegner

    873181 Luegner

    877099 Luegner

    916327 Luegner

    976873 Luegner

    983401 Luegner`



  • Erhard Henkes schrieb:

    Schaffe es momentan nicht gmpxx/gmp unter Windows zum Laufen zu bekommen.

    Da gibt es eine ganz einfache Lösung: Linux benutzen! Ich brauchte exakt nur sudo apt-get install libgmp3-dev eingeben (Ubuntu), Enter drücken und im Code includieren, und die gmp Library in der IDE hinzufügen.

    Eigentlich sollte es jetzt keine Fälle mehr geben, in denen zu unrecht false zurückgegeben wird. Also ich hab keine mehr gefunden.



  • Erhard Henkes schrieb:

    Schaffe es momentan nicht gmpxx/gmp unter Windows zum Laufen zu bekommen.

    GMP ist mal wieder so ein Projekt was die Existenz von Windows ignoriert. Unter Windows fährt man mit MPIR (http://mpir.org/index.html#about) besser. Das Interface ist sogar kompatibel zu GMP.



  • Erhard Henkes schrieb:

    Ich weiß nicht genau, wo es anfängt, aber es ist unterhalb 2^64 / 2.

    Ja, ab dort irgendwo hab ich lauter Überseher. Und Überseher darf es gar nicht geben.
    Habs so gefixt.

    #include <iostream>
    #include <cassert>
    #include <cstdint>
    using namespace std;
    
    typedef unsigned int UInt32;
    static_assert(sizeof(UInt32)==4,"wrong size");
    
    typedef unsigned long long UInt64;
    static_assert(sizeof(UInt64)==8,"wrong size");
    
    typedef UInt64 u64;
    
    UInt64 mulmod(UInt64 a, UInt64 b, UInt64 m)
    {
    	UInt64 r;
    	asm
    	("mulq %2;"
    	 "divq %3;"
    	 : "=&d"(r), "+%a"(a)
    	 : "rm"(b), "rm"(m)
    	 : "cc"
    	);
    	return r;
    }
    /*uint64_t powmod(uint64_t x, uint64_t exp, uint64_t mod)
    {
    	uint64_t res = 1;
    	for(; exp; exp >>= 1)
    	{
    		if(exp & 1)
    			res = mulmod(res, x, mod);
    		x = mulmod(x, x, mod);
    	}
    	return res;
    }*/
    UInt64 powmod(UInt64 base,UInt64 exp,UInt64 modul){
        //rechnet 'base hoch exp mod modul'
        UInt64 a1=base,z1=exp,x=1,m=modul;
        while(z1!=0){
            while((z1%2)==0){
                z1/=2;
                a1=mulmod(a1,a1,m);
            }
            --z1;
            x=mulmod(x,a1,m);
        }
        return x;
    }
    bool isSPRP(UInt64 n,UInt64 a)
    {
    	if(a%n==0) return true;
      UInt64 d=n-1;
      UInt64 ad;
      UInt64 s=0;
    
      // break down n-1 into d*(2^s). Linux ffs() can be better
      while (0==(d&1)) {
        ++s; d>>=1;
      }
    
      ad=(powmod(a%n, d, n)); // (a^d) mod n
    
      if (ad==1) return 1; // 1 == a^d mod n
      if (s>0 && ad==(n-1)) return 1; // -1 == a^d mod n (tests (a^d)^(2^0))
      for (UInt64 r=1; r<s; ++r) {
        // ad is currently ad^(2^(r-1)) so we square it to get ad^(2^r));
        ad=mulmod(ad,ad,n);
        if (ad==(n-1)) return 1; //tests (a^d)^(2^(r+1)))
      }
      return 0; // false, composite
    }
    /*bool IsPrimeMillerRabinOptimized(uint64_t number, uint64_t base){
    	return isSPRP(number,base);
    }*/
    
    bool IsPrimeMillerRabinOptimized(uint64_t number, uint64_t base)
    {
    	uint64_t d = number - 1;
    	int counter = 0;
    	while(d % 2 == 0)
    	{
    		d /= 2;
    		++counter;
    	}
    	uint64_t temp = powmod(base, d, number);
    	if(temp == 1 || temp == number - 1)  //Hier
    	{
    		return true;
    	}
    	for(int i = 0; i < counter; ++i)
    	{
    		temp = (temp * temp) % number;
    		if(temp == number - 1)
    		{
    			return true;
    		}
    	}
    	return false;
    }
    
    bool IsPrimeDivisionTest(uint64_t number)
    {
    	if(number<2)    return false;
    	if(number == 2)   return true;
    	if(number % 2 == 0) return false;
    	for(uint64_t i=3; i*i<=number; i+=2)
    	{
    		if(number%i == 0) return false;
    	}
    	return true;
    }
    
    int main()
    {
    	for(uint64_t i = uint64_t(1)<<32; ; ++i)
    	{
    		if(IsPrimeMillerRabinOptimized(i, 2) && !IsPrimeDivisionTest(i))
    			cout << i << " Luegner" << endl; // Rabin-Miller Lügner
    		if(!IsPrimeMillerRabinOptimized(i, 2) && IsPrimeDivisionTest(i))
    			cout << i << " Ueberseher" << endl; // Rabin-Miller Primzahlen-Überseher
    	}
    	wait();
    }
    

Anmelden zum Antworten