Option Strict On
Option Explicit On
Imports System.Numerics

'Aufgebaut auf der Aussage, das ...
'**********************************
'p mod 4 = 1 oder 3, >> d.h. x * 4 (+-) 1 = vielfach p
'p mod 6 = 1 oder 5, >> d.h. x * 6 (+-) 1 = vielfach p


Public Module PrimeGen
   Public Sub Main()
      Dim sw As New Stopwatch
      Dim pfpg As New PowerFastPrimeGenerator

      Dim cnt = 1_000I
      Dim res1 = New Int64(cnt - 1) {}

      sw.Restart()
      For i As Int32 = 0 To cnt - 1
         res1(i) = pfpg.GetPrime()
      Next
      Console.WriteLine("Count = {0} in {1}ms", cnt, sw.ElapsedMilliseconds)


      'Primes in einem bestimmten Bereich
      Dim res2 = New Int64(cnt - 1) {}
      Dim _min, _max As Int64
      _min = 300_000I
      _max = 500_000I
      pfpg.Swap(_min, _max)

      sw.Restart()
      For i As Int32 = 0 To cnt - 1
         res2(i) = pfpg.GetPrime(_min, _max)
      Next
      Console.WriteLine("Count = {0} in {1}ms", cnt, sw.ElapsedMilliseconds)

      Console.ReadLine()
   End Sub
End Module


'Wer's sicherer will, nimmt den 
'RNGCryptoServiceProvider
'oder
'RandomNumberGenerator
Public Class PowerFastPrimeGenerator
   Private ReadOnly Rand As New Random
   Private Const MAX4 As Int64 = Int64.MaxValue \ 4
   Private Const MAX6 As Int64 = Int64.MaxValue \ 6
   Public Sub Swap(ByRef l1 As Int64, ByRef l2 As Int64)
      If l1 = l2 Then l1 -= 10
      If l1 > l2 Then
         Dim t = l1 : l1 = l2 : l2 = t
      End If
   End Sub
   Public Function GetPrime() As Int64
      Dim res As Int64
      While True
         'irgend eine zufällige Prüfung
         If (Me.Int64Random(0, 100_000_000) And 1) = 0 Then
            res = Me.GetPrime4()
            If Not res = -1 Then Return res
         End If
         res = Me.GetPrime6()
         If Not res = -1 Then Return res
      End While
      Return -1
   End Function
   Public Function GetPrime(min As Int64, max As Int64) As Int64
      If min >= max Then Return -1
      Dim res As Int64
      While True
         'irgend eine zufällige Prüfung
         If (Me.Int64Random(0, 100_000_000) And 1) = 0 Then
            res = Me.GetPrime4(min, max)
            If Not res = -1 Then Return res
         End If
         res = Me.GetPrime6(min, max)
         If Not res = -1 Then Return res
      End While
      Return -1
   End Function
   Private Function GetPrime4(min As Int64, max As Int64) As Int64
      Dim res As Int64
      While True
         While True
            res = Me.Int64Random(min \ 4 + 1, max \ 4)
            If res < MAX4 Then Exit While
         End While
         If Me.IsMRPrime(res * 4 + 1) Then Return res * 4 + 1
         If Me.IsMRPrime(res * 4 - 1) Then Return res * 4 - 1
      End While
      Return -1
   End Function
   Private Function GetPrime6(min As Int64, max As Int64) As Int64
      Dim res As Int64
      While True
         While True
            res = Me.Int64Random(min \ 6 + 1, max \ 6)
            If res < MAX6 Then Exit While
         End While
         If Me.IsMRPrime(res * 6 + 1) Then Return res * 6 + 1
         If Me.IsMRPrime(res * 6 - 1) Then Return res * 6 - 1
      End While
      Return -1
   End Function
   Private Function GetPrime4() As Int64
      Dim res As Int64
      While True
         While True
            res = Me.Int64Random(0, MAX4)
            If res < MAX4 Then Exit While
         End While
         If Me.IsMRPrime(res * 4 + 1) Then Return res * 4 + 1
         If Me.IsMRPrime(res * 4 - 1) Then Return res * 4 - 1
      End While
      Return -1
   End Function
   Private Function GetPrime6() As Int64
      Dim res As Int64
      While True
         While True
            res = Me.Int64Random(0, MAX6)
            If res < MAX6 Then Exit While
         End While
         If Me.IsMRPrime(res * 6 + 1) Then Return res * 6 + 1
         If Me.IsMRPrime(res * 6 - 1) Then Return res * 6 - 1
      End While
      Return -1
   End Function
   Private Function IsMRPrime(ByVal num As BigInteger) As Boolean
      If (num And 1UL) = 0UL Then
         Return False 'Ist eine gerade Zahl
      End If

      Dim s = 0I
      Dim z As BigInteger = num - 1
      While (z And 1) = 0
         z >>= 1 : s += 1
      End While

      Dim f As BigInteger
      For a As Integer = 2 To 5
         f = BigInteger.ModPow(a, z, num)
         If f = 1 OrElse f = num - 1 Then
            Continue For
         End If
         For r As Integer = 1 To s - 1
            f = BigInteger.ModPow(f, 2, num)
            If f = 1 Then Return False
            If f = num - 1 Then Exit For
         Next
         If Not f = (num - 1) Then Return False
      Next
      Return True
   End Function
   Private Function Int64Random(_min As Int64, _max As Int64) As Int64
      Dim buf = New Byte(7) {}
      Me.Rand.NextBytes(buf)
      Dim r64 = BitConverter.ToInt64(buf, 0)
      Return (Math.Abs(r64 Mod (_max - _min)) + _min)
   End Function
End Class