Hallo nafets
Danke für deine Analyse. Hast dich da recht ins Zeug gelegt. Theoretisch wäre es möglich. Nur Praktisch kann es nie passieren das immer die gleiche Zufallszahl vom Generator erzeugt wird. Natürlich versteht sich von selber, dass min und max daher ein gewisses Delta haben müssen.
Die Codes habe ich kurz umgeschrieben und das Mathe-Zeug rausgenommen. Ich werde zu einem späteren Zeitpunkt schauen was mathematisch optmiert werden kann. Auch die Eigenschaft mit der Suchrichtung werde ich später machen. Dafür habe ich angefangen einzelne Funktionen auf Generic umzubauen. Die Codes laufen so recht zügig. Siehe BIlder.
Um Hinweise und Verbessung bin ich dankbar.
Edit: Korrektur. Teils Sachen beibehalten, da Schlussendlich immer noch ein Fermattest
Freundliche Grüsse
exc-jdbi
Hier der C#-Quellcode
Spoiler anzeigen
Und hier der VB.NET-Quellcode
Spoiler anzeigen
Danke für deine Analyse. Hast dich da recht ins Zeug gelegt. Theoretisch wäre es möglich. Nur Praktisch kann es nie passieren das immer die gleiche Zufallszahl vom Generator erzeugt wird. Natürlich versteht sich von selber, dass min und max daher ein gewisses Delta haben müssen.
Die Codes habe ich kurz umgeschrieben und das Mathe-Zeug rausgenommen. Ich werde zu einem späteren Zeitpunkt schauen was mathematisch optmiert werden kann. Auch die Eigenschaft mit der Suchrichtung werde ich später machen. Dafür habe ich angefangen einzelne Funktionen auf Generic umzubauen. Die Codes laufen so recht zügig. Siehe BIlder.
Um Hinweise und Verbessung bin ich dankbar.
Edit: Korrektur. Teils Sachen beibehalten, da Schlussendlich immer noch ein Fermattest
Freundliche Grüsse
exc-jdbi
Hier der C#-Quellcode
C#-Quellcode
- class Program
- {
- private static Random rnd;
- private double _maxf = 0.0;
- private double _minf = double.MaxValue;
- private ulong ggT(ulong a, ulong b)
- {
- ulong re = 0;
- while (b != 0)
- {
- re = a % b;
- a = b; b = re;
- }
- return a;
- }
- private bool isPrimePepin(ulong p)
- {
- //Pépin-Test folgert aus Lucas-Test (sehr sicher)
- ulong k = 0;ulong l = 0;ulong o = 0;
- k = 2;//pow(2,m)%m = immer 2
- l = (ulong)(BigInteger.ModPow(2, k, p)) + 1uL;
- k = (l - 1uL) >> 1;
- o = (ulong)(BigInteger.ModPow(3, k, l));
- if (o == l - 1)
- {
- return true;
- }
- return false;
- }
- private bool isPrimeFermat(ulong n, ulong t)
- {
- ulong[] a = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
- for (int i = 0; i < 9; i++)
- {
- if (n == a[i]) return true;
- if (n % a[i] == 0) return false;
- }
- ulong j = 1; ulong res = 0;
- for (ulong i = 0; i < t; i++)
- {
- j++;
- while (j < n)
- {
- if (ggT(j, n) == 1)
- {
- break;
- }
- j++;
- }
- res = (ulong)(BigInteger.ModPow(j, n - 1uL, n));
- if (res == 1)
- {
- return isPrimePepin(n);
- }
- }
- return false;
- }
- private double nextRnd()
- {
- double tmp = (double)((double)rnd.Next(int.MaxValue) * (double)(1.0 / (double)(int.MaxValue)));
- if (tmp < _minf) _minf = tmp;
- if (tmp > _maxf) _maxf = tmp;
- if (_maxf - _minf == 0.0)
- {
- nextRnd();
- }
- return 1.0 - ((_maxf - tmp) / (_maxf - _minf));
- }
- private ulong uniformDistribution(ulong min, ulong max)
- {
- ulong res = 0; double n = 0; double r = 0; double t = 0;
- n = (double)(max - min); r = nextRnd(); t = r * n;
- ulong b = max - min;
- if (t >= b) {
- res = max;
- } else {
- res = min + (ulong)(t > b ? b : t);
- }
- return res;
- }
- private ulong genRndUlong(ulong min, ulong max)
- {
- return (ulong)(uniformDistribution(min, max));
- }
- private ulong findPrimeFermat(ulong min, ulong max, ulong t)
- {
- ulong res = 0;
- ulong num = 0; int cnt = 0; int ii = 100000;
- while (true)
- {
- if (cnt++ >= ii) break;
- num = genRndUlong(min, max);
- if ((num == 0) || (num == 1))
- continue;
- if (num % 2 == 0)
- num |= 1;
- if (isPrimeFermat(num, t))
- {
- return num;
- }
- }
- if (cnt >= 100000)
- {
- msgError(0);
- }
- return res;
- }
- private void msgError(int eN)
- {
- switch (eN)
- {
- case 0: throw new Exception("Could not generate a random prime. Check intervall {min,max}");
- }
- }
- static void Main(string[] args)
- {
- rnd = new Random();
- int maxCnt = 1000;
- //ulong min = 0; ulong max = 255; ulong trial = 3;
- ulong min = 1000000000000000000; ulong max = ulong.MaxValue; ulong trial = 3;
- ulong[] prime = new ulong[maxCnt];
- Stopwatch sw = new Stopwatch();
- sw.Start();
- Program p = new Program();
- for (int i = 0; i < maxCnt; i++)
- {
- prime[i] = p.findPrimeFermat(min, max, trial);
- }
- int EndZeit = sw.Elapsed.Milliseconds;
- for (int i = 0; i < maxCnt; i++)
- {
- if (prime[i] > 0)
- {
- Console.WriteLine(prime[i].ToString());
- }
- }
- Console.WriteLine();
- Console.WriteLine("Primes:\t\t" + maxCnt + " pcs.");
- Console.WriteLine("Times:\t\t" + EndZeit + " ms");
- Console.ReadKey();
- }
- }
Und hier der VB.NET-Quellcode
VB.NET-Quellcode
- Option Strict On
- Option Explicit On
- Imports System.Numerics
- Imports System.Runtime.CompilerServices
- Module findPrimeFermat
- Private rnd As Random
- Private _minf As Double = Double.MaxValue, _maxf As Double = 0.0
- Private Function ggT(ByVal a As ULong, ByVal b As ULong) As ULong
- Dim re As ULong = 0
- While Not b = 0
- re = a Mod b : a = b : b = re
- End While
- Return a
- End Function
- Private Function isPrimePepin(ByVal p As ULong) As Boolean
- Dim k As ULong, l As ULong, o As ULong
- isPrimePepin = False
- 'Pépin-Test folgert aus Lucas-Test (sehr sicher)
- k = 2 'pow(2,m)%m = immer 2
- l = CULng(BigInteger.ModPow(2, k, p)) + 1UL
- k = (l - 1UL) >> 1 ' = (l-1)/2
- o = CULng(BigInteger.ModPow(3, k, l))
- If o = l - 1 Then
- Return True
- End If
- End Function
- Private Function isPrimeFermat(ByVal n As ULong, ByVal t As ULong) As Boolean
- Dim a As ULong() = {2, 3, 5, 7, 11, 13, 17, 19, 23}
- For i As Integer = 0 To 8
- If n = a(i) Then Return True
- If n Mod a(i) = 0 Then Return False
- Next
- Dim j As ULong = 1, res As ULong = 0
- For i As ULong = 0 To t - 1UL
- j += 1UL
- While j < n
- If ggT(j, n) = 1 Then
- Exit While
- End If
- j += 1UL
- End While
- res = CULng(BigInteger.ModPow(j, n - 1UL, n))
- If res = 1 Then
- Return isPrimePepin(n)
- End If
- Next
- Return False
- End Function
- Private Function nextRnd() As Double
- Dim tmp As Double = CDbl(CDbl(rnd.Next()) * CDbl(1.0 / CDbl(Integer.MaxValue)))
- If tmp < _minf Then _minf = tmp
- If tmp > _maxf Then _maxf = tmp
- If _maxf - _minf = 0.0 Then
- nextRnd()
- End If
- Return 1.0 - ((_maxf - tmp) / (_maxf - _minf))
- End Function
- Private Function uniformDistribution(ByVal min As ULong, ByVal max As ULong) As ULong
- Dim res As ULong = 0, n As Double, r As Double, t As Double
- n = CDbl(max - min) : r = nextRnd() : t = r * n
- Dim b As ULong = max - min
- If t >= b Then
- res = max
- Else : res = min + CULng(If(t > b, b, t))
- End If
- Return res
- End Function
- Private Function genRndUlong(ByVal min As ULong, ByVal max As ULong) As ULong
- Return CULng(uniformDistribution(min, max))
- End Function
- Private Function findPrimeFermat(ByVal min As ULong, ByVal max As ULong, ByVal t As ULong) As ULong
- findPrimeFermat = 0UL
- Dim num As ULong = 0, cnt As Integer = 0, ii As Integer = 100000
- While True
- cnt += 1 : If cnt = ii Then Exit While
- num = genRndUlong(min, max)
- If (num = 0) OrElse (num = 1) Then Continue While
- If num Mod 2 = 0 Then num -= 1UL
- If isPrimeFermat(num, t) Then
- Return num
- End If
- End While
- If cnt = 100000 Then
- msgError(0)
- End If
- End Function
- Private Sub msgError(ByVal eN As Integer)
- Select Case eN
- Case 0 : Throw New Exception("Could not generate a random prime. Check intervall {min,max}")
- End Select
- End Sub
- Public Sub Main()
- rnd = New Random()
- Dim maxCnt As Integer = 1000
- 'Dim min As ULong = 0 : Dim max As ULong = 256 : Dim trial As ULong = 3
- Dim min As ULong = CULng(10 ^ 18) : Dim max As ULong = ULong.MaxValue : Dim trial As ULong = 3
- Dim prime As ULong() = New ULong(maxCnt - 1) {}
- Dim sw As New Stopwatch()
- sw.Start()
- For i As Integer = 0 To maxCnt - 1
- prime(i) = findPrimeFermat(min, max, trial)
- Next
- Dim EndZeit As Integer = sw.Elapsed.Milliseconds
- For i As Integer = 0 To maxCnt - 1
- If prime(i) > 0 Then
- Console.WriteLine(prime(i).ToString())
- End If
- Next
- Console.WriteLine()
- Console.WriteLine("Primes:" & vbTab & vbTab & maxCnt & " pcs.")
- Console.WriteLine("Times:" & vbTab & vbTab & EndZeit & " ms")
- Console.ReadKey()
- End Sub
- End Module
Dieser Beitrag wurde bereits 9 mal editiert, zuletzt von „exc-jdbi“ ()