Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Klasse für Primzahl- und Integer-Berechnungen
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

Klasse für Primzahl- und Integer-Berechnungen

beantworten | zitieren | melden

Hier folgen einige Klassen zum Umgang mit Primzahlen und deren Nutzung bei einigen Rechnungen mit Integers.
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

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();
        }
    }
}
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

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(){}
    }
}
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

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;
        }
    }
}
private Nachricht | Beiträge des Benutzers
ikaros
myCSharp.de - Member



Dabei seit:
Beiträge: 1787

Nüscht für Ungut

beantworten | zitieren | melden

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)
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

Zitat
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.
private Nachricht | Beiträge des Benutzers
BerndFfm
myCSharp.de - Team

Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


Dabei seit:
Beiträge: 3778
Herkunft: Frankfurt a.M.

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

Zitat
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...)
private Nachricht | Beiträge des Benutzers
BerndFfm
myCSharp.de - Team

Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


Dabei seit:
Beiträge: 3778
Herkunft: Frankfurt a.M.

beantworten | zitieren | melden

Zitat
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
private Nachricht | Beiträge des Benutzers
BerndFfm
myCSharp.de - Team

Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


Dabei seit:
Beiträge: 3778
Herkunft: Frankfurt a.M.

beantworten | zitieren | melden

Hab nochmal recherchiert : es scheint doch Algorithmen zu geben die "etwas schneller" als das Probieren aller möglichen Faktoren sind :
Zitat
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
private Nachricht | Beiträge des Benutzers
joerg.uth
myCSharp.de - Member

Avatar #avatar-2080.jpg


Dabei seit:
Beiträge: 485
Herkunft: Lonnig

beantworten | zitieren | melden

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
Zitat
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
private Nachricht | Beiträge des Benutzers
Traumzauberbaum
myCSharp.de - Member



Dabei seit:
Beiträge: 513

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
joerg.uth
myCSharp.de - Member

Avatar #avatar-2080.jpg


Dabei seit:
Beiträge: 485
Herkunft: Lonnig

beantworten | zitieren | melden

Aber naja es ist zumindest ein etwas anderer Ansatz.

Jörg
private Nachricht | Beiträge des Benutzers
BerndFfm
myCSharp.de - Team

Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


Dabei seit:
Beiträge: 3778
Herkunft: Frankfurt a.M.

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

Themenstarter:

beantworten | zitieren | melden

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:
  1. ist eine lineare Beschleunigung bei einer (nahezu) exponentiellen Rechenzeit (fast) egal,
  2. 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,
  3. wenn ich die Primzahlen als Array im Speicher halte, wird das ganze wohl auch noch mal deutlich schneller (bei mehr Speicher) und
  4. 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.

  5. 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
    Zitat
    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.
    Zitat
    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:
    Zitat
    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.
private Nachricht | Beiträge des Benutzers
joerg.uth
myCSharp.de - Member

Avatar #avatar-2080.jpg


Dabei seit:
Beiträge: 485
Herkunft: Lonnig

beantworten | zitieren | melden

Zitat
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), [/quote]

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

    Jörg
  • Attachments
    private Nachricht | Beiträge des Benutzers
    BerndFfm
    myCSharp.de - Team

    Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


    Dabei seit:
    Beiträge: 3778
    Herkunft: Frankfurt a.M.

    beantworten | zitieren | melden

    Borg : Genau das was ich gesagt hatte, ausser
    Zitat
    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
    Zitat
    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
    private Nachricht | Beiträge des Benutzers
    Traumzauberbaum
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 513

    beantworten | zitieren | melden

    Zitat
    Original von BerndFfm
    Borg : Genau das was ich gesagt hatte, ausser
    Zitat
    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
    private Nachricht | Beiträge des Benutzers
    ikaros
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 1787

    beantworten | zitieren | melden

    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)
    private Nachricht | Beiträge des Benutzers
    BerndFfm
    myCSharp.de - Team

    Avatar #nZo9Gyth4VPDSxGqM4sT.jpg


    Dabei seit:
    Beiträge: 3778
    Herkunft: Frankfurt a.M.

    beantworten | zitieren | melden

    Zitat
    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
    private Nachricht | Beiträge des Benutzers
    Traumzauberbaum
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 513

    beantworten | zitieren | melden

    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
    private Nachricht | Beiträge des Benutzers
    Borg
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 1548
    Herkunft: Berlin, Germany

    Themenstarter:

    beantworten | zitieren | melden

    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...
    private Nachricht | Beiträge des Benutzers
    Atomroflman
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 274
    Herkunft: Hamburg

    beantworten | zitieren | melden

    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...
    private Nachricht | Beiträge des Benutzers
    Hajoseb
    myCSharp.de - Member

    Avatar #avatar-2670.jpg


    Dabei seit:
    Beiträge: 315

    beantworten | zitieren | melden

    Zitat
    Original von Borg
    Zitat
    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 ...)
    Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Hajoseb am .
    "Zufall ist das Pseudonym Gottes, wenn er nicht selbst unterschreiben will.”
    Anatole France
    private Nachricht | Beiträge des Benutzers
    smilingbandit
    myCSharp.de - Member



    Dabei seit:
    Beiträge: 151
    Herkunft: Nürnberg

    beantworten | zitieren | melden

    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).
    private Nachricht | Beiträge des Benutzers
    Hajoseb
    myCSharp.de - Member

    Avatar #avatar-2670.jpg


    Dabei seit:
    Beiträge: 315

    beantworten | zitieren | melden

    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 :D) 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
    private Nachricht | Beiträge des Benutzers
    Entwickelt mit ♥ und ASP.NET Core. Version 0.1.332+27ed306318 vom Uhr. Betrieben auf Azure App Service (debian.10-x64 mit .NET 5.0.9)
    Copyright 2003-2021 myCSharp.de - Alle Rechte vorbehalten. Benutzerinhalte unterliegen cc-by-sa 4.0