Laden...

Klasse für Primzahl- und Integer-Berechnungen

Erstellt von Borg vor 17 Jahren Letzter Beitrag vor 16 Jahren 22.001 Views
B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren
Klasse für Primzahl- und Integer-Berechnungen

Hier folgen einige Klassen zum Umgang mit Primzahlen und deren Nutzung bei einigen Rechnungen mit Integers.

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Als erstes eine statische Klasse zum Ermitteln von Primzahlen mit Hilfe des Siebes des Eratosthenes.
Diese kann speichert die ermittelten Primzahlen in einer Datei und kann auch im Hintergrund laufen.


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace Mathematics
{
    /// <summary>
    /// A static class for generating prime numbers
    /// Calculated prime numbers are stored in a binary file
    /// </summary>
    /// <remarks>
    /// Usage: 
    /// 
    /// static void Main(string[] args)
    /// {
    ///    PrimeNumberGenerator.PrimeDatabaseFileName = @"C:\myprimes.bin";
    ///    PrimeNumberGenerator.StartBackgroundPrimeNumberGenerator();
    ///    ...
    ///    run your program as usual
    ///    ...
    ///    PrimeNumberGenerator.StopBackgroundPrimeNumberGenerator();
    /// }
    /// </remarks>
    public static class PrimeNumberGenerator
    {
        /// <summary>
        /// Returns the greatest prime number found in the file
        /// </summary>
        public static long GreatestKnownPrimeNumber
        {
            get
            {
                if (File.Exists(PrimeDatabaseFileName))
                {
                    long buf;
                    // open it for reading
                    using (BinaryReader reader = new BinaryReader(new FileStream(PrimeDatabaseFileName, FileMode.Open, FileAccess.Read, FileShare.ReadWrite)))
                    {
                        // seek to the last long
                        reader.BaseStream.Seek(-sizeof(long), SeekOrigin.End);
                        // read the last long, it's the last found prime number
                        buf = reader.ReadInt64();
                        // close
                        reader.Close();
                    }
                    return buf;
                }
                else
                {
                    return 1;
                }
            }                
        }
        // how many numbers are tested in each run of Eratosthenes()
        private static long _NumbersToTest = 100000;
        /// <summary>
        /// Minimum value for NumbersToTest
        /// </summary>
        public const long MinNumbersToTest = 1000;
        /// <summary>
        /// Maximum value for NumbersToTest
        /// </summary>
        public const long MaxNumbersToTest = 1000000000;
        /// <summary>
        /// Get/set the count of numbers to test in a run of Eratosthenes()
        /// <para>The value is automatically corrected to be in the bounds given by MinNimbersToTest and MaxNumbersToTest</para>
        /// </summary>
        public static long NumbersToTest
        {
            get
            {
                return _NumbersToTest;
            }
            set
            {
                // TODO: enter code setting bounds to this value
                if (value < MinNumbersToTest)
                {
                    _NumbersToTest = MinNumbersToTest;
                }
                else
                {
                    if (value > MaxNumbersToTest)
                    {
                        _NumbersToTest = MaxNumbersToTest;
                    }
                    else
                    {
                        _NumbersToTest = value;
                    }
                }
            }
        }
        // true if Eratosthenes() is running as background thread
        private static bool RunThreaded = false;
        // the background thread itself
        private static System.Threading.Thread thread;
        private static string _FileName;
        /// <summary>
        /// The name of the file in which the prime numbers are stored
        /// </summary>
        public static string PrimeDatabaseFileName
        {
            get { return _FileName; }
            set
            {
                if (!RunThreaded)
                {
                    _FileName = value;
                }
                else
                {
                    throw new InvalidOperationException("Stop generator using StopBackgoundPNG() first");
                }
            }
        }
        /// <summary>
        /// Initializes the prime number generator with a default filename
        /// <para>FileName = Environment.GetFolderPath(Environment.SpecialFolder.CommonApplicationData) + "\\PrimeNumberDatabase.bin";</para>
        /// </summary>
        static PrimeNumberGenerator()
        {
            _FileName = Environment.GetFolderPath(Environment.SpecialFolder.CommonApplicationData) + "\\PrimeNumberDatabase.bin";
        }
        /// <summary>
        /// Tests NumberToTest numbers for prime and saves found primes to PrimeDatabaseFileName
        /// </summary>
        public static void Eratosthenes()
        {
            // do at least once
            do
            {
                // file access variables
                BinaryWriter writer = null;
                BinaryReader reader = null;
                // we do not need any exception here
                try
                {
                    // every number to test is an element in this array
                    bool[] Zahlen = new bool[NumbersToTest];
                    // initializes the array to false meaning the number is prime
                    Zahlen.Initialize();
                    // initialize last found prime number with 1
                    // although 1 is not a prime number it is necessary here
                    // anyway, algorithm starts by successor
                    long LastFoundPrimeNumber = 1;
                    // is prime number file existing?
                    if (File.Exists(PrimeDatabaseFileName))
                    {
                        // if yes:
                        // open it for reading
                        reader = new BinaryReader(new FileStream(PrimeDatabaseFileName, FileMode.Open, FileAccess.Read, FileShare.ReadWrite));
                        // seek to the last long
                        reader.BaseStream.Seek(-sizeof(long), SeekOrigin.End);
                        // read the last long, it's the last found prime number
                        LastFoundPrimeNumber = reader.ReadInt64();
                        // seek back to beginning
                        reader.BaseStream.Seek(0, SeekOrigin.Begin);
                    }
        #if DEBUG
                    Debug.WriteLine("last found prime number is " + LastFoundPrimeNumber.ToString());
                    Debug.WriteLine("looking for primes lower than " + ((long)(LastFoundPrimeNumber + NumbersToTest)).ToString());
        #endif
                    // first number to be test
                    // this is the number represented by Zahlen[0]
                    long ZIB = LastFoundPrimeNumber + 1;
                    // calc last number which multiples must be tested
                    long MaxSieb = Convert.ToInt64(Math.Ceiling(Math.Sqrt(LastFoundPrimeNumber + NumbersToTest)));
                    // the number of which multiples are beeing eliminated
                    long AktSieb = 0;
                    // if we have to look up prime numbers in Zahlen
                    // start at this index
                    long StartIndex = 0;
                    // repeat until all multiples of all primes lower than MaxSieb are eliminated
                    do
                    {
                        // current index
                        long SuchIndex = StartIndex;
                        // test, where the next prime number can be retrieved
                        // it has to be taken from file if
                        // -ZIB is greater than 2 (meaning that are already prime numbers in the file)
                        // -and current prime (AktSieb) is lower than the greatest prime in file
                        // -and there is actually a file opened
                        if ((ZIB > 2) && (AktSieb < LastFoundPrimeNumber) && (reader != null))
                        {
                            // load from file
                            do
                            {
                                // read a number
                                SuchIndex = reader.ReadInt64();
                            }
                            // until the number is greater than the current prime number
                            // or end of file
                            while ((SuchIndex <= AktSieb) && (reader.BaseStream.Position < reader.BaseStream.Length));
                            // current prime number is the loaded
                            AktSieb = SuchIndex;
        #if DEBUG
                            Debug.WriteLine("prime number loaded from file: " + AktSieb.ToString());
        #endif
                        }
                        else
                        {
                            // find in Zahlen
                            // find first element that is not true (meaning it is not a multiple of any prime number)
                            while (Zahlen[SuchIndex] == true)
                            {
                                SuchIndex++;
                            }
                            // current prime number is the number represented bei Zahlen[SuchIndex]
                            // (remember: ZIB is the number represented by Zahlen[0])
                            AktSieb = SuchIndex + ZIB;
        #if DEBUG
                            Debug.WriteLine("prime number found in current list: " + AktSieb.ToString());
        #endif
                        }
        #if DEBUG
                        Debug.WriteLine("now eliminating multiples of " + AktSieb.ToString() + " in current block");
        #endif
                        // find next multiple of the current prime
                        long Sieb = LastFoundPrimeNumber + AktSieb - (LastFoundPrimeNumber % AktSieb);
                        // repeat if the multiple is in the current block
                        while (Sieb < (LastFoundPrimeNumber + NumbersToTest + 1))
                        {
                            // do not "unprime" the prime itself
                            if (Sieb != AktSieb)
                            {
                                // "unprime" the multiple
                                Zahlen[Sieb - ZIB] = true;
                            }
                            // elevate to next mutliple
                            Sieb += AktSieb;
                        }
        #if DEBUG
                        Debug.WriteLine("elimination finished");
        #endif
                        // elevate look up start point for next loop
                        StartIndex++;
                    }
                    // loop until we have checked all possible primes
                    while (AktSieb <= MaxSieb);

                    // if there is input file
                    if (reader != null)
                    {
                        // close it
                        reader.Close();
                        // and null it for next loop
                        reader = null;
                    }

                    // write data to file (append)
                    writer = new BinaryWriter(new FileStream(PrimeDatabaseFileName, FileMode.Append, FileAccess.Write, FileShare.ReadWrite));
                    // loop all elements of Zahlen
                    for (long i = 0; i < Convert.ToInt64(Zahlen.LongLength); i++)
                    {
                        // false is meaning that the number has not been multiple of anything
                        // so it is prime
                        if (Zahlen[i] == false)
                        {
                            // write it to file
                            // remember: ZIB is the number represented by Zahlen[0]
                            writer.Write(((long)(ZIB + i)));
                        }
                    }
                }
                // if we encounter any exception above
                // we have to make sure, all files are closed before the next loop
                finally
                {
                    // is input file existing
                    if (reader != null)
                    {
                        // close it
                        reader.Close();
                        // null it for next loop
                        reader = null;
                    }
                    // same for output file
                    if (writer != null)
                    {
                        writer.Flush();
                        writer.Close();
                        writer = null;
                    }
                }
            }
            // repeat this if running as background thread
            while (RunThreaded);

        }

        /// <summary>
        /// Signals the generator to stop after next loop
        /// </summary>
        public static void EndBackgroundPNG()
        {
            RunThreaded = false;
        }

        /// <summary>
        /// Immediately stops a running background prime number generator
        /// </summary>
        public static void StopBackgroundPNG()
        {
            // if there is no thread return
            if (thread == null)
            {
                return;
            }
            // if this is false Eratosthenes() will not loop
            RunThreaded = false;
            // raise exception in Eratosthenes()
            thread.Abort();
            // wait until Eratosthenes() closes all files
            thread.Join(5000);
            // remove thread
            thread = null;
        }

        /// <summary>
        /// starts the prime number generator to run in the background
        /// </summary>
        public static void StartBackgroundPNG()
        {
            // if there is already a thread return
            if (thread != null)
            {
                RunThreaded = true;
                return;
            }
            // create thread for Eratosthenes()
            thread = new System.Threading.Thread(new System.Threading.ThreadStart(Eratosthenes));
            // inform Eratosthenes() about running continuosly
            RunThreaded = true;
            // it's only a background thread (will be aborted if main threads end)
            thread.IsBackground = true;
            // run with lowest priority (it shall be real background)
            thread.Priority = System.Threading.ThreadPriority.Lowest;
            // start
            thread.Start();
        }
    }
}
B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Zweitens eine Klasse, um die oben ermittelten Primzahlen auch zu lesen.


namespace Mathematics
{
    /// <summary>
    /// A class for sequentially reading prime numbers from the file specified in PrimeNumberGenerator.PrimeDatabaseFileName
    /// </summary>
    /// <remarks>
    /// Usage: 
    /// 
    /// static void Main(string[] args)
    /// {
    ///    PrimeNumberReader pnr = new PrimeNumberReader()
    ///    pnr.BeginGetNextPrime();
    ///    ...
    ///    pnr.GetNextPrime();
    ///    ...
    ///    pnr.EndGetNextPrime();
    /// }
    /// </remarks>
    public class PrimeNumberReader
    {
        private BinaryReader file = null;
        /// <summary>
        /// Prepare for reading prime numbers from file
        /// </summary>
        public void BeginGetNextPrime()
        {
            if (File.Exists(PrimeNumberGenerator.PrimeDatabaseFileName))
            {
                file = new BinaryReader(new FileStream(PrimeNumberGenerator.PrimeDatabaseFileName, FileMode.Open, FileAccess.Read, FileShare.ReadWrite));
            }
            else
            {
                throw new PrimeNumbersNotCalculatedException();
            }
        }
        /// <summary>
        /// End reading prime numbers from file
        /// </summary>
        public void EndGetNextPrime()
        {
            file.Close();
            file = null;
        }
        /// <summary>
        /// Get the next prime number in file
        /// </summary>
        /// <returns>The next prime number found in file at current position</returns>
        public long GetNextPrime()
        {
            if (file == null)
            {
                throw new InvalidOperationException("Call BeginGetNextPrime() first");
            }
            if (file.BaseStream.Position < file.BaseStream.Length)
            {
                return file.ReadInt64();
            }
            else
            {
                throw new PrimeNumbersNotCalculatedException();
            }
        }
        /// <summary>
        /// Get the next prime number in file greater than a specified number
        /// </summary>
        /// <param name="Number">The prime has to be greater than this number</param>
        /// <returns>The next prime greater than the specified number</returns>
        public long GetNextPrime( long Number )
        {
            if (file == null)
            {
                throw new InvalidOperationException("Call BeginGetNextPrime() first");
            }
            long intern = 0;
            while ((file.BaseStream.Position < file.BaseStream.Length) && (intern < Number))
            {
                intern = file.ReadInt64();
            }
            if (intern > Number)
            {
                return intern;
            }
            else
            {
                throw new PrimeNumbersNotCalculatedException();
            }
        }
    }
    /// <summary>
    /// This exception is thrown if a prime number is needed that is greater
    /// than any by now calculated prime numbers => calculate more
    /// </summary>
    public class PrimeNumbersNotCalculatedException : System.Exception
    {
        public long GreatestPrimeByNow
        {
            get
            {
                return PrimeNumberGenerator.GreatestKnownPrimeNumber;
            }
        }
        public PrimeNumbersNotCalculatedException() : base(){}
    }
}
B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Drittens eine Klasse, die obige Klasse für verschiedene nützliche Dinge mit Integers nutzt. (Zusätzlich auch Umwandlung in Römische Zahlen und zurück.)


namespace Mathematics
{
    /// <summary>
    /// A static class providing useful methods for integer calculations
    /// </summary>
    public static class Integers
    {
        /// <summary>
        /// Calculates the Greatest Common Dividor of two integer
        /// </summary>
        /// <param name="Number1">the first integer</param>
        /// <param name="Number2">the second integer</param>
        /// <returns>the Greatest Common Dividor</returns>
        public static long GetGCD(long Number1, long Number2)
        {
            long remainder = 0;
            do
            {
                remainder = Number1 % Number2;
                Number1 = Number2;
                Number2 = remainder;
            } while (remainder != 0);
            return Number1;
        }

        /// <summary>
        /// Calculates the Smallest Common Multiple
        /// </summary>
        /// <param name="Number1">the first integer</param>
        /// <param name="Number2">the first integer</param>
        /// <returns>the Smallest Common Multiple</returns>
        public static long GetSCM(long Number1, long Number2)
        {
            return (Number1 * Number2) / GetGCD(Number1, Number2);
        }

        /// <summary>
        /// Checks if an integer divides another
        /// </summary>
        /// <param name="Number1">the Divident</param>
        /// <param name="Number2">the Dividor</param>
        /// <returns>true if Number2 ist dividor of Number1, else false</returns>
        public static bool IsDivider(long Number1, long Number2)
        {
            return (Number1 % Number2) == 0;
        }

        /// <summary>
        /// test if an integer is prime
        /// </summary>
        /// <param name="Number">the integer</param>
        /// <returns>true if prime else false</returns>
        public static bool IsPrime(long Number)
        {
            bool value;
            PrimeNumberReader pnreader = new PrimeNumberReader();
            pnreader.BeginGetNextPrime();
            if (pnreader.GetNextPrime(Number - 1) == Number)
            {
                value = true;
            }
            else
            {
                value = false;
            }
            pnreader.EndGetNextPrime();
            return value;
        }

        /// <summary>
        /// Converts an integer to a string containing a roman number
        /// </summary>
        /// <param name="Number">The integer</param>
        /// <returns>The string containing the roman</returns>
        public static string ToRoman(long Number)
        {
            if (Number == 0)
            {
                return string.Empty;
            }
            if (Number >= 1000)
            {
                return "M" + ToRoman(Number - 1000);
            }
            if (Number >= 900)
            {
                return "CM" + ToRoman(Number - 900);
            }
            if (Number >= 500)
            {
                return "D" + ToRoman(Number - 500);
            }
            if (Number >= 400)
            {
                return "CD" + ToRoman(Number - 400);
            }
            if (Number >= 100)
            {
                return "C" + ToRoman(Number - 100);
            }
            if (Number >= 90)
            {
                return "XC" + ToRoman(Number - 90);
            }
            if (Number >= 50)
            {
                return "L" + ToRoman(Number - 50);
            }
            if (Number >= 40)
            {
                return "XL" + ToRoman(Number - 40);
            }
            if (Number >= 10)
            {
                return "X" + ToRoman(Number - 10);
            }
            if (Number >= 9)
            {
                return "IX" + ToRoman(Number - 9);
            }
            if (Number >= 5)
            {
                return "V" + ToRoman(Number - 5);
            }
            if (Number >= 4)
            {
                return "IV" + ToRoman(Number - 4);
            }
            if (Number >= 1)
            {
                return "I" + ToRoman(Number - 1);
            }
            return string.Empty;
        }

        /// <summary>
        /// Converts a string containing a roman number to an integer
        /// </summary>
        /// <param name="Roman">The string containing a roman number</param>
        /// <returns>The integer</returns>
        public static long FromRoman(string Roman)
        {
            if (Roman.Length == 0)
            {
                return 0;
            }
            Roman = Roman.ToUpper();
            long intern = 0;
            for (int i = 0; i < Roman.Length; i++)
            {
                int value = 0;
                switch (Roman[i])
                {
                    case 'M':
                        value = +1000;
                        break;
                    case 'D':
                        value = +500;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("M").IndexOf(Roman[j]) != -1)
                            {
                                value = -500;
                                break;
                            }
                        }
                        break;
                    case 'C':
                        value = +100;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("MD").IndexOf(Roman[j]) != -1)
                            {
                                value = -100;
                                break;
                            }
                        }
                        break;
                    case 'L':
                        value = +50;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("MDC").IndexOf(Roman[j]) != -1)
                            {
                                value = -50;
                                break;
                            }
                        }
                        break;
                    case 'X':
                        value = +10;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("MDCL").IndexOf(Roman[j]) != -1)
                            {
                                value = -10;
                                break;
                            }
                        }
                        break;
                    case 'V':
                        value = +5;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("MDCLX").IndexOf(Roman[j]) != -1)
                            {
                                value = -5;
                                break;
                            }
                        }
                        break;
                    case 'I':
                        value = +1;
                        for (int j = i + 1; j < Roman.Length; j++)
                        {
                            if (("MDCLXV").IndexOf(Roman[j]) != -1)
                            {
                                value = -1;
                                break;
                            }
                        }
                        break;
                    default:
                        throw new ArgumentException("Roman number string contains an illegal character at index " + i.ToString());
                }
                intern += Convert.ToInt64(value);
            }
            return Convert.ToInt64( intern );
        }

        /// <summary>
        /// Calculates the prime number factorization of a given integer
        /// </summary>
        /// <param name="Number">The integer to be factorized</param>
        /// <returns>A SortedDictionary where the keys are the prime factors and the corresponding values their exponent</returns>
        public static SortedDictionary<long,long> GetPrimeFactorization(long Number)
        {
            if (Number == 0)
            {
                throw new ArgumentOutOfRangeException("Number", "parameter must be greater than zero");
            }
            SortedDictionary<long, long> factors = new SortedDictionary<long, long>(); 
            if (Number == 1)
            {
                factors.Add(1, 1);
                return factors;
            }
            long MaxFactor = Convert.ToInt64(Math.Ceiling(Math.Sqrt(Number)));
            long CurrentPrime;
            PrimeNumberReader pnr = new PrimeNumberReader();
            pnr.BeginGetNextPrime();
            do
            {
                CurrentPrime = pnr.GetNextPrime();
                while ((Number % CurrentPrime) == 0)
                {
                    Number /= CurrentPrime;
                    if (factors.ContainsKey(CurrentPrime))
                    {
                        factors[CurrentPrime]++;
                    }
                    else
                    {
                        factors.Add(CurrentPrime, 1);
                    }
                }
                if (Number == 1)
                {
                    break;
                }
            }
            while (MaxFactor > CurrentPrime);
            if (Number != 1)
            {
                if (factors.ContainsKey(Number))
                {
                    factors[Number]++;
                }
                else
                {
                    factors.Add(Number, 1);
                }
            }
            pnr.EndGetNextPrime();
            return factors;
        }

        /// <summary>
        /// Generates a list containing all the dividers of a given integer
        /// </summary>
        /// <param name="Number">The integer</param>
        /// <returns>A List containing the dividers</returns>
        public static List<long> GetDividers(long Number)
        {
            return Integers.GetDividers(GetPrimeFactorization(Number));
        }

        /// <summary>
        /// Generates a list containing all the dividers of an integer specified by its prime factorization
        /// </summary>
        /// <param name="PrimeFactorization">The prime factorization of the integer</param>
        /// <returns>A List containing the dividers</returns>
        public static List<long> GetDividers(SortedDictionary<long,long> PrimeFactorization)
        {
            SortedDictionary<long, long> DividerMask = new SortedDictionary<long, long>();
            long DividerCount = 1;
            foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
            {
                DividerCount *= pfactor.Value + 1;
                long divMask = 1;
                foreach (KeyValuePair<long, long> dmask in DividerMask)
                {
                    divMask *= PrimeFactorization[dmask.Key] + 1;
                }
                DividerMask.Add(pfactor.Key, divMask);
            }
            List<long> Dividers = new List<long>(Convert.ToInt32(DividerCount));
            for (long i = 0; i < DividerCount; i++)
            {
                long Divider = 1;
                foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
                {
                    long pow = (i / DividerMask[pfactor.Key]) % (pfactor.Value + 1);
                    for (long j = 1; j <= pow; j++)
                    {
                        Divider *= pfactor.Key;
                    }
                }
                Dividers.Add(Divider);
            }
            Dividers.Sort();
            return Dividers;
        }
    }
}
I
1.739 Beiträge seit 2005
vor 17 Jahren
Nüscht für Ungut

Deine Klassen sind Zweifellos gut(ungeprüft doch überflogen).
Doch wozu sind sie gut?(ernsthaft).
Ich Empfinde es so:
Toll(Allerdings ist das Sieb des Eratosthenes nicht unbedingt erste Wahl bei hohen Primzahlen).(verdammt löchrich wg. unnötigen Berechnungen(alt halt))
Rein Mathematisch ist das ok, praktisch aber Müll, da veraltet.
Programmtechnisch ist 'ne Tabelle besser, wenn man 'ne notwendige Berechnung durchführt. Die Tabellen geben uns Supercomputer.
Als Mathematisches Example find ich den Code ok(bzw. Lehrreich), aber praktisch unmöglich(wg: Sieb : Rechenzeit und Relevanz).
Wenn du allerdings Darstellen willst was Informatik ist(kein reiner Flow) ist das dir gelungen, als Zielvorgabe für Hobbyprogrammierer/oder Erinnerung für Profs. (Informatik basiert halt auf rudimentären Bestandteilen wie Mathematik)

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Die erste Klasse erstellt sich eine Tabelle.

Ich benötigte mal für ein Projekt die Primfaktorzerlegung einer Zahl.
Um das zu verwirklichen brauchte ich jedoch die Primzahlen.
Und da habe ich mich halt rangesetzt und eine statische Klasse zum Bestimmen von Primzahlen geschrieben. Dann brauchte ich noch eine zum Lesen. und irgendwann habe ich die eigentliche Klasse noch um ein paar andere Spielchen erweitert.
Als ich jetzt neulich mal die Festplatte aufgeräumt habe, bin ich wieder darüber gestolpert und da mir nichts besseres einfiel, habe ich sie hier gepostet, in der Hoffnung, dass jemand vielleicht irgendetwas brauchen könnte.

PrimeNumberGenerator:
Diese statische Klasse berechnet im Hintergrund mit geringer Priorität Primzahlen nach dem Sieb des Eratosthenes und speichert diese in einer Datei.
Man braucht sie also bloß mit dem Programm laufen zu lassen und die bekannten Primzahlen werden immer mehr.
PrimeNumberReader:
Diese Klasse implementiert das Lesen aus der Datei der Primzahlen. Mit jedem Lesevorgang liefert sie die nächste Primzahl (bzw. die nächste Primzahl größer einer bestimmten Zahl).
Integers:
Diese statische Klasse nutzt PrimeNumberReader um die Primfaktorzerlegung und die Teilermenge einer Zahl zu bestimmen. Zusätzlich kann sie noch in römische Zahlen und zurück rechnen.

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Allerdings ist das Sieb des Eratosthenes nicht unbedingt erste Wahl bei hohen Primzahlen).(verdammt löchrich wg. unnötigen Berechnungen(alt halt))
Rein Mathematisch ist das ok, praktisch aber Müll, da veraltet.

Dem möchte ich hier widersprechen. Das Sieb des Eratosthenes ist heute immer noch eines der besten Verfahren, um alle Primzahlen innerhalb eines bestimmten Intervalls zu bestimmen.
Es gibt moderne Verfahren, um zu prüfen, ob eine Zahl prim ist.
Dies stellt jedoch eine völlig andere Thematik dar.

3.825 Beiträge seit 2006
vor 17 Jahren

Borg : Es gibt keine modernen Verfahren um Festzustellen ob eine Zahl prim ist. Wenn Du das findest hast Du alle Public Key Verfahren auf einmal geknackt.

Es gibt auch keine modernen (schnellen) Verfahren um ALLE Primzahlen zu ermitteln.

Für Public Key Verfahren gibt es moderne schnelle Routinen um irgendeine hohe Primzahl zu ermitteln.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Es gibt keine modernen Verfahren um Festzustellen ob eine Zahl prim ist. Wenn Du das findest hast Du alle Public Key Verfahren auf einmal geknackt.

Doch, es gibt solche Verfahren. Modern und schneller sind sie in der Weise, dass sie um Größenordnungen schneller sind als die "Brute-Force"-Variante (durchprobieren aller Zahlen von 2 bis sqrt(n)).
Allerdings sind sie immer noch nicht schnell genug, um große Zahlen, wie sie für Verschlüsselung verwendet werden, in einer auch nur annähernd praxistauglichen Zeit als prim zu ermitteln bzw. zu zerlegen.

Und wie ich schrieb: um alle Primzahlen zu ermitteln, gibt es nur ein sicheres Verfahren: das Sieb des Eratosthenes. Egal wie alt es ist (der Satz des Pythagoras hat auch schon ein paar tausend Jahre auf dem Buckel...)

3.825 Beiträge seit 2006
vor 17 Jahren

Doch, es gibt solche Verfahren.

Borg : Meines Wissens nein.

Laut TU Freiberg : "Es ist bis heute auch keine Formel bekannt, die es gestattet, schnell beliebig große Primzahlen zu berechnen, oder aus einer gegebenen Primzahl eine noch größere Primzahl herzustellen."

Quelle : http://www.mathe.tu-freiberg.de/~hebisch/cafe/primzahlen.html

Man kann zwar einige grosse Primzahlen schnell bestimmen, man kann aber nicht eine beliebig grosse Zahl nehmen und schneller als Brute Force bestimmen ob es eine Primzahl ist. IMHO wären alle Public Key Verfahren geknackt wenn man das könnte.

Der Public Key besteht nämlich (vereinfacht gesagt) aus einem Produkt aus 2 Primzahlen. Wenn man nun schnell bestimmen kann, das dies keine Primzahl ist, so kann man diese Zahl auch schnell in ihre Primfaktoren zerlegen. Damit hätte man den Secret Key.

Wenn man nun 2 als eine der Primfaktoren wählt ist es natürlich einfach.

😉

Wenn man übrigens beide Primzahlen mit den gleichen Stellenzahlen wählt ist es auch möglich das Produkt schnell in Primfaktoren zu zerlegen. Wenn die Stellenzahlen nur ungefähr gleich sind dann muss man alle möglichen Faktoren durchprobieren.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

3.825 Beiträge seit 2006
vor 17 Jahren

Hab nochmal recherchiert : es scheint doch Algorithmen zu geben die "etwas schneller" als das Probieren aller möglichen Faktoren sind :

Der CQS-Algorithmus (Congruential Quadratic Sieve) ist momentan der schnellste Faktorisierungsalgorithmus. Die grösste bis jetzt mit diesem Verfahren zerlegte Zahl ist 369 Bits lang, das entspricht 111 Dezimalstellen. Um eine 512-Bit Zahl zu zerlegen, benötigt man 7.3 · 10 hoch 19 Operationen. Eine MIPS-Maschine würde dazu 2 · 10 hoch 6 Jahre brauchen.

Quelle : http://astro.uibk.ac.at/~arntraud/science/pdf/informatik.pdf

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

484 Beiträge seit 2006
vor 17 Jahren

Kennt ihr das hier schon?
Neues Pattern das auf 6 basiert

http://www.aspose.com/Community/blogs/danny.cooper/archive/2006/08/28/55445.aspx

The second project is an improved version of the Sieve of Eratosthenes. It works in a much different fashion since the prime pattern is known. Based on my test so far it is between 100% and 150% faster than the basic sieve. If anyone would like copies of the projects, please feel free to email me for details.

Jörg

T
512 Beiträge seit 2006
vor 17 Jahren

Naja kann schon verstehen warum sich kein Mathematiker großartig dafür interessiert 😉

Es ist eben kein Muster für Primzahlen, sondern ein Muster für Nichtprimzahlen. Funktioniert eigentlich ziemlich analog zum Sieb des Eratosthenes, nur graphisch etwas schöner. Das passt eben alles zusammen. 2*3 = 6, wodurch sich die Spalten ergeben und zufällig liegen links und rechts von 6 wieder Primzahlen (5 und 7), wodurch die schönen Diagonalen zustande kommen. Aber dann hörts auch schon auf mit Schönheit 😉

e.f.q.

Aus Falschem folgt Beliebiges

484 Beiträge seit 2006
vor 17 Jahren

Aber naja es ist zumindest ein etwas anderer Ansatz.

Jörg

3.825 Beiträge seit 2006
vor 17 Jahren

Da bei Aufteliung auf 6 Spalten 3 Spalten die geraden Zahlen beinhalten und eine Spalte die durch 3 teilbaren Zahlen müssen sich die Primzahlen in den restlichen 2 Spalten befinden.

Mathematisch ist das total uninteressant.

Das RSA-Verfahren (Public Key Verfahren) ist damit nicht geknackt !

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Ich habe schon mehrfach gesagt, dass es sich hier um drei völlig unterschiedliche Dinge handelt:

  1. die Prüfung, ob eine bestimmte Zahl prim ist,
  2. die Ermittlung aller Primzahlen und
  3. die Zerlegung einer Zahl in Primfaktoren.

Zuerst zu 2.: Es gibt nur einen beweisbar allgemeingültig funktionierenden Algorithmus. Das wäre das Sieb des Eratosthenes. Jetzt kann man dieses Verfahren durch einige Kniffe und Optimierung sicherlich deutlich beschleunigen.
Nach bisherigen Kenntnisstand (und nach allen Vermutungen der Mathematiker überhaupt nicht) gibt es keine Bildungsvorschrift für Primzahlen.
Dieses so genannte "6er pattern" ist auch bloß ein Sieb des Eratosthenes. Das "schöne" Muster entsteht nur dadurch, dass bei sechs Spalten die Vielfachen der 5 (6-1) und der 7 (6+1) immer schräg unter dem Vorgänger stehen. Das stellt wohl kaum eine neue Erkenntnis dar und funktioniert genauso mit jeder anderen Anzahl Spalten größer als 2. Das hilft einem aber keineswegs bei der Primzahlberechnung, ist also Quatsch.
Das sieht man auch an der angegebenen Beschleunigung:*ist eine lineare Beschleunigung bei einer (nahezu) exponentiellen Rechenzeit (fast) egal, *vergleicht er die Geschwindigkeit seines neuen Codes mit der Geschwindigkeit seines anderen Codes. Dies bweweist jedoch nicht, dass sein neuer Algorithmus besser ist, sondern nur, dass seine Implementation des Algorithmus besser ist als seine Implementation des Siebes des Eratosthenes, *wenn ich die Primzahlen als Array im Speicher halte, wird das ganze wohl auch noch mal deutlich schneller (bei mehr Speicher) und *wenn ich den Code jetzt als x86-Maschinensprache schreibe (am besten noch mit MMX, SSE1+2+3+4, AMD 3Dnow und wie sie alle heissen) und hochoptimiere, ist wohl auch eine Steigerung um locker den Faktor 100 drin.

Zu 1.: Die naheliegenste und beweisbar funktionierende Variante ist die Brute-Force-Variante. Man prüft einfach für jede Primahl von 2 bis sqrt(n), ob sie n teilt. Falls ja, ist n teilbar, falls nicht ist n prim.
Es gibt auch einige deutlich schnellere Verfahren, wobei diese jedoch oft nur eine Wahrscheinlichkeit dafür liefern, dass eine Zahl prim ist, d.h. eine derartig ermittelte Primzahl muss noch überprüft werden; und zwar durch Division dieser Zahl durch alle bekannten Primzahlen. Erst dann ist sicher, dass sie wirklich prim ist.

Die richtige Aussage

Laut TU Freiberg : "Es ist bis heute auch keine Formel bekannt, die es gestattet, schnell beliebig große Primzahlen zu berechnen, oder aus einer gegebenen Primzahl eine noch größere Primzahl herzustellen." bezieht sich damit auf Punkt 2.
Man kann zwar einige grosse Primzahlen schnell bestimmen, man kann aber nicht eine beliebig grosse Zahl nehmen und schneller als Brute Force bestimmen ob es eine Primzahl ist. IMHO wären alle Public Key Verfahren geknackt wenn man das könnte.

Stimmt so auch nicht. Man kann zwar mit einigen Formeln Kandidaten für Primzahlen ermitteln (z. Bsp. Mersenne-Zahlen), muss diese aber wieder mit anderen Verfahren überprüfen. (erst die schnellen, die eine Wahrscheinlichkeit liefern, dann um sicher zu gehen das langsame Brute-Force)
Es gibt jedoch Verfahren, die sicher bestimmen können, dass eine Zahl keine Primzahl ist, jedoch nicht die Umkehrung. Damit kann man relativ schnell nachweisen, dass eine Zahl keine Primzahl ist, nur der eindeutige Beweis, dass sie es ist gelingt nur mit Brute-Force.

Und zu 3.:
Das Problem bei der Verschlüsselung ist auch nicht zu prüfen, ob der Schlüssel prim ist (das ist er nämlich mit Sicherheit nicht), sondern die beiden Primfaktoren zu bestimmen, aus denen er besteht. Und dies bereitet Probleme, da es sehr viele Möglichkeiten gibt, durch Multiplikation zweier ca. 400 bis 600 Bit langer Primzahlen einen 1024 Bit langen Schlüssel zu erhalten. Und ohne die Primfaktoren kann man den zur Entschlüsselung benötigten Exponenten nicht berechnen.

Dies wird auch hier bestätigt:

Der CQS-Algorithmus (Congruential Quadratic Sieve) ist momentan der schnellste Faktorisierungsalgorithmus. Die grösste bis jetzt mit diesem Verfahren zerlegte Zahl ist 369 Bits lang, das entspricht 111 Dezimalstellen. Um eine 512-Bit Zahl zu zerlegen, benötigt man 7.3 · 10 hoch 19 Operationen. Eine MIPS-Maschine würde dazu 2 · 10 hoch 6 Jahre brauchen.

Und typische symmetrische Verfahren nutzen mindesten 1024 Bit für den öffentlichen Schlüssel...

EDIT: nach dem Hinweis mit dem doch vorhandenen Code habe ich den unten zitierten Kommentar umgeschrieben.

484 Beiträge seit 2006
vor 17 Jahren

Original von Borg

Zuerst zu 2.:...
vergleicht er die Geschwindigkeit seines neuen (nicht veröffentlichten) Codes mit der Geschwindigkeit seines anderen (ebenfalls nicht veröffenlichten) Codes (wenn ich in meinen Code zum Sieb des Eratosthenes noch ein paar Thread.Sleep(100) reinschreibe, kann ich Code erzeugen, der im Vergleich dazu um den Faktor 1000 schneller ist),

Er hat ihn veröffentlicht unter http://www.aspose.com/preview/danny/prime/newsieve.zip

Jörg

3.825 Beiträge seit 2006
vor 17 Jahren

Borg : Genau das was ich gesagt hatte, ausser

Stimmt auch nicht. Man kann zwar mit einigen Formeln Kandidaten für Primzahlen ermitteln (z. Bsp. Mersenne-Zahlen), muss diese aber wieder mit anderen Verfahren überprüfen. (erst die schnellen, die eine Wahrscheinlichkeit liefern, dann um sicher zu gehen das langsame Brute-Force)

Es gibt verschiedene Formeln um hohe Primzahlen zu ermitteln OHNE die gefundene Zahl durch Brute Force zu verifizieren, z.B. Mersenne-Zahlen).
Sonst wäre ja die Public Key Verschlüsselung auch ewig langsam.

Und

Das Problem bei der Verschlüsselung ist auch nicht zu prüfen, ob der Schlüssel prim ist

hatte ich nicht behauptet. Der Public Key ist immer ein Produkt aus 2 Primzahlen. Allerdings ist das Problem 1 (Prüfen ob beliebige Zahl Prim) mathematisch das gleiche Gleiche wie Problem 3 (Primfaktorenzerlegung). Wenn man die Primfaktoren gefunden hat weiss man ob die Zahl eine Primzahl ist oder nicht.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
512 Beiträge seit 2006
vor 17 Jahren

Original von BerndFfm
Borg : Genau das was ich gesagt hatte, ausser

Stimmt auch nicht. Man kann zwar mit einigen Formeln Kandidaten für Primzahlen ermitteln (z. Bsp. Mersenne-Zahlen), muss diese aber wieder mit anderen Verfahren überprüfen. (erst die schnellen, die eine Wahrscheinlichkeit liefern, dann um sicher zu gehen das langsame Brute-Force)

Es gibt verschiedene Formeln um hohe Primzahlen zu ermitteln OHNE die gefundene Zahl durch Brute Force zu verifizieren, z.B. Mersenne-Zahlen).
Sonst wäre ja die Public Key Verschlüsselung auch ewig langsam.

Es gibt keine Formel mit der man garantiert eine Primzahl ermitteln kann. Das sieht man doch gerade an den Mersenne-Primzahlen. Für die 25 ersten Mersenne-Zahlen (also nach der Formel 2^n-1 mit n ist Primzahl) sind gerademal 10 auch Primzahlen. Der Trick ist, dass man mit ner höheren Wahrscheinlichkeit eine Primzahl findet, als durch pures Raten. Bzw. ist der Vorteil bei den Mersenne-Zahlen, dass man sie leichter auf prim testen kann.
Und das ist auch ein Erkenntniss der Primzahlforschung. Es gibt kein festes Muster, aber es gibt eine Verteilung der Primzahlen. Das heißt es gibt Formeln die öfters eine Primzahl finden als andere. Oder anders: man kann Zahlen eine Wahrscheinlichkeit zuordnen, dass sie eine Primzahl sind und diese Wahrscheinlichkeit ist nicht gleichverteilt. Bzw. glaubt man, dass sie nicht ganz zufällig verteilt sind. Ob es einen Beweis dafür gibt, oder ob man das inzwischen verworfen hat möchte ich jetz nicht beschwören... kann gut sein dass ich mich irre...

Aber es gibt keine Formel die jedesmal eine Primzahl findet. Man muss also sehr wohl die Zahl mit Brute Force (oder bei Mersenne-Zahlen mit einem eigenen Test) prüfen, egal welche Formel man hernimmt.

e.f.q.

Aus Falschem folgt Beliebiges

I
1.739 Beiträge seit 2005
vor 17 Jahren

Tja, recht du hast.
Man kann in gewissen Bereichen Primzahlen Eingrenzen und Berechnen, oder Ausgrenzen(Berechnumg halt).
Zum Errechnen der Unbekannten der Solchen(bisher unbekannten Primzahl) hilft ganz bestimmt nicht eine neue Sprache....
(derzeit wird das Limit mit Vergewaltigung von Strings aufgehoben, das geht mit fast jeder Sprache)

3.825 Beiträge seit 2006
vor 17 Jahren

Aber es gibt keine Formel die jedesmal eine Primzahl findet. Man muss also sehr wohl die Zahl mit Brute Force (oder bei Mersenne-Zahlen mit einem eigenen Test) prüfen, egal welche Formel man hernimmt.

Dann hab ich das vom Studium (ja, ist lange her) falsch in Erinnerung. Wir hatten damals Verfahren untersucht um hohe Primzahlen zu finden. Es gab da mehrere Formeln. An Brute Force danach kann ich mich nicht erinnern.

Ich finde es allerdings bedenklich dass 99% aller Verschlüsselungen auf der Tatsache beruhen, dass man eine Große Zahl nicht in kurzer zeit in Primfaktoren zerlegen kann. Es kann durchaus sein dass man ein solches Verfahren noch entdeckt.
Ausserdem ist die Primfaktorenzerlegung gut auf mehrere Rechner aufteilbar und z.B. gut von Quantenrechnern zu erledigen (ca. 1000 mal schneller und 100.000 mal kleiner als bisherige CPU's) .

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
512 Beiträge seit 2006
vor 17 Jahren

Es gibt tatsächlich einen Polynomialzeit Algorithmus zur Faktorisierung auf Quantencomputern. Mehr als das weiß ich aber auch nicht, hab die Vorlesung nicht weiter besucht 😁

e.f.q.

Aus Falschem folgt Beliebiges

B
Borg Themenstarter:in
1.529 Beiträge seit 2006
vor 17 Jahren

Es basieren ja nur die asynchronen Verschlüsselungen auf diesem Verfahren (die mit dem öffentlichen und geheimen Schlüssel).
Ein schneller Primzahltest würde daher nur diese kompromitieren.
Genau aus diesem Grund muss man für asynchrone Schlüssel auch solch lange öffentliche Schlüssel verwenden. So sind heutzutage 1024Bit öffentlicher Schlüssel absolutes Minimum. Und wie oben steht, würde man mit derzeitigem Stand für 512Bit Schlüssel knapp 10^20 Operationen benötigen. Selbst eine idealer Algorihtmus auf einem idealen Prozessor (1 Operation pro Takt) mit 4GHz (=4e9) würde also 2,5e11 Sekunden benötigen. Dies sind rund 7900 Jahre. Man bräuchte also einen Super²-Computer mit mindestens 8000 CPUs (Probleme mit Abwärme etc. vernachlässigt) um die Rechenzeit unter 1 Jahr zu drücken. Selbst wenn dieser Prozessor nur 50Watt unter Vollast verbrät, wären das 50Watt * 2,5e11 Sekunden = 3.472.222 kWh. Selbst wenn der Strom nur 10 Cent/kWh kostet, wären das knapp 350.000 Euro. Es wird wohl kaum Geheimnisse geben, die mehr wert sind als das und trotzdem nur mit 512Bit verschlüsselt werden...

A
266 Beiträge seit 2007
vor 16 Jahren

Oh mein Gott!
Habt ihr alle Mathematik studiert oder habt ihr euch das alles durch nur lesen beigebracht?
Ich hatte echt Probleme zu folgen... Aber ihr habt schon Recht... 😁 👍 RESPEKT!

Von all den Sachen, die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen... MfG...

309 Beiträge seit 2007
vor 16 Jahren

Original von Borg

Es gibt keine modernen Verfahren um Festzustellen ob eine Zahl prim ist. Wenn Du das findest hast Du alle Public Key Verfahren auf einmal geknackt.
Doch, es gibt solche Verfahren. Modern und schneller sind sie in der Weise, dass sie um Größenordnungen schneller sind als die "Brute-Force"-Variante (durchprobieren aller Zahlen von 2 bis sqrt(n)).
Allerdings sind sie immer noch nicht schnell genug, um große Zahlen, wie sie für Verschlüsselung verwendet werden, in einer auch nur annähernd praxistauglichen Zeit als prim zu ermitteln bzw. zu zerlegen.

Und wie ich schrieb: um alle Primzahlen zu ermitteln, gibt es nur ein sicheres Verfahren: das Sieb des Eratosthenes. Egal wie alt es ist (der Satz des Pythagoras hat auch schon ein paar tausend Jahre auf dem Buckel...)

Eine Beschleunigung des obigen Verfahrens ist es,
wenn ich nur durch bereits bekannte Priemzahlen bis sqrt(n) probiere,
da sich ja jede Priemzahl in Priemfaktoren zerlegen läßt ...

mfg Hajoseb

(Ja. Wir sind bei "klassischen" Vefahren ...)

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France

S
151 Beiträge seit 2007
vor 16 Jahren

Wenn du Primzahlen in Primfaktoren zerlegen könntest, wären es keine Primzahlen mehr 🙂

Nur als kleine Anmerkung. Ich glaube du meinst die Schlüssel von verschiedenen PK-Verfahren (die bestehen meist aus zwei Primzahlen und teilweise noch anderen Zufallszahlen je nach Verfahren).

309 Beiträge seit 2007
vor 16 Jahren

Ich meinte eigentlich eher, ich muss nur versuchen durch bereits bekannte Primzahlen zu teilen ...

Will ich also wissen, ob 4357 eine Primzahl ist teste ich mit

4357 / 2 = ...
4357 / 3 = ...
4357 / 5 = ...
4357 / 7 = ...
usw ...

aber nicht
4357 / 4 = ...
4357 / 6 = ...
usw ...
denn diese Zahlen sind ja wieder aus Primzahlen zusammengesetzt.
Ist die Zahl z.B. durch 6 teilbar, ist sie in jedem Fall auch durch 2 und durch 3 teilbar. ... und das haben wir ja schon geprüft ...

Da jede Zahl aus Primfaktoren besteht ( eine Primzahl halt eben nur aus einem, sie selber 😄) brauche ich eben bis zur Wurzel der Zahl nur die (bereits bekannten) Primzahlen zu testen.

Ich muss eben nur bereits genug Primzahlen gesammelt haben.

Mfg Hajoseb

**"Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.” **
Anatole France